Disciplina Curricular

Matemática Discreta MDisc

Licenciatura Bolonha em Engenharia Informática - 3_Plano 2015/16 a 2024/25

Contextos

Grupo: 3_Plano 2015/16 a 2024/25 > 1º Ciclo > 2º Ano

Período:

Peso

6.0 (para cálculo da média)

Objectivos

Desenvolver métodos básicos de combinatória enumerativa, teoria elementar dos números, funções geradoras e relações de recorrência e teoria dos grafos. Alguma ênfase em questões computacionais.

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.