Plano de Estudos

Matemática Finita MFinit

Contextos

Groupo: 3_Plano 2015/16 a 2021/22 > 1º Ciclo > -

ECTS

6.0 (para cálculo da média)

Objectivos

Desenvolver métodos básicos de teoria dos números, combinatória enumerativa e teoria de grafos, introduzindo estruturas aritméticas e algébricas relevantes do ponto de vista teórico e computacional.

Programa

1. Teoria Elementar de números: Algoritmo de Euclides. Divisibilidade. Primos e teorema fundamental da Aritmética. Congruências. Pequeno teorema de Fermat. Função totiente de Euler. Criptografia de chaves públicas - sistema RSA. 2. Combinatória enumerativa: Princípios básicos de contagem (incluindo a Tabela de Stanley), números binomiais e multinomiais. Princípio de Inclusão-Exclusão. Funções geradoras e relações de recorrência lineares. Contagem com simetria. 3. Teoria de Grafos: Grafos simples e dirigidos, matrizes de incidência e adjacência, árvores, grafos planares, fórmula de Euler, grafo dual e poliedros, teorema de Kuratowski; árvores geradoras, algoritmo PageRank.

Método de Avaliação

Método de ensino: Aulas teóricas: exposição da matéria com ênfase em exemplos concretos Aulas TP: Resolução de exercícios propostos semanalmente, individualmente ou em grupo, através de exposição escrita e/ou oral durante as aulas TP. Alternativas para Avaliação: A) Participação em aulas TP (10%), e 2 Testes durante o período letivo, dispensando exame final (90%) B) Exame final.

Carga Horária

Carga Horária de Contacto -

Trabalho Autónomo - 98.0

Carga Total -

Bibliografia

Principal

Discrete Mathematics, Elementary and beyond: L. Lovász, J. Pélikan, K. Vesztergombi 2003, Spriger, undergraduate texts in Mathematics
Discrete Mathematics: Norman L. Biggs 2003, Oxford UP
Fundamentos de Matemática Discreta: Carlos Florentino 2020

Secundária

An introduction to Combinatorics : A. Slomson 1999, Chapman and Hall
Elementary number theory: G.A. Jones, J.M. Jones 1998, Springer, undergraduate Maths series
Graphes: C. Berge 1973, Gauthier-Villars
Introduction to Graph theory, 5th edition: R.J. Wilson 2010, Prentice Hall
Elements of number theory: J. Stilwell 2003, Springer, undergraduate Texts in Maths
Enumerative Combinatorics (vol i) : R. Stanley 1997, Cambridge University Press
Discrete Mathematics and Its Applications: Kenneth Rosen 2018, McGraw Hill
Discrete Mathematics for computer scientists: J. Truss 1999, Addison Wesley