Aula 1 26/09/07 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.
Aula 2 3/10/07 Lógica: Cálculo Proposicional (conclusão).
Aula 3 10/10/07 Predicados. Quantificadores. Breve referência ao Cálculo de Predicados. Lógicas de Primeira Ordem. O Tarski World. 1.2. Algoritmos e complexidade. Medida da complexidade de um algoritmo. Complexidade polinomial e complexidade exponencial. Exemplos.
Aula 4 17/10/07 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. Técnicas para resolver somatórios.
Aula 5 24/10/07 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. 1.3. Os inteiros. Criptografia. O algoritmo da divisão inteira. Aritmética modular.
Aula 6 31/10/07 Adição e multiplicação módulo n. 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.
Aula 7 7/11/07 Não houve aula por determinação superior (realização de testes diagnóstico de Português/Inglês aos alunos do 1º ano da FCTUC).
Aula 8 14/11/07 Demonstração do resultado que suporta o método RSA: o Teorema pequeno de Fermat. Exemplo de simulação do método. 1.4. 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, condicionais, equivalências, redução ao absurdo, indução matemática.
Aula 9 21/11/07 Provas por indução matemática: O método de indução matemática. Exemplos de aplicação. Definições recursivas e algoritmos recursivos. Exemplos: factorial; função de Collatz. Análise da conjectura de Collatz com a ajuda do Maple. 2. Contagem 2.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.
Aula 10 28/11/07 Números binomiais. Propriedades. Fórmula de Pascal. Triângulo de Pascal. Binómio de Newton: demonstração por indução. 2.2. Técnicas avançadas Permutações e combinações de n elementos r a r, com repetição de elementos. Exemplos: o paradoxo dos aniversários.
Aula 11 05/12/07 Princípio da inclusão-exclusão. Exemplos e aplicações. O problema dos desencontros. Relações de recorrência. Método de resolução das lineares, homogéneas, com coeficientes constantes. Exemplo: a sucessão de Fibonacci.
Aula 12 12/12/07 Não houve aula.
Aula 13 17/12/07 3. Grafos. Problema das 7 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 e caminhos hamiltonianos. Grafos eulerianos e grafos hamiltonianos. 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.