CI065 - Plano de Aula

CI065 - Algoritmos e Teoria dos Grafos Segundo semestre de 2002 Ementa -- Bibliografia -- Provas -- Listas -- Aulas -- Frequ�ncia -- Notas -- Atendimento

Ementa:

Introdu��o � Teoria dos Grafos

No��es b�sicas.
Emparelhamento.
Conexidade.
Colora��o.

Algoritmos em Grafos

Representa��o de grafos.
Percursos em grafos.
Caminho m�nimo.
�rvore geradora m�nima.

Objetivos:

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

Carga hor�ria: 60 horas.

Cr�ditos: 4

Respons�vel: Prof. Jair

Bibliografia b�sica:

Graph Theory with applications, Bondy e Murty.

Introduction to Algorithms, Cormen, Leiserson, Rivest (Cap�tulos sobre algoritmos em grafos)

Graph Theory, Diestel.

Bibliografia complementar:

Algorithms in C++, R. Sedgewick.
Graph Theory: An Introductory course, B. Bollob�s.
Graph Theory, F. Harary.
Grafos e Algoritmos Computacionais, J.L. Szwarcfiter.
Grafos: Teoria, Modelos, Algoritmos, P.O. Boaventura Neto.
Data Structures and Algorithms, A.V. Aho, J.E. Hopcroft, J.D. Ullman.
Combinatorics for Computer Scientists, D. Breslauer, D.B. Dubhashi

Sistema de avalia��o

M�dia=(2xP1 + 2xP2 + (M�dia das listas))/5.

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 menor do que 70 e maior que 40 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.

Calend�rio de provas

Prova 1: 19/11/2002, as 15h30min, no sal�o de provas

Prova 2: 11/03/2003, as 15h30min, na sala de aulas

Final : 01/04/2003, as 15h30min, na sala de aulas

Exerc�cios:

1a. lista de exerc�cios para entregar.

2a. lista de exerc�cios para entregar. Entrega 28/02 - cada exerc�cio vale 0 ou 0,25 pontos. Entregue quantos exerc�cios conseguir fazer. A nota ser� somada a nota de P1.

T�picos das aulas



Aula 1 (15/10) - Noc�es b�sicas: Defini��o de grafo, Representa��o geom�trica.
Aula 2 (17/10) - Grau de um v�rtice, Subgrafos.

Aula 3 (22/10) - Subgrafo induzido, Isomorfismo.

Aula 4 (24/10) - Caminhos, Circuitos, Grafos conexos, �rvores. 1a. Lista de exerc�cios: ps.

Aula x (29/10) - N�O HAVER� AULA. (evinci)

Aula x (31/10) - N�O HAVER� AULA. (evinci)

Aula 5 (05/11) - �rvores e Florestas.

Aula 6 (07/11) - Grafos bipartidos e Grafos eulerianos.

Aula 7 (12/11) - Grafos eulerianos e Grafos hamiltonianos.

Aula 8  (14/11) - Grafos hamiltonianos e exerc�cios. 2a. Lista de exerc�cios: ps.

Aula 9  (19/11) - PROVA. Notas.

Aula 10 (21/11) - Corre��o da prova.

Aula 11 (26/11) - Grafos hamiltonianos-Teorema de Dirac; Conexidade.

Aula 12 (29/11) - Conexidade.

Aula 13 (03/12) - Aresta-conexidade. Grafos 2-conexos.

Aula 14 (05/12) - Aula de exerc�cios.

Aula 15 (10/12) - Grafos 2-conexos.

Aula 16 (12/12) - Constru��o de uma rede de comunica��o confi�vel.


2003


Aula 17 (21/01) - Grafos dirigidos. Grafos com pesos nas arestas. Matriz de adjac�ncias e Lista de adjac�ncias. 

Aula 18 (23/01) - Percusos em grafos: Busca em largura.

Aula 19 (28/01) - Busca em largura - corretude.

Aula 20 (30/01) - Busca em profundidade.

Aula 21 (04/02) - Componentes fortemente conexas.


Material / lista para a 5 aulas acima. Precisa de uns ajustes na nota��o do material.


Aula 22 (06/02) - �rvore geradora m�nima. Algoritmos de Kruskal e Prim.

Aula 23 (11/02) - Caminho m�nimo. Algoritmo de Dijkstra.

Aula 24 (13/02) - Caminho m�nimo. Algoritmo de Bellman-Ford.

Aula 25 (18/02) - Emparelhamento.

Aula 26 (20/02) - Emparelhamento: Teorema de Hall.

Aula 27 (25/02) - Emparelhamento: M�todo Hungaro. �ltima lista 

Aula 28 (27/02) - POSSIVELMENTE N�O HAVER� AULA.

Aula xx (04/03) - N�O HAVER� AULA. (Carnaval)

Aula 29 (06/03) - Aula de exerc�cios. Aplica��es de grafos em complexidade de algoritmos.

Aula 30 (11/03) - PROVA. Notas.

Aula 31 (13/03) - Corre��o da prova.

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

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