Esta é uma disciplina de 2 encontros semanais (4 créditos), e portanto ela possui 2*16 = 32 encontros planejados, dos quais 30 são Aulas e 2 são Avaliações Parciais. Adicionalmente, poderá ser realizada também uma Avaliação Final. Na tabela a seguir estão as datas e descrições de cada encontro.
O conteúdo que veremos pode ser dividido em 5 partes:
Introdução (4 aulas): introdução à disciplina, a grafos e seus algoritmos, e às representações de grafos em algoritmos.
Percursos e Aplicações (8 aulas): motivados por 3 problemas (computar distâncias, ciclos e ordenações topológicas), estudaremos diferentes maneiras de percorrer um grafo, e em particular os percursos em Largura e em Profundidade.
Árvores Geradoras Mínimas (5 aulas): estudaremos o problema, os algoritmos de Kruskal e Prim, a teoria subjacente e estruturas de dados para Conjuntos Disjuntos.
Caminhos Mínimos (6 aulas): estudaremos 3 versões do problema de caminhos mínimos (em grafos com pesos não-negativos, em grafos com pesos negativos e em DAGs) e soluções respectivas, incluindo os algoritmos de Dijkstra e Bellman-Ford.
Fluxo em Grafos (7 aulas): estudaremos o problema de fluxo máximo, dois algoritmos polinomiais para ele (Edmonds-Karp e Push-Relabel) e a teoria subjacente, incluindo a relação com cortes em grafos.
| Aula | Data | Descrição |
|---|---|---|
| 01 | 23/02 (Sex) | Introdução à Disciplina |
| 02 | 28/02 (Qua) | Introdução a Grafos e seus Algoritmos |
| 03 | 02/03 (Sex) | Representações de Grafos: Problema, Ideias e Apreciação |
| 04 | 07/03 (Qua) | Representações de Grafos: Alternativas, Comparação e Programação |
| 05 | 09/03 (Sex) | Distâncias em Grafos Não-Ponderados: Problema, Ideias e Apreciação |
| 06 | 14/03 (Qua) | Distâncias em Grafos Não-Ponderados: 2 Algoritmos e Discussão da Corretude |
| 07 | 16/03 (Sex) | Distâncias em Grafos Não-Ponderados: Corretude via Invariantes de Laço |
| 08 | 21/03 (Qua) | Detecção de Ciclos em Grafos Não-Direcionados e Direcionados: Introdução |
| 09 | 23/03 (Sex) | Detecção de Circuitos em Digrafos: Algoritmo e Discussão |
| 10 | 28/03 (Qua) | Detecção de Circuitos em Digrafos: Corretude |
| 30/03 (Sex) | Feriado Nacional – Paixão de Cristo | |
| 11 | 04/04 (Qua) | Ordenação Topológica (1/2) |
| 12 | 06/04 (Sex) | Ordenação Topológica (2/2) |
| 13 | 11/04 (Qua) | Árvores Geradoras Mínimas (1/5) |
| 14 | 13/04 (Sex) | Árvores Geradoras Mínimas (2/5) |
| 15 | 18/04 (Qua) | Árvores Geradoras Mínimas (3/5) |
| 16 | 20/04 (Sex) | Árvores Geradoras Mínimas (4/5) |
| 17 | 25/04 (Qua) | Árvores Geradoras Mínimas (5/5) |
| * | 27/04 (Sex) | Avaliação Parcial 1 |
| 18 | 02/05 (Qua) | Caminhos Mínimos em Grafos Ponderados (1/3) |
| 19 | 04/05 (Sex) | Caminhos Mínimos em Grafos Ponderados (2/3) |
| 20 | 09/05 (Qua) | Caminhos Mínimos em Grafos Ponderados (3/3) |
| 21 | 11/05 (Sex) | Caminhos Mínimos com Pesos Negativos (1/2) |
| 22 | 16/05 (Qua) | Caminhos Mínimos com Pesos Negativos (2/2) |
| 23 | 18/05 (Sex) | Caminhos Mínimos em DAGs |
| 24 | 23/05 (Qua) | Fluxo em Grafos (1/7) |
| 25 | 25/05 (Sex) | Fluxo em Grafos (2/7) |
| 26 | 30/05 (Qua) | Fluxo em Grafos (3/7) |
| 27 | 01/06 (Sex) | Fluxo em Grafos (4/7) |
| 28 | 06/06 (Qua) | Fluxo em Grafos (5/7) |
| 29 | 08/06 (Sex) | Fluxo em Grafos (6/7) |
| 30 | 13/06 (Qua) | Fluxo em Grafos (7/7) |
| * | 15/06 (Sex) | Avaliação Parcial 2 |
| 20/06 (Qua) | ||
| 22/06 (Sex) | ||
| * | 27/06 (Qua) | Avaliação Final |