Disciplina Curricular
Matemática Discreta MDisc
Licenciatura Bolonha em Química - 7_LQ 2022/23
Contextos
Grupo: 7_LQ 2022/23 > 1º Ciclo > Licenciatura em Química ou Minor > Licenciatura em Química com Minor > Minor em Matemática > 559_Minor em Matemática
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.
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.