Teoria dos Grafos

COS242 - 2012/2



Retirado do Wikipedia
Professores
Monitores
Local / Horário
Lista de email
Página atualizada em: 26-Fevereiro-2013

Programação das aulas

Aula Data Comentário Slides Tarefa
1 15/10 Logística, regras, definição de grafos, introdução, motivação com problemas reais, formando casais aula_0.pdf
aula_1.pdf 		Procurar livro sobre algoritmos e grafos (ver referências abaixo)
2 17/10 Mais problemas reais, definições importantes, algumas propriedades aula_2.pdf
 Arrumar livro texto. Saiu lista 1.
3 22/10 Representando grafos, matriz e lista, tempo de acesso aula_3.pdf
 Terminar lista 1. Arrumar livro texto.
4 24/10 Introdução ao problema de busca em grafos, algoritmos genéricos de busca aula_4.pdf
 Entregar lista 1. Saiu lista 2.
5 29/10 Busca em grafos, BFS (Busca em Largura), árvore geradora, caminhos mínimos aula_5.pdf
6 31/10 Implementação, complexidade, BFS e DFS (Busca em Profundidade), componentes conexas aula_6.pdf
7 05/11 Classe de funções e notação O, Omega, Theta, propriedades da notação, funções usuais, tempo de execução e algoritmos aula_7.pdf
8 07/11 Grafos direcionados, busca em grafos direcionados, DAG, ordenação topológica aula_8.pdf
9 12/11 Grafos com pesos, distâncias, algoritmo de Dijkstra. aula_9.pdf
 Saiu lista 3.
10 14/11 Dijkstra, análise de corretude, implementação com heap, complexidade aula_9.pdf
- 19/11 Feriado dia 20/11: Dia da Consciência Negra.

11 21/11 Entrega e apresentação dos trabalhos práticos. Cada grupo terá 10min para expor oralmente seu trabalho (tragam seus slides também em PDF).
Entregar trabalho. Saiu lista 4.
12 26/11 MST (Árvore Geradora Mínima), algoritmos de Prim e Kruskal. aula_11.pdf Entregar lista 3.
13 28/11 Propriedades da MST (corte e ciclo), corretude dos algoritmos de Prim e Kruskal, algoritmos gulosos. aula_11.pdf
14 03/12 Primeira prova. Início às 13h pontualmente na sala de aula H304-A. Refazer todas as listas para se preparar para a prova.
Entregar lista 4.
15 05/12 Algoritmos gulosos, princípio e exemplos. aula_14.pdf
16 10/12 Clusterização de objetos, métricas, algoritmo guloso e variações aula_18.pdf Saiu lista 6.
17 12/12 Coloração em grafos, número cromático, algoritmo guloso, coloraçao de mapas aula_17.pdf
18 17/12 Escalonando tarefas no tempo com pesos, análise da solução ótima, algoritmo recursivo, iterativo, programação dinâmica aula_19.pdf
19 19/12 Entrega e apresentação individuais para os monitores da primeira parte do segundo trabalho.
Entregar trabalho 2 primeira parte.
20 07/01 Entrega e apresentação do segundo trabalho. Cada grupo terá 10m para expor oralmente seu trabalho (tragam seus slides também em PDF).
Entregar trabalho 2 segunda parte.
21 09/01 Problema da soma do subconjunto (subset sum), programação dinâmica, problema da mochila. aula_20.pdf Entregar lista 6.
22 14/01 Grafos com pesos negativos, caminho mais curto entre todos os pares, algortimo de Floyd-Warshall, programação dinâmica. aula_23.pdf
 Sairam listas 7 e 8.
23 16/01 Redes de fluxo, problema do fluxo máximo, problema do corte mínimo, dualidade. aula_25.pdf
24 21/01 Algoritmo de Ford-Fulkerson, análise, melhorias. aula_26.pdf
 Entregar lista 7.
25 23/01 Aplicação de fluxo máximo e redução. Emparelhamento perfeito, caminho distintos, etc. aula_27.pdf
26 28/01 Mais aplicação de fluxo máximo e redução. aula_27.pdf
27 30/01 Entrega e apresentação do trabalho prático parte III. Cada grupo terá 10m para expor oralmente seu trabalho (tragam seus slides também em PDF).
Entregar trabalho 3.
28 04/02 Resumo da ópera: apanhado final, futuro em redes, discussão, dúvidas das listas aula_29.pdf
29 06/02 Segunda prova. Início às 13h pontualmente na sala H304. Refazer todas as listas para se preparar para a prova, dando maior ênfase às listas pós-P1.
Entregar lista 8.
30 20/02 Vista da P2.

31 25/02 Prova final. Início às 13h pontualmente na sala H304. Refazer todas as listas para se preparar para a prova. Participar da monitoria.


Listas de exercícios
Trabalhos
Datas das provas e trabalho



Notas
Referências

As notas de aulas serão tiradas principalmente dos seguintes referências:

Você pode pesquisar pelos livros acima no acervo da UFRJ.

Leituras