Matemática Discreta
1
2023-2024
01001168
Matemática
Português
Presencial
Semestral
7.5
Obrigatória
1º Ciclo - Licenciatura
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ãoPrograma
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)
Olga Maria da Silva Azenhas
Métodos de Avaliação
Avaliação
Exame (100%) ou Frequência (80%) + Mini-testes (20%): 100.0%
Bibliografia
Class Notes O.Azenhas,2013
Martin Aigner,A Course in Enumeration,Springer,2010
Keneth Bogart,Combinatorics Through Guided Discovery http://www.math.dartmouth.edu/news-resources/electronic/kpbogart
Miklós Bóna A Walk Through Combinatorics.An introduction to Enumeration and Graph Theory,World Scientific Publishing 2002
Peter J.Cameron Combinatorics: Topics,Techniques,Algorithms,Cambridge University Press,1994
Domingos M.Cardoso, Jerzy Szymanski,Mohammad Rostami,Matemática Discreta,Combinatória,Teoria grafos, Algoritmos,Escolar Editora, 2009
Reinhard Diestel Graph Theory,4th edition,Springer, 2010
George E. Martin,Counting The Art of Enumerative Combinatorics, Springer, 2001
J.M.Simões Pereira Matemática Discreta:Tóp.de Combinatória. Coimbra:Editora Luz da Vida 2006
J.M.Simões Pereira,Matemática Discreta:Grafos Redes e Aplicações,Editora Luz da Vida,2009
Richard Stanley,Enumerative Combinatorics, 1st volume,Cambridge Studies in Adavanced Mathematics49 Cambridge University Press,1997