Matemática Discreta

Ano
1
Ano lectivo
2021-2022
Código
01001168
Área Científica
Matemática
Língua de Ensino
Português
Modo de Ensino
Presencial
Duração
Semestral
Créditos ECTS
7.5
Tipo
Obrigatória
Nível
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ã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)

João Eduardo da Silveira Gouveia

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