Matemática Discreta (24-1)

  • Professor: Hugo Nobrega
  • Turma: 11019
  • Grupo de discussões: Discord
  • Monitores: Anna Cristina, Christopher Ciafrino, João Victor Lopez
  • Local das aulas: F3-014

Funcionamento da disciplina

O meio primário de comunicação entre os alunos, monitores e professores será o grupo listado acima.

As aulas serão realizadas em modalidade presencial, com aulas às 3as e 5as de 08:00 às 10:00 na sala F3-014 do CCMN.

Bibliografia

  • L. Lovász, J. Pelikán e K. Vestergombi, Matemática Discreta. Série Textos Universitários, SBM, 2003. PDF da versão em inglês disponível gratuitamente se acessado a partir da UFRJ.
  • M. R. Cerioli e P. Viana, Minicurso de Combinatória de Contagem. II Colóquio de Matemática da Região Sul, 2012. PDF disponível gratuitamente.
  • J. Plínio, M. Mello, I. Murari, Introdução à Análise Combinatória, 4a edição. Ciência Moderna, 2007. Disponível em várias bibliotecas da UFRJ (CCMN, NCE, IM)
  • A. Morgado, J. Pitombeira, P. Carvalho, P. Fernandez, Análise combinatória e probabilidade. Série Coleção do Professor de Matemática, SBM, 2016. Disponível em várias bibliotecas da UFRJ (CCMN, NCE, IM)
  • D. Hunter, Fundamentos de Matemática Discreta, Capítulo 3: Pensamento Recursivo. LTC, 2019
  • Uma boa fonte adicional (porém em inglês) para o material de provas, lógica, conjuntos, etc. é: R. Hammack, Book of Proof, 3a edição. PDF disponível gratuitamente

Listas de Exercícios

ListaData Limite de Entrega
Lista 129 de abril às 20:00
Lista 224 de maio às 20:00
Lista 328 de junho às 20:00
Lista 415 de julho às 20:00

Regras de colaboração

As listas de exercícios podem ser entregues em duplas. Não poderá haver repetição de duplas em diferentes listas! Isso é feito para aumentar a confiança do professor ao dar uma nota individual para cada aluno no final da disciplina.

As diferentes duplas podem sempre discutir os problemas e as ideias de como resolvê-los (e isso é recomendado, pois é uma ótima forma de estudar e aprender!), porém: soluções de exercícios não devem ser compartilhadas entre diferentes duplas (nem de outros períodos). O recomendável é que você não mostre suas soluções completas para alunos de outras duplas, nem veja as soluções completas de outros.

Soluções iguais ou parecidas demais entre duplas diferentes serão desconsideradas.

Cronograma planejado/registro de atividades

DataAulaConteúdoMaterial
19/3 ter1Apresentação da disciplina; discussão sobre o propósito da Matemática Discreta para a ComputaçãoSlides
21/3 qui2RecursãoVídeo, Slides, Código, Output do REPL
26/3 ter3Mais sobre recursão (“explicação mais precisa”); indução como caso particular de recursãoSlides
28/3 qui4Ainda recursão e induçãoVídeo (sem áudio), Slides
2/4 ter5Mais exemplos de recursão e induçãoVídeo, Slides
4/4 qui6Discussão sobre os conceitos “conjunto”, “função”, “relação”Vídeo, Slides, Código
9/4 ter-JICTAC (SEM AULA)
11/4 qui7Combinatória de contagem à la Cerioli & Viana: objetos, estruturas, configurações; princípio da contagem direta; princípio da bijeçãoVídeo, Slides
16/4 ter8Principios: aditivo, multiplicativo, k-para-1Vídeo, Slides
18/4 qui9Aplicações dos princípios; arranjos, combinações, permutaçõesVídeo, Slides
23/4 ter-Feriado (São Jorge)
25/4 qui10Mais aplicações dos princípios; permutações com repetições; exercíciosVídeo, Slides
30/4 ter11Discussão sobre “combinação com reposição” e raciocínios incorretos; Permutações circularesVídeo, Slides, Código
2/5 qui12“Número de soluções naturais de uma equação \(x_0 + x_1 + … + x_{n-1} = k\)” como permutação com repetição; número de combinações completas (com reposição) como número de soluções naturais de equação; Pequeno Teorema de Fermat através dos princípios de contagemVídeo, Slides
7/5 ter13Princípio da Inclusão-ExclusãoVídeo, Slides
9/5 qui14Exemplo de PIE: Função φ (totiente) de Euler; algumas identidades combinatórias; triângulo de PascalVideo, Slides
14/5 ter15Mais identidades combinatórias; Teorema BinomialVídeo, Slides
16/5 qui16Recorrências: lineares e não lineares, homogêneas e não homogêneasVídeo, Slides, Código em Python
21/5 ter-sem aula (paralisação dos docentes)
23/5 qui17Recorrências lineares homogêneas (caso “raízes distintas”)Vídeo, Slides, Output do Python
28/5 ter18Recorrências lineares: homogêneas sem raízes distintas; não homogêneas (início)Vídeo, Slides, Output do Python
30/5 qui-Feriado (Corpus Christi)
4/6 ter19Revisão para P1Vídeo, Slides, Código em Python
6/6 quiP1PROVA 1-
11/6 ter20Recorrências lineares não homogêneas: caso polinomialVídeo, Slides
13/6 qui21Recorrências lineares não homogêneas: outra técnica envolvendo “chute”; grafos (introdução)Vídeo, Slides, Código em Python
18/6 ter22Grafos: definições recursivas, provas indutivas (“em todo grafo simples, a quantidade de vértices de grau ímpar é par”); passeios, caminhos, conectividadeVídeo, Slides
20/6 qui23Grafos: conectividade minimal, ausência de ciclos maximal; árvoresVídeo, Slides
25/6 ter24Grafos: construção de árvores, número de arestas de árvores, árvores geradorasVídeo, Slides
27/6 qui-sem aula (professor doente)
2/7 ter25Grafos: grafos Eulerianos e Hamiltonianos (definição); prova de quais grafos são Eulerianos; coloração de vérticesVídeo, Slides
4/7 qui26Grafos: G é 2-colorível sse G não tem ciclo ímpar (ou passeio fechado ímpar)Vídeo, Slides
9/7 ter27Revisão para a P2Vídeo, Slides
11/7 quiP2aPROVA 2 (primeira rodada)
16/7 terP2bPROVA 2 (segunda rodada)
18/7 quiP2aChPROVA de 2a Chamada: Prova 1, Prova 2

Método de avaliação

Teremos ?? listas de exercícios e 2 provas.

Descartaremos a pior nota dentre as listas de exercícios, e ML será a média aritmética das restantes.

MP será a média ponderada das notas das provas, sendo a maior nota com peso 3 e a menor nota com peso 2.

A média final é:

  • MP, se MP \(<\) 4;
  • a média ponderada entre ML e MP, sendo ML com peso 1 e MP com peso 2, caso contrário.

A nota para aprovação é 5,0; não há prova final.