Plano de Estudos

Matemática Discreta MDisc

Contextos

ECTS

6.0 (para cálculo da média)

Objectivos

Desenvolver métodos básicos de combinatória enumerativa, teoria elementar dos números, 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. Emparelhamentos e o teorema de Hall. Coeficientes binomiais. A 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 chave pública e o protocolo RSA. A notação assintótica O: notas sobre eficiência computacional e segurança. 3. Sequências e somatórios. Relações de recorrência. Relações de recorrência lineares. Funções geradoras. Algoritmos de dividir e conquistar e relações de recorrência associadas. 4. Teoria dos grafos. Grafos simples, matrizes adjacentes. Exemplos e noções básicas. A fórmula da soma dos graus (valências) dos vértices. Exemplos de algumas questões computacionais. Árvores. Árvores de suporte de um grafo. Grafos planares e fórmula de Euler. Sólidos platónicos. Grafos dirigidos. O algoritmo PageRank.

Método de Avaliação

Três mini-testes de total 6 valores e um exame final de 14 valores. O regente reserva-se o direito de efetuar orais caso o julgue necessário.

Carga Horária

Bibliografia

Principal

• Discrete Mathematics and Its Applications: Kenneth Rosen 2018 McGraw-Hill

Secundária

• Concrete Mathematics: A Foundation for Computer Science (2nd Edition): Ronald Graham, Donald Knuth, and Oren Patashnik 1994 Addison-Wesley
• Fundamentos de Matemática Discreta: Carlos Florentino 2020
• Discrete Mathematics: Norman L. Biggs 2003 Oxford University Press
• Matemática Finita: Carlos André e Fernando Ferreira 2000 Universidade Aberta

Disciplinas de Execução

2023/2024 - 2 Semestre

2024/2025 - 2 Semestre