CI065 - Algoritmos e Teoria dos Grafos

Segundo semestre de 2006

sala: PC02

4a e 6a 15:30

gabarito da P3

Sumário: Conteúdo -- Bibliografia -- Avaliação -- Notas de aula e Listas de exercícios -- Programa -- Calendário -- Notas -- Atendimento -- 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

Introduction to Algorithms, Cormen, Leiserson, Rivest e Stein (Capítulos 22, 23 e 24). (Biblioteca)

Bibliografia complementar:

Algorithms in C, R. Sedgewick. (Capítulos 29 --- 34). (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 que perder alguma(s) avaliação(ões) deve entrar em contato para agendar 2a chamada desde que esteja dentro do 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 da semana
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, algoritmo p/ calcular distância
notas 5	lista 5	Correção da prova. Circuito.
notas 6	lista 6	Dijkstra, Bellman-Ford
notas 7	lista 7	Grafos conexos e biconexos
notas 8	lista 7	Conexidade
notas 9	lista 8	construção de grafos k-conexos *correção* numa definição
notas 10	lista 9	gabarito da 2a prova, árvores, florestas
notas 11	lista 10	árvore geradoras mínimas, "union-find"
notas 12	lista 11	emparelhamentos
notas 13	lista 12	Algoritmo de Edmonds

Calendário

31/07 - Início das aulas
30/08 - Prova 1: conteúdo das aulas
07/09 - Feriado: Independência
08/09 - Feriado: Padroeira
28/09 - Prazo final para cancelamento de matrícula
11/10 - Prova 2: conteúdo das aulas
12/10 - Feriado: Padroeira (do Brasil dessa vez)
02/11 - Feriado: Finados
24/11 - Prova 3: conteúdo das aulas
30/11 - Último dia letivo e encerramento da monitoria
06/12 - Prova final todo conteúdo

 
         August 2006             September 2006            October 2006    
     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 

         October 2006            November 2006            December 2006    
     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  6  7               1  2  3  4                     1  2 
      8  9 10 11 12 13 14      5  6  7  8  9 10 11      3  4  5  6  7  8  9 
     15 16 17 18 19 20 21     12 13 14 15 16 17 18     10 11 12 13 14 15 16 
     22 23 24 25 26 27 28     19 20 21 22 23 24 25     17 18 19 20 21 22 23 
     29 30 31                 26 27 28 29 30           24 25 26 27 28 29 30 
                                                       31

Programação das aulas:

aula 01 - Grafos.
aula 02 - Grau.
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 - Caminho; distancia. 
aula 08 - Aula de exercícios.

aula 09 -- PROVA

aula 10 - Correção da prova. Circuito. 
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 - Teorema de Hall. 
aula 25 - Algoritmo Húngaro. 
aula 26 - Emparelhamentos em grafos bipartidos com pesos nas arestas. 

aula 27 - PROVA

Horário de atendimento aos alunos:

Monitor: Leonardo Boiko (lfsb01@inf.ufpr.br).
Local: sala dos professores ou sala de estudos do mestrado.

2a. 17:30--18:30
6a. 19:00--20:00

Professor
- ou em horário agendado (olhe aqui antes) previamente por email: se eu não responder o seu email num prazo razoável ele pode ter sido decaptado pelo spamassassin. Esse não será o caso se você enviá-lo pelo seu endereço da universidade ou do departamento.
NÃO ATENDO EM DIA DE PROVA.