CI065 - Algoritmos e Teoria dos Grafos

Segundo semestre de 2007

sala:

PH11 - 4ª e 6ª 15:30-17:30

Sumário: Conteúdo -- Bibliografia -- Avaliação -- Listas de exercícios -- Programa -- Calendário -- Notas -- Monitoria -- provas de outros semestres

Conteúdo:

Noções Básicas de Teoria dos Grafos. Definições, exemplos, e aplicações.
Representação e Implementação.
Caminhos e Percursos.
Conectividade.
Árvores.
Emparelhamento.
Caminho mínimo, Árvore geradora mínima, emparelhamento mínimo.
Coloração.

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

Pré-requisito:	CI057 - Algoritmos e Estruturas de Dados III (obrigatório)
	CI237 - Matemática Discreta (fortemente recomendado)

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

Bibliografia básica:

Graph Theory, R. Diestel. (Capítulo 1)

Há um link para livro em pdf

aqui

Graph Theory with applications, A. Bondy e U.S.S.R. Murty. (Capítulos 1 --- 6)

aqui

Algorithms in C, R. Sedgewick. (Capítulos 29 --- 34). (Biblioteca)

Bibliografia complementar:

Introduction to Algorithms, Cormen, Leiserson, Rivest e Stein (Capítulos 22, 23 e 24). (Biblioteca)
Graph Theory, F. Harary. (Biblioteca)
Grafos e Algoritmos Computacionais, J.L. Szwarcfiter. (Biblioteca)
Grafos: Teoria, Modelos, Algoritmos, P.O. Boaventura Neto. (Biblioteca)
Data Structures and Algorithms, A.V. Aho, J.E. Hopcroft, J.D. Ullman. (Biblioteca)

Avaliação

São 3 provas regulares com conteúdo cumulativo mais uma prova final sobre toda a matéria.

A média ponderada das provas regulares com pesos 1, 1 e 2 dá a média parcial.
Tendo 75% de freqüência, o aluno com média parcial maior ou igual a 70 estará aprovado.
Tendo 75% de freqüência, o aluno com média parcial maior ou igual a 40 e menor do que 70 estará habilitado a fazer a prova final. A média final é a média aritmética da média parcial com a nota da prova final, o aluno com média final maior ou igual a 50 estará aprovado.
Em qualquer outro caso o aluno estará reprovado e será indicado se houve ou não freqüência mínima.

Listas de exercícios

As listas não são obrigatórias e não valem nota, porém você pode enviar algumas de suas soluções para serem corrigidas. Para ter um retorno até a data da prova recomendo que entregue com pelo menos 15 dias de antecedência.

Exercícios	Tema
lista 1	definições iniciais e grau
lista 2	subgrafos, grafos bipartidos, isomorfismo
lista 3	representação computacional
lista 4	percurso
lista 5	caminhos e circuitos
lista 6	caminhos mínimos algoritmo de dijkstra
lista 7	caminhos mínimos algoritmo de bellman-ford
lista 8	grafos conexos
lista 9	grafos biconexos
lista 10	árvores
lista 11	árvores geradoras de custo mínimo
lista 12	emparelhamento, emparelhamento em grafos bipartidos, algoritmo de Edmonds.

Calendário

30/07 - Início das aulas
29/08 - Prova 1
07/09 - Feriado
08/09 - Feriado
21/09 - Prazo final para cancelamento de matrícula em disciplinas semetrais
17/10 - Prova 2
12/10 - Feriado
13/10 - Feriado
02/11 - Feriado
23/11 - Prova 3
01/12 - Último dia letivo e encerramento da monitoria
12/12 - Prova final todo conteúdo

Programação das aulas:

aula 01 - Grafos.  
aula 02 - Grau. 
aula 03 - Subgrafos.
aula 04 - Grafos bipartidos. Corte. Isomorfismo. 
aula 05 - Representação computacional.
aula 06 - Percursos em grafos. Busca em largura e Busca em profundidade. 
aula 07 - Análise do algoritmo de percurso.
aula 08 - Aula de exercícios.

aula 09 -- PROVA

aula 10 - Correção da prova. 
aula 11 - Caminhos e circuitos. 
aula 12 - Caminhos e circuitos orientados em grafos dirigidos. Caminhos mínimos em grafos dirigidos com pesos nas arestas.  função de relaxação.
aula 13 - Algoritmo de Dijkstra. 
aula 14 - Algoritmo de Bellman-Ford.
aula 15 - Grafos conexos. Grafos biconexos.
aula 16 - Algoritmo para determinar articulações.
aula 17 - Aula de exercícios.

aula 18 - PROVA


aula 19 - Correção da prova.
aula 20 - Árvores e Florestas. 
aula 21 - Árvores geradoras de custo mínimo.  Algoritmo de Prim. 
aula 22 - Emparelhamentos.
aula 23 - Emparelhamentos em grafos bipartidos.
aula 24 - Teorema de Hall. 
aula 25 - Algoritmo de Edmonds. 
aula 26 - Emparelhamentos em grafos bipartidos com pesos nas arestas. 
aula 27 - Grafos Hamiltonianos.
aula 28 - Grafos Eulerianos.
aula 29 - Aula de exercícios. 

aula 30 - PROVA