MAC-328 Algoritmos em Grafos
IME - BCC
Primeiro semestre de 2014
Aulas
Para cada aula aparecem
Transparências
(usadas na aula) e
Papel
(mesmo material, em formato melhor para impressão - e talvez estudo).
17/02 - Blá geral. Definições básicas (
Transparências
/
Papel
)
20/02 - Caminhos, e sua busca com matriz de adjacência. (
Transparências
/
Papel
)
24/2 - Caminhos e cortes. (
Transparências
/
Papel
)
27/2 - Listas de adjacência. Busca em profundidade. (
Transparências
/
Papel
)
10/03 - Busca em profundidade. Procurando um ciclo. (
Transparências
/
Papel
)
13/03 - Digrafos acíclicos. Ordenação topológica. (
Transparências
/
Papel
)
17/03 - Grafos conexos e componentes. Florestas e árvores. Grafos bipartidos. (
Transparências
/
Papel
)
20/03 - Grafos bipartidos. Pontes. (
Transparências
/
Papel
)
24/03 - Pontes e articulações. (
Transparências
/
Papel
)
27/03 - Componentes fortemente conexas. (
Transparências
/
Papel
)
31/03 - Busca em largura. Caminhos mínimos. (
Transparências
/
Papel
)
03/04 - 1-potenciais e correção do algoritmo de distâncias. Caminhos de custo mínimo. (
Transparências
/
Papel
)
07/04 - Algoritmo de Dijkstra (
Transparências
/
Papel
)
10/04 - Prova 1
24/04 - Algoritmo de Dijkstra -demonstração. Caminhos mínimos em DAGs. (
Transparências
/
Papel
)
28/04 - Custos negativos. Algoritmo de Bellman-Ford, variações. (
Transparências
/
Papel
)
05/05 - Algoritmo de Floyd-Warshal (
Transparências
/
Papel
)
08/05 - Árvores geradoras, ciclos e cortes fundamentais. Árvore de custo mínimo, caracterização. Algoritmo de Prim. (
Transparências
/
Papel
)
15/05 - Algoritmo de Kruskal. Implementações. (
Transparências
/
Papel
)
19/05 - Fluxos em redes. (
Transparências
/
Papel
)
22/05 - Fluxos em redes: método do caminho de aumento, Teorema FMCM. (
Transparências
/
Papel
)
26/05 - Fluxos em redes: implementação do algoritmo de Ford e Fulkerson. (
Transparências
/
Papel
)