- 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
| Lista | Data Limite de Entrega |
|---|---|
| Lista 1 | 29 de abril às 20:00 |
| Lista 2 | 24 de maio às 20:00 |
| Lista 3 | 28 de junho às 20:00 |
| Lista 4 | 15 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
| Data | Aula | Conteúdo | Material |
|---|---|---|---|
| 19/3 ter | 1 | Apresentação da disciplina; discussão sobre o propósito da Matemática Discreta para a Computação | Slides |
| 21/3 qui | 2 | Recursão | Vídeo, Slides, Código, Output do REPL |
| 26/3 ter | 3 | Mais sobre recursão (“explicação mais precisa”); indução como caso particular de recursão | Slides |
| 28/3 qui | 4 | Ainda recursão e indução | Vídeo (sem áudio), Slides |
| 2/4 ter | 5 | Mais exemplos de recursão e indução | Vídeo, Slides |
| 4/4 qui | 6 | Discussão sobre os conceitos “conjunto”, “função”, “relação” | Vídeo, Slides, Código |
| 9/4 ter | - | JICTAC (SEM AULA) | |
| 11/4 qui | 7 | Combinatória de contagem à la Cerioli & Viana: objetos, estruturas, configurações; princípio da contagem direta; princípio da bijeção | Vídeo, Slides |
| 16/4 ter | 8 | Principios: aditivo, multiplicativo, k-para-1 | Vídeo, Slides |
| 18/4 qui | 9 | Aplicações dos princípios; arranjos, combinações, permutações | Vídeo, Slides |
| 23/4 ter | - | Feriado (São Jorge) | |
| 25/4 qui | 10 | Mais aplicações dos princípios; permutações com repetições; exercícios | Vídeo, Slides |
| 30/4 ter | 11 | Discussão sobre “combinação com reposição” e raciocínios incorretos; Permutações circulares | Vídeo, Slides, Código |
| 2/5 qui | 12 | “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 contagem | Vídeo, Slides |
| 7/5 ter | 13 | Princípio da Inclusão-Exclusão | Vídeo, Slides |
| 9/5 qui | 14 | Exemplo de PIE: Função φ (totiente) de Euler; algumas identidades combinatórias; triângulo de Pascal | Video, Slides |
| 14/5 ter | 15 | Mais identidades combinatórias; Teorema Binomial | Vídeo, Slides |
| 16/5 qui | 16 | Recorrências: lineares e não lineares, homogêneas e não homogêneas | Vídeo, Slides, Código em Python |
| 21/5 ter | - | sem aula (paralisação dos docentes) | |
| 23/5 qui | 17 | Recorrências lineares homogêneas (caso “raízes distintas”) | Vídeo, Slides, Output do Python |
| 28/5 ter | 18 | Recorrê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 ter | 19 | Revisão para P1 | Vídeo, Slides, Código em Python |
| 6/6 qui | P1 | PROVA 1 | - |
| 11/6 ter | 20 | Recorrências lineares não homogêneas: caso polinomial | Vídeo, Slides |
| 13/6 qui | 21 | Recorrências lineares não homogêneas: outra técnica envolvendo “chute”; grafos (introdução) | Vídeo, Slides, Código em Python |
| 18/6 ter | 22 | Grafos: definições recursivas, provas indutivas (“em todo grafo simples, a quantidade de vértices de grau ímpar é par”); passeios, caminhos, conectividade | Vídeo, Slides |
| 20/6 qui | 23 | Grafos: conectividade minimal, ausência de ciclos maximal; árvores | Vídeo, Slides |
| 25/6 ter | 24 | Grafos: construção de árvores, número de arestas de árvores, árvores geradoras | Vídeo, Slides |
| 27/6 qui | - | sem aula (professor doente) | |
| 2/7 ter | 25 | Grafos: grafos Eulerianos e Hamiltonianos (definição); prova de quais grafos são Eulerianos; coloração de vértices | Vídeo, Slides |
| 4/7 qui | 26 | Grafos: G é 2-colorível sse G não tem ciclo ímpar (ou passeio fechado ímpar) | Vídeo, Slides |
| 9/7 ter | 27 | Revisão para a P2 | Vídeo, Slides |
| 11/7 qui | P2a | PROVA 2 (primeira rodada) | |
| 16/7 ter | P2b | PROVA 2 (segunda rodada) | |
| 18/7 qui | P2aCh | PROVA 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.