Matemática Discreta

Conhecimentos de Base Recomendados

Conhecimento e domínio da matéria de combinatória lecionada na disciplina de Matemática do ensino secundário. Familiaridade com a indução matemática, resultados da teoria elementar dos números e fundamentos da matemática (lógica e demonstração, conjunto, relação, função) adquiridos nas disciplinas de Teoria dos Números e Análise Infinitesimal I.

Métodos de Ensino

As aulas TP são expositivas e incluem exemplos, para motivar e clarificar os conceitos, e exercícios de aplicação dos conhecimentos adquiridos. A resolução de problemas por parte dos alunos é fundamental. Problemas mais avançados de cariz opcional são também propostos.

Durante o semestre, os alunos dispõem de um tempo de orientação tutorial para esclarecimento de dúvidas na aquisição de conhecimentos e na resolução de problemas.

Resultados de Aprendizagem

Trata-se de um curso introdutório à análise combinatória: combinatória enumerativa e teoria dos grafos. A combinatória é um ramo da matemática transversal a várias áreas que vai desde  problemas de jogos de cartas, à álgebra e à internet . O objetivo é dar a conhecer aos estudantes os métodos básicos desta área, com incidência na contagem e na teoria dos grafos.

As principais competências a desenvolver são: capacidade de generalização, abstração e cálculo; capacidade de formular e resolver problemas; capacidade de constuir modelos matemáticos e usá-los em contagens bem como na resolução de  problemas reais; argumentação lógica; capacidade de aprendizagem autónoma; imaginação e criatividade; iniciativa individual.

Estágio(s)

Não

Programa

Tópicos de combinatória.  Princípio do pombal, indução matemática e recursão. Princípios de contagem elementar. Subconjuntos e coeficientes binomiais. Multiconjuntos, composições e coeficientes multinomiais. Partições de inteiros. Partições de conjuntos.  Permutações e ciclos de uma permutação. Números de Stirling e de Bell. Princípio da inclusão-exclusão. Funções  geradoras e relações de recorrência.

Tópicos de grafos. Digrafos e redes: definições básicas, conexões e conectividades, estruturas, árvores, percursos de Euler e de Hamilton, planaridade, índices fundamentais. Subgrafos e menores. Alguns dos algoritmos mais conhecidos (por exemplo, DFS, BFS, Kruskal, Warshall, do caminho mais curto, dos fluxos).

Docente(s) responsável(eis)

Ricardo Nuno Fonseca de Campos Pereira Mamede

Métodos de Avaliação

Avaliação continua
Mini Testes: 20.0%
Frequência: 80.0%

Avaliação final
Exame: 100.0%

Bibliografia

O. Azenhas, Class Notes, 2013

M. Aigner, A Course in Enumeration, Springer, 2010

K. Bogart, Combinatorics Through Guided Discovery  http://www.math.dartmouth.edu/news-resources/electronic/kpbogart

M. Bóna, A. Walk, Through Combinatorics. An introduction to Enumeration and Graph Theory, World Scientific Publishing, 2002.

P. J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press,1994

D. M. Cardoso, J. Szymanski, M. Rostami, Matemática Discreta, Combinatória, Teoria dos grafos, Algoritmos, Escolar Editora, 2009

R. Diestel, Graph Theory, 4th edition, Springer, 2010.

G. E. Martin, Counting: The Art of Enumerative Combinatorics, Springer, 2001.

J. M. Simões Pereira, Matemática Discreta: Tópicos de Combinatória, Ed. Luz da Vida, 2006

J. M. Simões Pereira, Matemática Discreta: Grafos Redes e Aplicações, Ed. Luz da Vida, 2009    

R. Stanley, Enumerative Combinatorics, Vol.1, Cambridge Studies in Advanced Mathematics 49, Cambridge University Press, 1997