CI065 - Algoritmos e Teoria dos Grafos

Primeiro semestre de 2006

local: PD04

4a e 6a 15:30

Sumário: Programa -- Bibliografia -- Avaliação -- Listas de exercícios -- Programa -- Calendario -- Notas -- Atendimento -- provas antigas

Programa:

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
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; Pascal; C++; Java], R. Sedgewick. (Capítulos 29 --- 34)

Bibliografia complementar:

Notas de aula
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.
Introduction to Algorithms, Cormen, Leiserson, Rivest e Stein (Capítulos sobre algoritmos em grafos). A biblioteca tem esse livro em português.

Avaliação

Média ponderada das provas dá a média final.
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 maior ou igual a 40 e menor do que 70 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.

Listas de exercícios

Calendário

06/03 - Início das aulas

31/03 - Prova 1:

14/04 - Feriado: Sexta-feira santa

21/04 - Feriado: Tiradentes

10/05 - Prova 2:

24/04 - Prazo para cancelamento de matrícula

26/06 - Prova 3: conteúdo das aulas 18 a 22,25,26,27.

26/06 - Último dia letivo

27/06 - 17hs. - 2a. chamada p/ os casos cobertos pela secao V da resolução 37/97 (pag 26)
Os interessados em fazer 2a chamada devem me procurar no departamento 15 min. antes da prova.
30/06 - Exame final

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

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

Programação das aulas:

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

aula 08 -- PROVA

aula 09 - Correção da prova. Caminho; distancia. 
aula 10 - Circuito. Caminhos e circuitos orientados em grafos dirigidos.
aula 10 - Caminhos mínimos em grafos dirigidos com pesos nas arestas. Algoritmo de Dijkstra. 
aula 11 - Algoritmo de Bellman-Ford.
aula 12 - Grafos conexos. Grafos biconexos, blocos. 
aula 13 - Conexidade de grafos.
aula 14 - Construção de grafos $k$-conexos minimais.
aula 15 - Aula de exercícios.

aula 16 - PROVA

aula 17 - Correção da prova. 
aula 18 - Árvores e Florestas.
aula 19 - Árvores geradoras de custo mínimo.  Algoritmo de Prim. 
aula 20 - Algoritmo de Kruskal.
aula 21 - Representação de conjuntos disjuntos: com vetor; com listas ligadas. 
aula 22 - Representação de conjuntos disjuntos: com árvores.
aula 23 - Circuitos hamiltonianos.
aula 24 - Trilhas eulerianas.
aula 25 - Emparelhamentos.
aula 26 - Emparelhamentos em grafos bipartidos - Teorema de Hall. 
aula 27 - Algoritmo Húngaro. 
aula 28 - Emparelhamentos em grafos bipartidos com pesos nas arestas. 
aula 29 - Coloração. 

aula 30 - PROVA

Horário de atendimento aos alunos:

Monitor: Leonardo Boiko (lfsb01)
- 2a. 15:30--17:00
- 3a. 13:30--15:00
Professor:
- 5a. das 13:30 as 15:00hs
- 4a. das 17:30 as 19:00hs
- ou em horário agendado previamente por email: se eu nao 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.