Esta disciplina possui 34 encontros planejados, dos quais 32 são Aulas e 2 são Avaliações Parciais (as alterações de 32 para 33 e 34 encontros foram aprovadas em sala pelos alunos). 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 (9 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 (8 aulas): estudaremos o problema, os algoritmos de Kruskal e Prim, a teoria subjacente e estruturas de dados para Conjuntos Disjuntos.
Caminhos Mínimos (4 aulas): estudaremos 2 versões do problema de caminhos mínimos (em grafos com pesos não-negativos e em grafos com pesos quaisquer) e soluções respectivas (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: Discussão da Corretude |
| 08 | 21/03 (Qua) | Distâncias em Grafos Não-Ponderados: Invariantes de Laço |
| 09 | 23/03 (Sex) | Detecção de Ciclos em Grafos Não-Direcionados |
| 10 | 28/03 (Qua) | Detecção de Circuitos em Digrafos: Algoritmo e Discussão |
| 30/03 (Sex) | Feriado Nacional – Paixão de Cristo | |
| 11 | 04/04 (Qua) | Detecção de Circuitos em Digrafos: Corretude |
| 12 | 06/04 (Sex) | Corretude da Detecção de Circuitos; O Problema da Ordenação Topológica |
| 13 | 11/04 (Qua) | Ordenação Topológica: um Algoritmo e Corretude |
| 14 | 13/04 (Sex) | Árvores Geradoras Mínimas: Problema, Ideias e Apreciação |
| 15 | 18/04 (Qua) | Árvores Geradoras Mínimas: Corretude de uma Estratégia |
| 16 | 20/04 (Sex) | Árvores Geradoras Mínimas: Complexidade da Estratégia Inicial |
| 17 | 25/04 (Qua) | Árvores Geradoras Mínimas: Estratégia Alternativa (Kruskal) e Implementação |
| 18 | 27/04 (Sex) | Árvores Geradoras Mínimas: Implementação de Conjuntos Disjuntos e Kruskal |
| 19 | 30/04 (Seg) | Árvores Geradoras Mínimas: Complexidade e Corretude de Kruskal (aula extra) |
| 20 | 02/05 (Qua) | Árvores Geradoras Mínimas: Estratégia Alternativa (Prim) e Implementação |
| 21 | 04/05 (Sex) | Árvores Geradoras Mínimas: Implementação e Complexidade de Prim |
| 22 | 09/05 (Qua) | Caminhos Mínimos em Grafos Ponderados (1/2) |
| 23 | 11/05 (Sex) | Caminhos Mínimos em Grafos Ponderados (2/2) |
| * | 16/05 (Qua) | Avaliação Parcial 1 |
| 24 | 18/05 (Sex) | Caminhos Mínimos com Pesos Negativos (1/2) |
| 25 | 23/05 (Qua) | Caminhos Mínimos com Pesos Negativos (2/2) |
| 26 | 25/05 (Sex) | Fluxo em Grafos (1/7) |
| 27 | 30/05 (Qua) | Fluxo em Grafos (2/7) |
| 28 | 01/06 (Sex) | Fluxo em Grafos (3/7) |
| 29 | 06/06 (Qua) | Fluxo em Grafos (4/7) |
| 30 | 08/06 (Sex) | Fluxo em Grafos (5/7) |
| 31 | 13/06 (Qua) | Fluxo em Grafos (6/7) |
| 32 | 15/06 (Sex) | Fluxo em Grafos (7/7) |
| * | 20/06 (Qua) | Avaliação Parcial 2 |
| 22/06 (Sex) | ||
| * | 27/06 (Qua) | Avaliação Final |
Para fins de registro, também é possível acessar a versão anterior do plano acima.