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)

784 - Maze Exploration

10305 - Ordering Tasks

10099 - The Tourist Guide

762 - We Ship Cheap

10004 - Bicoloring

10067 - Playing with Wheels

523 - Minimum Transport Cost

532 - Dungeon Master

10034 - Freckles

 

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.