MCCC003-23 Algoritmos em Grafos 2026-3
Professor Jair Donadelli --- email jair.donadelli @ ufabc.edu.br — sala 546-2 bloco A
Nesta disciplina, revemos conceitos básicos da teoria dos grafos, apresentamos algoritmos eficientes para problemas clássicos em grafos juntamente com a análise de tempo de execução e prova de correção dos algoritmos estudados.
Espera-se que ao final do curso o aluno seja capaz de modelar problemas em grafos, adquira familiaridade com técnicas de prova de correção de algoritmos, conheça os principais problemas em grafos e os algoritmos eficientes que os resolvem.
| Horários: | Sala: |
|---|---|
| Terça 8-10h | |
| Quinta 10-12h | |
| Recomendação: | T-P-E-I: |
| Natureza da Informação; Funções de Uma Variável; Algoritmos e Estruturas de Dados I e II; Programação Estruturada; Matemática Discreta I e II. | 4-0-0-4 |
Programação da disciplina
Ementa
Revisão da terminologia básica de Teoria dos Grafos. Noções de análise de algoritmos. Estruturas de dados para representação de grafos. Buscas em largura e profundidade e suas aplicações: caminhos mínimos sem pesos, componentes conexas. Grafos ponderados. Árvores geradoras mínimas: algoritmos de Prim e Kruskal. Grafos Eulerianos e Hamiltonianos. O Problema do Caixeiro Viajante. Digrafos: definições básicas, componentes fortemente conexas e ordenação topológica. Caminhos mínimos em digrafos ponderados: algoritmos de Dijkstra, Bellman-Ford e Floyd–Warshall. Fluxo máximo: algoritmo de Ford-Fulkerson e suas aplicações.
Bibliografia básica
BONDY, J. A.; MURTY, U. S. R. Graph theory. New York: Springer, 2008. (Graduate Texts in Mathematics, v. 244).
ERICKSON, Jeff. Algorithms. 1. ed. [S. l.], 2019. Disponível em: https://jeffe.cs.illinois.edu/teaching/algorithms/.
CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro: Elsevier, 2012
Calendário
Reposição dos feriados: não há
Aulas
| Semana | Tema principal | Tópicos | Referências | Atividades |
|---|---|---|---|---|
| 01 | Fundamentos | Terminologia básica; grafos simples e multigrafos; grafos direcionados; adjacência; grau; caminhos e ciclos; subgrafos; conectividade; representações por matriz e lista de adjacência; noções de análise de algoritmos | Bondy & Murty; Erickson; Cormen et al. | |
| 02 | Fundamentos | |||
| 03 | Busca em largura e busca em profundidade | Busca em largura (BFS); busca em profundidade (DFS); árvores de busca; descoberta e finalização de vértices; propriedades das buscas | Erickson; Cormen et al. | |
| 04 | Aplicações de BFS e DFS | Caminhos mínimos em grafos não ponderados; componentes conexas; detecção de ciclos; alcançabilidade; aplicações de BFS e DFS | Erickson; Cormen et al. | |
| 05 | Árvores geradoras mínimas | Grafos ponderados; árvores geradoras; problema da árvore geradora mínima; propriedade do corte; propriedade do ciclo; algoritmos gulosos | Erickson; Cormen et al.; Bondy & Murty | |
| 06 | Grafos Eulerianos, Hamiltonianos e TSP | Trilhas e circuitos eulerianos; caminhos e ciclos hamiltonianos; problema do Caixeiro Viajante; formulação de problemas; algoritmos eficientes versus problemas computacionalmente difíceis | Bondy & Murty; Erickson | |
| 07 | Digrafos e ordenação topológica | Digrafos; graus de entrada e saída; DAGs; ordenação topológica; componentes fortemente conexas | Bondy & Murty; Erickson; Cormen et al. | |
| 08 | Caminhos mínimos em digrafos I | Problema dos caminhos mínimos; relaxação; propriedades de caminhos mínimos; pesos não negativos | Erickson; Cormen et al. | |
| 09 | Caminhos mínimos em digrafos II | Pesos negativos; ciclos negativos; caminhos mínimos de uma origem; caminhos mínimos entre todos os pares | Erickson; Cormen et al. | |
| 10 | Fluxo máximo | Redes de fluxo; capacidades; conservação de fluxo; fluxos e cortes; caminhos aumentantes; fluxo máximo; corte mínimo | Erickson; Cormen et al. | |
| 11 | Fluxo máximo |
Bibliografia complementar
BRASSARD, Gilles; BRATLEY, Paul. Fundamentals of algorithmics. Englewood Cliffs: Prentice Hall, 1996.
SEDGEWICK, Robert. Algorithms in c, Part 5: Graph Algorithms. 3. ed. Reading, USA: AddisonWesley Professional, 2002. 482 p.
MANBER, Udi. Introduction to algorithms: a creative approach. Addison-Wesley.(Capítulo 7)
DASGUPTA, Sanjoy; PAPADIMITRIOU, Christos H.; VAZIRANI, Umesh V. Algorithms. Boston, USA: McGraw-Hill, 2008. 320 p.
Material de apoio
R. Bianconi, Como ler e estudar matemática?
Fernando Q. Gouvêa e Shai Simonson, How to Read Mathematics (uma tradução "rápida e grosseira", segundo o tradutor, aqui).
Atendimento
A definir
Avaliação
x provas.
As avaliações são individuais, presenciais e sem consulta.
Os critérios de avaliação também incluem
Apresentação clara, legível, discursiva, uniforme, objetiva das soluções dos problemas.
Atendimento às normas de correção ortográfica e gramatical.
Observância às orientações específicas da atividade quando for o caso.
Instruções para as provas
Podem usar lápis (legível) ou caneta (não vermelha).
Podem responder às questões em qualquer ordem.
Podem usar parte da folha de resposta como rascunho, identificando-a no topo da página com a palavra Rascunho.
Podem entregar a prova a qualquer momento, desde que assinem a lista de presença.
Devem trazer um documento com foto atual.
Devem deixar as mochilas no chão, com o celular dentro (desligado ou silenciado). É proibido o uso de eletrônicos (celular, calculadoras, smartwatches, etc).
Devem entregar a folha de questões juntamente com a folha de respostas.
Devem deixar sobre a carteira somente lápis, caneta, borracha, documento e garrafa d'água. Qualquer outro objeto deve ser guardado.
Idas ao banheiro apenas mediante a entrega definitiva da prova.
Todo aluno poderá, eventualmente e a critério do professor, ser arguido oralmente sobre as soluções apresentadas na prova e essa arguição será parte da avaliação.
O não cumprimento das instruções implica anulação da prova.
Na ocorrência de fraude, o aluno será reprovado.
Recuperação
Tem direito ao exame recuperação, o qual engloba todo o conteúdo da disciplina, aqueles que foram aprovado com D ou reprovado com F e obtiveram frequência mínima. O resultado do exame é um conceito que compõe com o conceito final M obtido na avaliação regular da disciplina como segue:
O aluno deve manifestar interesse em fazer a recuperação de acordo com as instruções que serão enviadas pelo siga em momento apropriado durante a disciplina.
Substitutiva
Para os casos previstos em resolução mediante comprovação.