Programa

Matemática Discreta

Curso Livre em MINOR - Alunos Externos

Licenciatura Bolonha em Física

Licenciatura Bolonha em Biologia

Licenciatura Bolonha em Engenharia Informática

Licenciatura Bolonha em Ciência de Dados

Licenciatura Bolonha em Estudos Gerais

Licenciatura Bolonha em Química

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.