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