Disciplina Curricular
Matemática Discreta MDisc
Licenciatura Bolonha em Matemática - 4_LMat 2022/23
Contextos
Grupo: 4_LMat 2022/23 > 1º Ciclo > Matemática - Tronco Comum
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, 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étodos de ensino e 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.