CI065 - Plano de Aula

CI065 - Algoritmos e Teoria dos Grafos Segundo semestre de 2002 Ementa -- Bibliografia -- Provas -- Listas -- Aulas -- Frequência -- Notas -- Atendimento

Ementa:

Introdução à Teoria dos Grafos

Noções básicas.
Emparelhamento.
Conexidade.
Coloração.

Algoritmos em Grafos

Representação de grafos.
Percursos em grafos.
Caminho mínimo.
Árvore geradora mínima.

Objetivos:

Dar aos alunos noções de teoria dos grafos e apresentar o seu uso na resolução de problemas.

Carga horária: 60 horas.

Créditos: 4

Responsável: Prof. Jair

Bibliografia básica:

Graph Theory with applications, Bondy e Murty.

Introduction to Algorithms, Cormen, Leiserson, Rivest (Capítulos sobre algoritmos em grafos)

Graph Theory, Diestel.

Bibliografia complementar:

Algorithms in C++, R. Sedgewick.
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.
Combinatorics for Computer Scientists, D. Breslauer, D.B. Dubhashi

Sistema de avaliação

Média=(2xP1 + 2xP2 + (Média das listas))/5.

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 menor do que 70 e maior que 40 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: 19/11/2002, as 15h30min, no salão de provas

Prova 2: 11/03/2003, as 15h30min, na sala de aulas

Final : 01/04/2003, as 15h30min, na sala de aulas

Exercícios:

1a. lista de exercícios para entregar.

2a. lista de exercícios para entregar. Entrega 28/02 - cada exercício vale 0 ou 0,25 pontos. Entregue quantos exercícios conseguir fazer. A nota será somada a nota de P1.

Tópicos das aulas



Aula 1 (15/10) - Nocões básicas: Definição de grafo, Representação geométrica.
Aula 2 (17/10) - Grau de um vértice, Subgrafos.

Aula 3 (22/10) - Subgrafo induzido, Isomorfismo.

Aula 4 (24/10) - Caminhos, Circuitos, Grafos conexos, Árvores. 1a. Lista de exercícios: ps.

Aula x (29/10) - NÃO HAVERÁ AULA. (evinci)

Aula x (31/10) - NÃO HAVERÁ AULA. (evinci)

Aula 5 (05/11) - Árvores e Florestas.

Aula 6 (07/11) - Grafos bipartidos e Grafos eulerianos.

Aula 7 (12/11) - Grafos eulerianos e Grafos hamiltonianos.

Aula 8  (14/11) - Grafos hamiltonianos e exercícios. 2a. Lista de exercícios: ps.

Aula 9  (19/11) - PROVA. Notas.

Aula 10 (21/11) - Correção da prova.

Aula 11 (26/11) - Grafos hamiltonianos-Teorema de Dirac; Conexidade.

Aula 12 (29/11) - Conexidade.

Aula 13 (03/12) - Aresta-conexidade. Grafos 2-conexos.

Aula 14 (05/12) - Aula de exercícios.

Aula 15 (10/12) - Grafos 2-conexos.

Aula 16 (12/12) - Construção de uma rede de comunicação confiável.


2003


Aula 17 (21/01) - Grafos dirigidos. Grafos com pesos nas arestas. Matriz de adjacências e Lista de adjacências. 

Aula 18 (23/01) - Percusos em grafos: Busca em largura.

Aula 19 (28/01) - Busca em largura - corretude.

Aula 20 (30/01) - Busca em profundidade.

Aula 21 (04/02) - Componentes fortemente conexas.


Material / lista para a 5 aulas acima. Precisa de uns ajustes na notação do material.


Aula 22 (06/02) - Árvore geradora mínima. Algoritmos de Kruskal e Prim.

Aula 23 (11/02) - Caminho mínimo. Algoritmo de Dijkstra.

Aula 24 (13/02) - Caminho mínimo. Algoritmo de Bellman-Ford.

Aula 25 (18/02) - Emparelhamento.

Aula 26 (20/02) - Emparelhamento: Teorema de Hall.

Aula 27 (25/02) - Emparelhamento: Método Hungaro. última lista 

Aula 28 (27/02) - POSSIVELMENTE NÃO HAVERÁ AULA.

Aula xx (04/03) - NÃO HAVERÁ AULA. (Carnaval)

Aula 29 (06/03) - Aula de exercícios. Aplicações de grafos em complexidade de algoritmos.

Aula 30 (11/03) - PROVA. Notas.

Aula 31 (13/03) - Correção da prova.

         October 2002            November 2002            December 2002    
     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 

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