Programa

Matemática Discreta

Curso Livre em MINOR - Alunos Externos

Licenciatura Bolonha em Matemática

Licenciatura Bolonha em Química

Licenciatura Bolonha em Estatística Aplicada

Licenciatura Bolonha em Física

Licenciatura Bolonha em Biologia

Licenciatura Bolonha em Engenharia Informática

Licenciatura Bolonha em Estudos Gerais

Pós-Graduação em Curso de Formação em Ciências para o Ensino

Pós-Graduação em Ciências para o Ensino (Complementar)

Pós-Graduação em Ciências para o Ensino

Programa

1) Combinatória enumerativa: Princípios básicos de contagem. Coeficientes binomiais. Outros coeficientes. Tabela de Stanley. Princípio da inclusão-exclusão. (2) Teoria elementar dos números. Divisibilidade. Algoritmo de Euclides. Primos e teorema fundamental da aritmética. Congruências. Pequeno teorema de Fermat. Criptografia de chaves públicas: o sistema RSA. Notação assintótica e notas sobre análise algorítmica, segurança e ataques maliciosos. (3) Funções geradoras. Somatórios. Relações de recorrência. Relações de recorrência lineares. Recorrências associadas a algoritmos de "dividir para conquistar". (4) Teoria dos grafos. Grafos simples e dirigidos, matrizes de adjacência. O lema do aperto de mão. Sequências gráficas e o algoritmo de Havel-Hakimi. Caminhos e ciclos. Conexidade. Problemas computacionalmente difíceis: o exemplo dos grafos Hamiltonianos. Grafos planares e fórmula característica de Euler. Poliedros convexos e sólidos platónicos. Árvores, árvores geradoras.