Aula 1 22/09/10 Apresentação da disciplina: programa, avaliação, plano das aulas, atendimento aos alunos, página da disciplina. 0. Introdução: o que é a Matemática Discreta? Problemas motivadores: existência, contagem e optimização. 1. Fundamentos 1.1. Introdução à Lógica. Cálculo Proposicional. Sintaxe e semântica da lógica proposicional.
Aula 2 29/09/10 Fórmulas logicamente equivalentes. Algumas equivalências básicas. Prova da equivalência de duas fórmulas: tabelas de verdade, deduções formais usando as leis básicas, método de Quine. Formas normais conjuntivas e disjuntivas. Algoritmo. Funções de verdade.
Aula 3 6/10/10 Predicados. Quantificadores. Breve referência ao Cálculo de Predicados. Lógicas de Primeira Ordem. O Tarski World. 1.2. Raciocínio matemático, indução e recursão Quando é que um argumento matemático está correcto? O que é uma prova. Falácias. Digressão por algumas técnicas de prova: verificação exaustiva. Exemplos: conjectura de Goldbach, conjectura de Polya.
Aula 4 13/10/10 Mais técnicas de prova: condicionais, equivalências, redução ao absurdo, indução matemática. Provas por indução matemática: O método de indução matemática. Exemplos de aplicação. Visualização de alguns aplicativos ilustrativos. 1.3. Algoritmos e complexidade. Definições recursivas e algoritmos recursivos.
Aula 5 20/10/10 Exemplos: factorial; função de Collatz. Análise da conjectura de Collatz com a ajuda do Mathematica. Medida da complexidade de um algoritmo. Complexidade polinomial e complexidade exponencial. Exemplos. Análise da eficiência de um algoritmo na pior situação. Algoritmos optimais na pior situação. Árvores de decisão. Somatórios. Propriedades dos somatórios.
Aula 6 37/10/10 Técnicas para resolver somatórios. Funções floor e ceiling. Progressões aritméticas e progressões geométricas. Mais técnicas de somatórios: O método da perturbação. O método ad hoc: Visualização de alguns aplicativos ilustrativos.
Aula 7 3/11/10 2. Grafos. Problema das pontes de Konigsberg. Grafos simples, pseudografos e grafos dirigidos. Grafos completos. Grau de um vértice. Propriedades. Matrizes de adjacência e de incidência. Caminhos e ciclos. Grafos conexos. Caminhos eulerianos. Grafos eulerianos. Caracterização dos grafos eulerianos: Teorema de Euler. Exemplos. Solução do problema das 7 pontes. Algoritmo para a enumeração de um caminho euleriano.
Aula 8 10/11/10 Ilustração de alguns dos conceitos estudados na aula anterior com a ajuda do programa Mathematica. Grafos planares. Grafos regulares. Caminhos semi-eulerianos. Grafos semi-eulerianos. Caminhos hamiltonianos. Grafos hamiltonianos. O problema do trajecto mais curto. Algoritmo de Dijkstra. O problema do caixeiro-viajante.
Aula 9 17/11/10 Árvores. Propriedades. Raiz; vértice interno, folha. Árvores m-árias; árvores m-árias plenas. Propriedades. 3. Os inteiros. Criptografia. O algoritmo da divisão inteira. Aritmética modular. Adição e multiplicação módulo n. Aplicações: a cifra de César.
Aula 10 24/11/10 Continuação da aula anterior. Cifras aditivas e multiplicativas. Elementos invertíveis. Máximo divisor comum. Algoritmo de Euclides. Resolução de congruências. Aplicações: a cifra de César; a criptografia moderna: o método RSA de chave pública. Exemplo de simulação do método RSA.
Aula 11 15/12/10 4. Contagem 4.1. Técnicas básicas Estratégias básicas para resolver problemas de contagem. Princípio da Multiplicação e Princípio da Adição. Exercícios. Permutações e combinações de n elementos r a r. Números binomiais. Propriedades. Fórmula de Pascal. Triângulo de Pascal. Binómio de Newton: demonstração por indução. 4.2. Técnicas avançadas Permutações e combinações de n elementos r a r, com repetição de elementos. Exemplo: o paradoxo dos aniversários.