Algoritmos
em Grafos - TCC-00.284
Primeiro Período de 2022
Prof. Fábio Protti - fabio@ic.uff.br, fabioprotti@id.uff.br
Horário
Segundas e quartas,
das 11:00 às 13:00
Programa da disciplina
·
Conceitos
básicos em grafos e digrafos.
·
Busca
em profundidade em grafos e digrafos. Aplicações (p.ex., ordenação topológica).
·
Busca
em largura em grafos. Aplicações.
·
Algoritmo
de Dijkstra para caminhos mínimos em digrafos.
·
Algoritmo
de Floyd-Warshall para caminhos mínimos entre todos os pares de vértices de um
digrafo.
·
Algoritmos
de Kruskal e Prim para determinação de árvores geradoras mínimas.
·
Fluxos
em redes.
Estrutura do Curso
·
Aulas
presenciais: exposição de conteúdo e resolução de dúvidas.
·
Atividades
assíncronas: leituras, exercícios, vídeos, problemas para implementar.
·
Postagem
de material será feita na plataforma Classroom.
Avaliação
·
Média final = (2*P1
+ 2*P2 + T) / 5, onde T é a média dos trabalhos de implementação.
·
Os trabalhos de implementação
serão feitos no ambiente Beecrowd.
Datas
·
P1: 16/05
·
P2: 11/07
·
VS: 18/07
·
VR: a definir
·
Datas dos trabalhos: a
definir
Exemplos de problemas para
implementar (site http://onlinejudge.org)
Bibliografia
1.
Jayme
L. Szwarcfiter. Grafos e Algoritmos
Computacionais. Campus, Rio de Janeiro, 1986.
2.
Alan Gibbons. Algorithmic
Graph Theory. Cambridge
University Press, 1985.
3.
T.
H. Cormen e outros. Algoritmos
(tradução da 2a. Edição Americana). Campus, RJ, 2002.
4.
Jayme
L. Szwarcfiter. Teoria Computacional
de Grafos: Os Algoritmos. Elsevier,
2018.