Plano de Estudos
Matemática Discreta MDisc
Contextos
Groupo: 1_PGCFCE 2023/24 a 2025/26 > Pós-graduação > Percurso Matemática > 665_Perfil Matemática > 2º ano > 2º semestre
Groupo: 1_PGCFCE 2023/24 a 2025/26 > Pós-graduação > Percurso Matemática > 665_Perfil Matemática > 1º ano > 2º semestre
ECTS
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.
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
Carga Horária de Contacto -
Trabalho Autónomo - 98.0
Carga Total -
Bibliografia
Principal
- Fundamentos de Matemática Discreta: Carlos Florentino 2020 Apontamentos
- Matemática Finita: Carlos André e Fernando Ferreira 2000 Universidade Aberta
- Notas de Teoria Elementar dos Números: Fernando Ferreira 2024 Apontamentos
Secundária
- Concrete Mathematics: A Foundation for Computer Science (2nd Edition): Ronald Graham, Donald Knuth, and Oren Patashnik 1994 Addison-Wesley
- Discrete Mathematics and Its Applications: Kenneth Rosen 2018 McGraw-Hill
- Discrete Mathematics: Norman L. Biggs 2003 Oxford University Press