- Professor: Hugo Nobrega
- Turma: 12720
- Grupo de discussões: Discord
- Monitores: a definir
- 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 15:00 às 17:00 na sala F3-014 do CCMN.
Conteúdo programático, plano de aulas, previsões de avaliações
Bibliografia
- Notas de aula de 25-2
- Notas de aula de turmas anteriores dessa disciplina: 24-1 24-2
- 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 | 3 de setembro às 20:00 |
| Lista 2 | 1 de outubro às 20:00 |
| Lista 3 | 29 de outubro às 20:00 |
| Lista 4 | 8 de dezembro à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 |
|---|---|---|---|
| ter 5 ago | 01 | Informações sobre o funcionamento da disciplina; discussão sobre o conceito de “discreta” e sua relação com a computação | Vídeo; Quadros |
| qui 7 ago | 02 | Recursão: introdução; análise de quando funciona; “agendamento de tarefas” em uma definição recursiva | Vídeo; Quadros |
| ter 12 ago | 03 | Mais exemplos de recursão; indução (“provas construídas por recursão”) | Vídeo; Quadros |
| qui 14 ago | 04 | Exemplos de prova por indução | Vídeo; Quadros; Código |
| ter 19 ago | 05 | Mais provas por indução; discussão sobre conjuntos, funções, relações | Vídeo; Quadros |
| qui 21 ago | 06 | Conjuntos, listas, multiconjuntos; Funções injetivas, sobrejetivas, bijetivas; Combinatória de contagem: Princípio da Bijeção (PB) | Vídeo; Quadros |
| ter 26 ago | 07 | Relações: reflexividade, simetria, antissimetria, transitividade, totalidade, ordens parciais, ordens totais, relações de equivalência; Partições; Princípio Aditivo (PA) | Vídeo; Quadros |
| qui 28 ago | 08 | Exemplos de aplicação do PA; Princípio Multiplicativo (PM) e alguns exemplos; Discussão e exemplos do Princípio da Bijeção; curiosidades sobre os números de Catalan | Vídeo (sem imagem); Quadros |
| ter 2 set | 09 | Fórmula recursiva “de Catalan” (resolvendo problemas da aula 08); arranjos completos (com reposição) | Vídeo (sem áudio); Quadros; Código |
| qui 4 set | 10 | Mais aplicações de PA e PM: arranjos, permutações. Princípio k-para-1; permutações com repetição, combinações, combinações com repetição (paradigma “bolas e traços”) | Vídeo (sem áudio); Quadros |
| ter 9 set | 11 | Mais exemplos de combinação com repetição/bolas e traços; Permutação circular; aplicação: Pequeno Teorema de Fermat | Vídeo; Quadros |
| qui 12 set | 12 | Princípio da Inclusão-Exclusão; exemplos (função de Euler; funções sobrejetivas) | Vídeo; Quadros |
| ter 16 set | 13 | “Argumentos combinatórios”; Triângulo de Pascal | Vídeo; Quadros; Código do Triângulo de Pascal |
| qui 18 set | 14 | Mais argumentos combinatórios (“identidade do taco de hóquei”, teorema binomial, outros) | Vídeo; Quadros |
| ter 23 set | sem aula | Semana de Integração Acadêmica (SIAc) | |
| qui 25 set | sem aula | Semana de Integração Acadêmica (SIAc) | |
| ter 30 set | 15 | Recorrências lineares homogêneas: a busca por forma fechada; Código para investigar recorrências; Código para imprimir tabelas | Vídeo; Quadros |
| qui 2 out | 16 | Aula de dúvidas e revisão para P1 | Vídeo; Quadros |
| ter 7 out | P1 | PROVA 1 | |
| qui 9 out | 17 | Recorrências lineares homogêneas: método para encontrar forma fechada no caso “equação característica tem raízes distintas” | Vídeo; Quadros |
| ter 14 out | 18 | Discussão da P1; Recorrências lineares homogêneas, caso “equação característica pode ter raízes não todas distintas” | Vídeo; Quadros |
| qui 16 out | 19 | Recorrências lineares não puramente homogêneas: o caso “homogênea + polinômio”; Questões de Recorrência Linear (para praticar) | Vídeo; Quadros |
| ter 21 out | 20 | Recorrências lineares não puramente homogêneas: o caso “homogênea + exponencial” EXTRA: explicação para o caso “raízes repetidas” | Vídeo; Quadros |
| qui 23 out | 21 | Introdução à teoria dos grafos: definição, definições recursivas, prova (por indução!) de que em todo grafo há quantidade par de vértices de grau ímpar | Vídeo; Quadros |
| ter 28 out | 22 | Passeios, trilhas, caminhos, ciclos | Vídeo; Quadros |
| qui 30 out | 23 | Árvores | Vídeo; Quadros |
| ter 4 nov | 24 | Aula de dúvidas e revisão para P2 | Vídeo; Quadros |
| qui 6 nov | P2 | PROVA 2 | |
| ter 11 nov | 25 | Árvores geradoras; discussão da P2; grafos Hamiltonianos e Eulerianos (introdução) | Vídeo (áudio ruim!); Quadros |
| qui 13 nov | 26 | Grafos Eulerianos | Vídeo; Quadros |
| ter 18 nov | 27 | Coloração (de vértices) em grafos; grafos bipartidos | Vídeo; Quadros |
| qui 20 nov | sem aula | Feriado (Consciência Negra) | |
| ter 25 nov | 28 | Grafos planares: teorema de Euler, K_5 e K3,3 não são planares | Vídeo; Quadros |
| qui 27 nov | 29 | “Teoremas das n cores: Grafos planares são \(n\) coloríveis” para \(n=6\) e \(n=5\) | Vídeo; Quadros |
| ter 2 dez | - | “Monitoria” com o professor | Sem vídeo; Sem quadros |
| qui 4 dez | - | “Monitoria” com o professor | |
| ter 9 dez | 30 | Aula de dúvidas e revisão para P3 | Vídeo; Quadros |
| qui 11 dez | P3 | PROVA 3 | |
| ter 16 dez | Provas | Provas de Segunda Chamada: P1, P2 | |
| qui 18 dez | |||
Método de avaliação
Teremos 4 listas de exercícios e 3 provas.
Descartaremos a pior nota dentre as listas de exercícios, e ML será a média aritmética das restantes.
A média das provas, MP, é a média ponderada das notas das 3 provas, sendo a maior nota com peso 3, a segunda maior com peso 2, e a menor com peso 1.
A média final é:
- MP, se MP \(<\) 5;
- 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.