Algoritmos em grafos

BCC - 1o. Semestre de 2007

Sinopse das aulas

• Fevereiro
  1. (Aula 0) 27/2/2007 Discussão inicial sobre a disciplina. Veja informações gerais sobre esta edição [PS | PDF]. Definições básicas. Transparências

• Março
  1. (Aula 1) 2/3/2007 Definições básicas. Transparências

  2. (Aula 2) 6/3/2007 Representações de grafos em programas; matrizes de adjacência e listas de adjacência. Transparências

  3. (Aula 3) 9/3/2007 Três problemas envolvendo passeios: caminho entre dois vértices, caminho hamiltoniano entre dois vértices, trilha euleriana entre dois vértices. Transparências

  4. (Aula 4) 13/3/2007 Outros problemas computacionais envolvendo grafos: noções de complexidade computacional. Busca em profundidade. Transparências

  5. (Aula 5) 16/3/2007 Busca em profundidade. Transparências

  6. 20/3/2007 Não houve aula
  7. (Aula 6) 23/3/2007 2-aresta-conexidade, 2-conexidade. Caracterização de arestas de corte em termos de árvores de busca em profundidade. Transparências

  8. (Aula 7) 30/3/2007 Busca generalizada em grafos. Grafos dirigidos e grafos dirigidos acíclicos. Transparências

• Abril
  1. 3/4/2007 Semana Santa

  2. 6/4/2007 Semana Santa

  3. (Aula 8) 10/4/2007 Busca em profundidade em grafos dirigidos. Acessibilidade. Transparências

  4. (Aula 9) 13/4/2007 Aula de exercícios

  5. (Aula 10) 17/4/2007 Prova 1

  6. (Aula 11) 20/4/2007 Acessibilidade em grafos dirigidos e o fecho transitivo de grafos dirigidos; multiplicação de matrizes booleanas; algoritmo de Warshall. Transparências

  7. (Aula 12) 24/4/2007 Ordenação topológica de DAGs. Identificação de componentes fortemente conexos (introdução). Transparências

  8. (Aula 13) 27/4/2007 Identificação de componentes fortemente conexos; algoritmo de Kosaraju. Transparências

• Maio
  1. 1/5/2007 Feriado

  2. 4/5/2007 Semana de break

  3. (Aula 14) 8/5/2007 Árvores geradoras mínimas. Transparências

  4. 11/5/2007 Não houve aula (Papa em São Paulo)

  5. (Aula 15) 15/5/2007 Árvores geradoras mínimas. O algoritmo de Prim. Transparências

  6. (Aula 16) 18/5/2007 Árvores geradoras mínimas. O algoritmo de Kruskal. Transparências

  7. (Aula 17) 22/5/2007 Caminhos mínimos. O algoritmo de Dijkstra. Transparências

  8. (Aula 18) 25/5/2007 Caminhos mínimos. O algoritmo de Floyd. Transparências

  9. (Aula 19) 29/5/2007 Fluxos em redes. O teorema do fluxo máximo e corte mínimo. Transparências

• Junho
  1. (Aula 20) 1/6/2007 Fluxos em redes. O teorema do fluxo máximo e corte mínimo, redes residuais, implementação, critério de Edmonds-Karp. Transparências

  2. 5/6/2007 Semana de break

  3. 8/6/2007 Semana de break

  4. (Aula 21) 12/6/2007 Teorema de Hall. Prova baseada no teorema do fluxo máximo e corte mínimo.

  5. (Aula 22) 15/6/2007 Teorema de König e Egerváry. Discussão de exercícios, em preparação para a Prova 2

  6. (Aula 23) 19/6/2007 Prova 2

  7. (Aula 24) 22/6/2007 Planaridade de grafos

  8. (Aula 25) 26/6/2007 Prova 3

  9. (Aula 26) 29/6/2007 Algoritmos de planaridade (profa. Cristina Gomes Fernandes)

Calendário

   February 2007              March 2007               April 2007     
Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa 
             1  2  3                  1  2  3      1  2  3  4  5  6  7 
 4  5  6  7  8  9 10      4  5  6  7  8  9 10      8  9 10 11 12 13 14 
11 12 13 14 15 16 17     11 12 13 14 15 16 17     15 16 17 18 19 20 21 
18 19 20 21 22 23 24     18 19 20 21 22 23 24     22 23 24 25 26 27 28 
25 26 27 28              25 26 27 28 29 30 31     29 30

      May 2007                June 2007          
Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa     
       1  2  3  4  5                     1  2     
 6  7  8  9 10 11 12      3  4  5  6  7  8  9     
13 14 15 16 17 18 19     10 11 12 13 14 15 16     
20 21 22 23 24 25 26     17 18 19 20 21 22 23     
27 28 29 30 31           24 25 26 27 28 29 30    

Last modified: Tue Jun 19 20:03:49 BRT 2007