CI065 - Algoritmos e Teoria dos Grafos

Primeiro semestre de 2007

sala: PC 04

4a e 6a 15:30

Gabarito da 1a. prova aqui
Gabarito da 2a. prova aqui
As notas estao disponiveis no link "Notas" abaixo

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 4 provas, 3 regulares e 1 prova final. A média final para aprovação é 50 porém alunos com desempenho muito superior a média (leia-se média das provas regulares pelo menos 70) são dispensados da prova final.

Média das provas regulares 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.

O aluno tem direito a 2a chamada desde que o motivo que o levou a perder a prova esteja previsto na seção V da resolução 37/97.

Notas de aula e 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.

Anotações	Exercícios	Tema
notas 1	lista 1	definições iniciais e grau
notas 2	lista 2	subgrafo, isomorfismo e estruturas de dados
notas 3	lista 3	percursos, busca em largura e em profundidade
notas 4	lista 4	caminhos e circuitos
notas 5	lista 5	caminhos minimos em grafos com pesos nas arestas
notas 6	lista 6	Grafos conexos e biconexos
notas 7	lista 7	Conexidade
notas 8	lista 8	árvores, florestas
notas 9	lista 9	árvore geradoras mínimas, "union-find"
notas 10	lista 10	emparelhamentos
notas 11	lista 11	Grafos hamiltonianos e grafos eulerianos

Calendário

26/02 - Início das aulas

30/03 - Prova 1: conteúdo das aulas 01 - 08

06/04 - Feriado Sexta-feira santa

13/04 - Prazo final para cancelamento de matrícula

21/04 - Feriado Tiradentes

01/05 - Feriado Dia do trabalho

04/05 - Prova 2: conteúdo das aulas 01 - 16

07/06 - Feriado Dia do trabalho

20/06 - Prova 3: conteúdo de todas as aulas

22/06 - 2a. chamada conteúdo da prova perdida

23/06 - Último dia letivo e encerramento da monitoria

04/07 - Prova final todo conteúdo

Programação das aulas:

aula 01 - Grafos.
aula 02 - Grau. Exercicios.
aula 03 - Subgrafos.
aula 04 - Outras noções de grafos. Isomorfismo. Representação computacional.
aula 05 - Percursos em grafos.
aula 06 - Busca em largura e Busca em profundidade. 
aula 07 - Caminhos e circuitos
aula 08 - Aula de exercícios.

aula 09 -- PROVA

aula 10 - Algoritmo para Distancia.Correção da prova. 
aula 11 - Caminhos e circuitos orientados em grafos dirigidos.
          Caminhos mínimos em grafos dirigidos com pesos nas arestas. 
aula 12 - Algoritmo de Dijkstra. 
aula 13 - Algoritmo de Bellman-Ford.
aula 14 - Grafos conexos. Grafos biconexos, blocos. 
aula 15 - Conexidade de grafos.
aula 16 - Construção de grafos $k$-conexos minimais.
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 - Algoritmo de Kruskal.
aula 23 - Emparelhamentos.
aula 24 - Emparelhamentos em grafos bipartidos.
aula 25 - Teorema de Hall. 
aula 26 - Algoritmo Húngaro. 
aula 27 - Emparelhamentos em grafos bipartidos com pesos nas arestas. 
aula 28 - Grafos Hamiltonianos.
aula 29 - Grafos Eulerianos.

aula 30 - PROVA

Horário da monitoria:

Monitor: Vagner (vagnerln at gmail . com)
Local: PET
Horario:
- Tercas: 19:30 - 20:20
- Quintas: 19:30 - 20:20
Professor: enquanto o departamento estiver em reforma agende por email