Semestre 2017.2

Quando: terças e quintas, 14h50 às 16h40.
Onde: sala a decidir

Bibliografia:

• Tertuliano Franco, Princípios de Análise Combinatória
• Judith Gersting, Mathematical Structures for Computer Science
• Gary Haggard, John Schlipf, Sue Whitesides, Discrete Mathematics for Computer Science
• Elon Lages, Análise Real Vol. I

1ª Lista de exercícios

Ementa:

• 1ª parte
1. Lógica proposicional
2. O que é uma Prova? Tipos de prova
   • Por contraexemplo
   • Por exaustão
   • Prova direta
   • Contraposição
   • Contradição
3. Conjuntos, relações, relações de equivalência e funções (incluindo Union and Find Algorithm)
4. O que é um número natural? Axiomas de Peano
5. Enumerabilidade e não enumerabilidade. Diagonal de Cantor
6. Princípio de Indução
• 2ª parte
1. Regra da Soma e do Produto
2. Contagem via relações de equivalência: permutações, combinações etc.
3. Princípio de Inclusão-Exclusão (e Números de Stirling de Primeira e Segunda Ordem)
4. Recorrências (incluindo Divide and Conquer Algorithm)
5. Métodos de Resolução de Recorrências
• 3ª parte
1. Métodos de Resolução de Recorrências (continuação)
2. Princípio da Reflexão e Números de Catalan
3. Triângulo de Pascal e Binômio de Newton
4. Contagem de Partições via funções geradoras

Avaliação: Três provas.

• 1ª prova: 9 de novembro de 2017
• 2ª prova: 19 de dezembro de 2017
• 1ª prova (substitutiva): 11 de janeiro de 2018
• 3ª prova: 22 de fevereiro de 2018