CI065 - Algoritmos e Teoria dos Grafos

Primeiro semestre de 2008

4ª,6ª 15:30 sala: PA03

O exame será na PH11
soluções dos exercícios da P3

Veja aqui uma dica pra ser aprovado em grafos. Mais dicas, apesar do título serve para várias disciplinas da computação também.

Não haverá aula de ci065 na semana de 14 a 18 de abril pois estarei aqui . Na sexta feira dia 18, havera plantao do monitor no horario e local da aula.

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; Representação e Implementação; Caminhos e Percursos; Conexidade; Árvores; Emparelhamento; Caminho mínimo, Árvore geradora mínima, emparelhamento máximo.

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 with applications, A. Bondy e U.S.S.R. Murty. (Capítulos 1 --- 6)

O livro está disponível em pdf

aqui

Introduction to algorithms Udi Manber. (cap 7) biblioteca

Bibliografia complementar:

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

aqui

Algorithms in C, R. Sedgewick. (Capítulos 29 --- 34). (Biblioteca)
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.

O aluno tem direito a 2a chamada desde que o motivo que o levou a perder a prova esteja previsto no art. 106 da resolução 37/97 e desde que quem perdeu a prova cumpra as formalidades exigidas pela resolução.

Listas de exercícios

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

Exercícios	Tema
lista 1	definições iniciais
lista 2	grau
lista 3	subgrafos, grafos bipartidos, conjuntos independentes, cliques e corte
lista 4	Isomorfismo, outros grafos e representação computacional
lista 5	Percursos em grafos
lista 6	Caminhos e circuitos
lista 7	caminhos mínimos em grafos com pesos nas arestas
lista 8	Grafos conexos
lista 9	Árvores
lista 10	Árvore geradora mínima
lista 11	Emparelhamento
lista 12	em breve

Calendário

21,22/03 - Feriado: sexta-feira santa e sábado de aleluia.
28/03 - Prova 1
11/04 - Prazo final para protocolar cancelamento de disciplinas semestrais.
14-18/04 - não haverá aula, professor em congresso.
21/04 - Feriado: Tiradentes.
12-16/05 - Semana Acadêmica do Setor de Ciências Exatas.
09/05 - Prova 2.
22/05 - Feriado: Corpus Christi.
18/06 - Prova 3.
21/06 - Último dia letivo do 1o semestre de 2008.
23-28/06 - Período de estudos preparatórios para os exames finais.
30/06-05/07 - Exames finais das disciplinas de regime semestral do 1o semestre de 2008.
02/07 - Prova final.

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


       May 2008                June 2008                July 2008      
     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa 
                  1  2  3      1  2  3  4  5  6  7            1  2  3  4  5 
      4  5  6  7  8  9 10      8  9 10 11 12 13 14      6  7  8  9 10 11 12 
     11[12 13 14 15 16]17     15 16 17 18 19 20 21     13 14 15 16 17 18 19 
     18 19 20 21 22 23 24     22 23 24 25 26 27 28     20 21 22 23 24 25 26 
     25 26 27 28 29 30 31     29 30                    27 28 29 30 31

Programação das aulas: (tentativa)

aula 01 - Grafos.
aula 02 - Grau.
aula 03 - Subgrafos. Subgrafos induzidos. Conjunto independente. Clique.
aula 04 - Grafo bipartido e corte. Exercicios.
aula 05 - Isomorfismo. 
aula 06 - Representação computacional.
aula 07 - Percursos em grafos.
aula 08 - Busca em largura 
aula 09 - Busca em profundidade. 
aula 10 - Caminho; distância.
aula 11 - Circuitos.
aula 12 - Caminhos mínimos em grafos com pesos nas arestas. 
aula 13 - Algoritmo de Dijkstra. 
aula 14 - Algoritmo de Floyd-Warshall.
aula 15 - Grafos e componentes conexos. Grafos e componentes biconexos.
aula 16 - Algoritmo para determinar articulações.
aula 17 - Árvores e Florestas.
aula 18 - Árvores.
aula 19 - Árvores geradoras de custo mínimo.  Algoritmo de Prim. 
aula 20 - Algoritmo de Kruskal.
aula 21 - Emparelhamentos.
aula 22 - Emparelhamentos e coberturas.
aula 23 - Emparelhamentos em grafos bipartidos.
aula 24 - Teorema de Hall. 
aula 25 - Algoritmo de Edmonds. 
aula 26 - Grafos Eulerinos.
aula 27 - Grafos  Hamiltonianos.

Horário da monitoria:

Monitor: Leandro (lmz05 inf ufpr br)
Local: PET
Horário: 6a. 17:00 -- 19:30

Provas de semestres anteriores

Final 2006-1 gabarito

"Graph theory has long become recognized as one of the more useful mathematical subjects for the computer science student to master. The approach which is natural in computer science is the algorithmic one; our interest is not so much in existence proofs or enumeration techniques, as it is in finding efficient algorithms for solving relevant problems, or alternatively showing evidence that no such algorithms exist. Although algorithmic graph theory was started by Euler, if not earlier, its development in the last ten years has been dramatic and revolutionary." Shimon Even

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