CI065 - Algoritmos e Teoria dos Grafos

Primeiro semestre de 2005


Ementa -- Bibliografia -- Provas -- Listas -- Aulas -- Calendario -- Notas -- Atendimento

Novidades:
Gabarito da final: html, pdf

Conteúdo:

Objetivos:

Dar aos alunos noções de teoria dos grafos e apresentar o seu uso na resolução de problemas.

Carga horária: 60 Créditos: 4 Responsável: Jair.

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)
  4. Bibliografia complementar:

  5. Graph Theory: An Introductory course, B. Bollobás.
  6. Graph Theory, F. Harary.
  7. Grafos e Algoritmos Computacionais, J.L. Szwarcfiter.
  8. Grafos: Teoria, Modelos, Algoritmos, P.O. Boaventura Neto.
  9. Data Structures and Algorithms, A.V. Aho, J.E. Hopcroft, J.D. Ullman.
  10. 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

Calendário de provas

Não haverá aulas em:

Listas de exercícios


Tópicos das aulas
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