Teoria dos Grafos

COS242 - 2011/2



Retirado do Wikipedia

Professores
Monitor
Local / Horário
Lista de email
Página atualizada em: 26-March-13


Programação das aulas

Aula Data Comentário Slides Tarefa
1 8/08 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 10/08 Mais problemas reais, definições importantes, algumas propriedades aula_2.pdf Saiu lista 1. Arrumar livro texto.
3 15/08 Representando grafos, matriz e lista, tempo de acesso aula_3.pdf Terminar lista 1. Arrumar livro texto.
4 17/08 Introdução ao problema de busca em grafos, algoritmos genéricos de busca Entregar lista 1
5 22/08 Busca em grafos, BFS (Busca em Largura), árvore geradora, caminhos mínimos aula_5.pdf Saiu lista 2
6 24/08 Implementação, complexidade, BFS e DFS (Busca em Profundidade), componentes conexas aula_6.pdf Saiu trabalho parte 1. Fazer lista 2
7 29/08 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 Começar trabalho parte 1. Terminar lista 2
8 31/08 Grafos direcionados, busca em grafos direcionados, DAG, ordenação topológica aula_8.pdf Entregar lista 2. Fazer trabalho parte 1
9 5/09 Grafos com pesos, distâncias, algoritmo de Dijkstra. aula_9.pdf Fazer lista 3
- 7/09 Feriado nacional: Dia da Independência do Brasil. Fazer lista 3. Continuar trabalho!
10 12/09 Dijkstra, análise de corretude, implementação com heap, complexidade aula_9.pdf Fazer lista 3
11 14/09 MST (Árvore Geradora Mínima), algoritmos de Prim e Kruskal. aula_11.pdf Entregar lista 3. Continuar trabalho.
12 19/09 Propriedades da MST (corte e ciclo), corretude dos algoritmos de Prim e Kruskal, algoritmos gulosos. aula_11.pdf Terminar trabalho.
13 21/09 Entrega e apresentação dos trabalhos práticos. Cada grupo terá 10min para expor oralmente seu trabalho (tragam seus slides também em PDF). Ver detalhes da avaliação no email enviado para a lista. Entregar trabalho. Saiu lista 4
14 26/09 Algoritmos gulosos, princípio e exemplos. Discussão para a prova (tragam suas dúvidas). aula_14.pdf Fazer lista 4.
15 28/09 Primeira prova. Início às 8h pontualmente. Sala a ser determinada. Refazer todas as listas para se preparar para a prova. Entregar lista 4. Saiu parte 2 do trabalho.
16 3/10 [Aula opcional, presença não obrigatória] Pontes de Königsberg, ciclo Euleriano, ciclo Hamiltoniano, e "Quem foi Turing?" aula_16.pdf Fazer lista 5 (resumo de trabalhos da JIC). Começar trabalho parte 2.
- 5/10 Não teremos aula. Semana da Jornada de Iniciação Científica (JIC) da UFRJ. Fazer lista 5 (resumo de trabalhos da JIC). Começar trabalho parte 2.
- 10/10 Não teremos aula. Professor participando de um Workshop na área de Redes de Computadores. Ver aula de reposição dia 13/10. Entregar resumos da JIC. Fazer trabalho parte 2.
- 12/10 Feriado nacional: Dia de Nossa Senhora Aparecida, padroeira do Brasil. Fazer trabalho parte 2.
17 13/10 [Aula de reposição: 15h, sala H304] Coloração em grafos, número cromático, algoritmo guloso, coloraçao de mapas aula_17.pdf Fazer trabalho parte 2.
18 17/10 Clusterização de objetos, métricas, algoritmo guloso e variações aula_18.pdf Saiu lista 6. Saiu datasets.
19 19/10 Escalonando tarefas no tempo com pesos, análise da solução ótima, algoritmo recursivo, iterativo, programação dinâmica aula_19.pdf Fazer lista 6. Terminar trabalho.
20 24/10 Problema da soma do subconjunto (subset sum), programação dinâmica, problema da mochila. aula_20.pdf Fazer lista 6. Terminar trabalho.
21 26/10 Discussão e vista da primeira prova. Trabalho adiado. Fazer lista 6.
22 31/10 Entrega e apresentação do trabalho prático parte II. Cada grupo terá 10m para expor oralmente seu trabalho (tragam seus slides também em PDF). Ver detalhes da avaliação no email enviado para a lista. Entregar trabalho. Entregar lista 6
- 2/11 Feriado nacional: Dia de Finados. Saiu lista 7
23 7/11 Grafos com pesos negativos, caminho mais curto entre todos os pares, algortimo de Floyd-Warshall, programação dinâmica. aula_23.pdf Fazer lista 7
24 9/11 Caminho mínimo em grafos com pesos negativos, algoritmo de Bellman-Ford, programação dinâmica, algoritmo distribuído. aula_24.pdf Saiu trabalho prático. Fazer lista 7.
- 14/11 Enforcado pelo Feriado Nacional: Dia da Proclamação da República do Brasil Terminar lista 7
25 16/11 Redes de fluxo, problema do fluxo máximo, problema do corte mínimo, dualidade. aula_25.pdf Entregar lista 7.
26 21/11 Algoritmo de Ford-Fulkerson, análise, melhorias. aula_26.pdf Saiu lista 8.
27 23/11 Aplicação de fluxo máximo e redução. Emparelhamento perfeito, caminho distintos, etc. aula_27.pdf Fazer lista 8.
28 28/11 Mais aplicação de fluxo máximo e redução. aula_27.pdf Fazer lista 8 e trabalho prático.
29 30/11 Resumo da ópera: apanhado final, futuro em redes, discussão, dúvidas das listas aula_29.pdf Terminar lista 8. Finalizar trabalho
30 5/12 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.
31 7/12 Segunda prova. Início às 8h pontualmente. Sala a ser determinada. Refazer todas as listas para se preparar para a prova, dando maior ênfase às listas pós-P1. Entregar lista 8.
32 14/12 Prova final. Início às 8h 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



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