CI065 - Algoritmos e Teoria dos Grafos

Segundo semestre de 2005

4as e 6as as 15:30 na PE7

Ementa -- Bibliografia -- Provas -- Listas -- Aulas -- Calendario -- Notas -- Atendimento

Gabarito da P3 (txt)

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.

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

Bibliografia básica:

Graph Theory, R. Diestel.
Graph Theory with applications, A. Bondy e U.S.S.R. Murty.
Algorithms, R. Sedgewick. (Capítulos sobre algoritmos em grafos)
Notas de aula não revisada.

Bibliografia complementar:

Graph Theory: An Introductory course, B. Bollobás.
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.

Sistema de avaliação

Média ponderada das provas com peso 03 com média das tarefas domésticas com peso 01 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.

Calendário de provas

Prova 1: 26/08
Prova 2: 21/10
Prova 2-2a chamada: 10/11-13:30 na sala de professores
Prova 3: 30/11
Final : 09/12

2a chamada para os que perderem a 3a prova pelos motivos previstos pelo regimento será sexta 02/12 no horário de aula.

Listas de exercícios

Datas de entrega:

07/10 - os exercícios serão passados em sala de aula - enunciados da 1a lista para entrega

16/11 - os exercícios serão passados em sala de aula - enunciados da 2a lista para entrega

Listas:

1a. Lista de exercícios (pdf)
2a. Lista de exercícios (pdf)
3a. Lista de exercícios (pdf)
4a. Lista de exercícios (pdf)
5a. Lista de exercícios (pdf)
6a. Lista de exercícios (pdf)
7a. Lista de exercícios (pdf)
8a. Lista de exercícios (pdf)
9a. Lista de exercícios (pdf)
10a. Lista de exercícios (pdf)
11a. Lista de exercícios (pdf)

Tópicos das aulas (em construção)

Aula 01 - Grafos: definição, representação geométrica, nomeclatura. 
          Grau de um vértice. Vizinhança.  

Aula 02 - Subgrafos. 

Aula 03 - Isomorfismo. Outras noções de grafos. 
          Representação computacional. 

Aula 04 - Percuros em grafos. Busca em largura e Busca em profundidade. 

Aula 05 - Aula de exercícios.

Aula 06 - Caminhos e circuitos. 
(as notas foram revisadas em 25/8 por conta de definição errada de  diâmetro na equação (21) pg 20)

Aula 07 - Caminhos e circuitos.

Aula 08 - Prova. 

Aula 09 - Grafos conexos.

Aula 10 - Grafos biconexos.

Aula 11 - Conexidade e aresta-conexidade de grafos. 
      Prova de aresta-conexidade >= conexidade. 

aula 12 - Construção de grafos conexos com mínimo de arestas.

Aula 13 - aula de exercícios. 

Aula 14 - Árvores e Florestas.

Aula 15 - Circuitos hamiltonianos e Trilhas eulerianas.

Aula 16 - Emparelhamentos e emparelhamentos em grafos bipartidos.

Aula 17 - Emparelhamentos: algoritmo húngaro.

Aula 18 - Prova.

Aula 19 - Grafos com pesos nas arestas.

Aula 20 - Recesso decretado de ultima hora pelo magnifico.

Aula 21 - Caminhos mínimos: Dijkstra e Floyd-Warshall. 

Aula 22 - Árvore geradora mínima: Prim. 
 
Aula 23 - Árvore geradora mínima: Kruskal. 

Aula 24 - Estruturas "Union find" para conjuntos disjuntos. 
          Union-Find com vetor e lista-ligada

Aula 25 - Union-Find com floresta/uniao por rank/compressao de caminhos 

Aula 26 - Aula da exercicios

Aula 27 - Aula da exercicios

Aula 28 - Prova 

Aula 29 - Correção da prova

Aula 30 - 2a chamada

Calendario:

Não haverá aulas em:

07/09 - Independencia
05,07/10 - Semana de Ensino Pesquisa e Extensao
12/10 - Padroeira
02/11 - Finados


                             2005                              

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

6: final finais         1: inicio 2.sem         7: Independencia
                                                8: Padroeira de Ctba
                                               30: prazo canc. disc.

--------------------------------------------------------------------
      October                 November                December      
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                 1  2  3
 2  3  4  5  6  7  8     6  7  8  9 10 11 12     4  5  6  7  8  9 10
 9 10 11 12 13 14 15    13 14 15 16 17 18 19    11 12 13 14 15 16 17
16 17 18 19 20 21 22    20 21 22 23 24 25 26    18 19 20 21 22 23 24
23 24 25 26 27 28 29    27 28 29 30             25 26 27 28 29 30 31
30 31                                       
 
3-7: Semana Ens&Pq&Ext  2: Finados              3: fim 2.sem
12: Padroeira Brasil    15: Procl. Republica    8-14: finais

Last modified: Tue Dec 13 17:16:02 BRST 2005