CI065 - Algoritmos e Teoria dos Grafos

Bibliografia básica:

1. Graph Theory, R. Diestel.
2. Graph Theory with applications, A. Bondy e U.S.S.R. Murty. Veja aqui.
3. Algorithms, R. Sedgewick. (Capítulos sobre algoritmos em grafos)

Bibliografia complementar:

4. Graph Theory: An Introductory course, B. Bollobás.
5. Graph Theory, F. Harary.
6. Grafos e Algoritmos Computacionais, J.L. Szwarcfiter.
7. Grafos: Teoria, Modelos, Algoritmos, P.O. Boaventura Neto.
8. Data Structures and Algorithms, A.V. Aho, J.E. Hopcroft, J.D. Ullman.
9. Introduction to Algorithms, Cormen, Leiserson, Rivest e Stein (Capítulos sobre algoritmos em grafos). A biblioteca tem esse livro em português.

Sistema de avaliação

• Média ponderada de duas provas com peso *** com média das tarefas domésticas com peso um dá a média final.
• Tendo 75% de freqüência, o aluno com nota maior ou igual a 70 estará aprovado.
• Tendo 75% de freqüência, o aluno com nota maior ou igual a 40 e menor do que 70 estará habilidato a fazer a prova final.
• Em qualquer outro caso o aluno estará reprovado e será indicado se houve ou não infreqüência.
• O aluno que fizer a prova final estará aprovado apenas se a média aritmética da prova final e da média final for maior ou igual a 50.

• Prova 1: 27/04
• Prova 2: 22/06
• Final : 01/07

Não haverá aulas em:

• 25/03

• 1a. Lista de exercícios (pdf)
• 2a. Lista de exercícios (pdf)
• 3a. Lista de exercícios (pdf)
• 4a. Lista de exercícios (pdf)
• 5a. Lista de exercícios (pdf)
• 6a. Lista de exercícios (pdf)
• 7a. Lista de exercícios (pdf)
• 8a. Lista de exercícios (pdf)
• 9a. Lista de exercícios (pdf)
• 10a. Lista de exercícios (pdf)
• 11a. Lista de exercícios (pdf)

Aula 01 - Grafos: definição, representação geométrica, nomeclatura. 
          Grau de um vértice. Vizinhança. 

Aula 02 - Subgrafos. Subgrafo induzido. No. max. de arestas em grafos sem triangulos.
          Isomorfismo. Outras noções de grafos.

Aula 03 - Representação computacional. 
          Percuros em grafos, Busca em largura e Busca em profundidade.

Aula 04 - Caminhos.

Aula 05 - Circuitos.

Aula 06 - Grafos conexos e biconexos.

Aula 07 - Conexidade e aresta-conexidade de grafos.

Aula 08 - Prova de aresta-conexidade >= conexidade. 

aula 09 - Aula de exercícios.

Aula 10 - Construção de grafos conexos com mínimo de arestas.

aula 11 - Aula de exercícios.

Aula 12 - Árvores.

Aula 13 - Prova.

Aula 14 - Correção da prova.

Aula 15 - Trilhas eulerianas.

Aula 16 - Circuitos hamiltonianos.

Aula 17 - Emparelhamentos: Teorema de Berge.

Aula 18 - Emparelhamentos: Teorema de Hall.

Aula 19 - Emparelhamentos: Metodo Hungaro.

Aula 20 - Caminhos mínimos: Dijkstra.

Aula 21 - Caminhos mínimos: Floyd-Warshall.

Aula 22 - Aula de exercícios.

Aula 23 - Árvore geradora mínima: Prim.

Aula 24 - Árvore geradora mínima: Kruskal.

Aula 25 - Union-Find com vetor e lista-ligada

Aula 26 - Union-Find com foresta/uniao por rank/compressao de caminhos

Aula 27 - Aula de exercicios.

Aula 28 - Aula de exercicios.

Aula 29 - Prova.

Aula 30 - correção da prova.


Calendario:


                             2005                              

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

                        28: inicio do 1.sem    25: Sexta-feira Santa

--------------------------------------------------------------------
       April                    May                     June        
Su Mo Tu We Th Fr Sa    Su Mo Tu We Th Fr Sa    Su Mo Tu We Th Fr Sa
                1  2     1  2  3  4  5  6  7              1  2  3  4
 3  4  5  6  7  8  9     8  9 10 11 12 13 14     5  6  7  8  9 10 11
10 11 12 13 14 15 16    15 16 17 18 19 20 21    12 13 14 15 16 17 18
17 18 19 20 21 22 23    22 23 24 25 26 27 28    19 20 21 22 23 24 25
24 25 26 27 28 29 30    29 30 31                26 27 28 29 30
                                            
21: Tiradentes          1: Dia do trabalho      25: final 1.sem 
27: prazo canc. disc.   26: Corpus Christi      30: inicio finais

--------------------------------------------------------------------










Last modified: Sun Jul  3 20:29:57 BRT 2005