Teoria dos Grafos

COS242 - 2016/2



Retirado do Wikipedia

Professor
Monitor
Local / Horário
Lista de email
Programação das aulas

Primeira Aula: 5/9 (segunda)

Aula Data Comentário Slides Tarefa
1 5/09 Logística e regras do jogo. Definindo grafos, abstração para estrutura, problemas reais aula_0.pdf
aula_1.pdf
Saiu lista 1
- 7/09 Feriado Nacional: Independência do Brasil Fazer lista 1
2 12/09 Outro problema real, definições importantes, algumas propriedades aula_2.pdf Entregar lista 1
3 14/09 Representando grafos, matriz e lista, tempos de acesso aula_3.pdf Saiu lista 2
4 19/09 Explorando grafos, algoritmo genérico, BFS, árvore geradora, distâncias aula_4.pdf Fazer lista 2
5 21/09 Implementando a BFS, DFS e sua implementação, complexidade aula_5.pdf Fazer lista 2
6 26/09 Componentes conexos, grafos direcionados, busca em grafos direcionados, DAG, ordenação topológica aula_6.pdf Entregar lista 2, saiu trabalho 1
7 28/09 Grafos com pesos, comprimento, distâncias, ideia e algoritmo de Dijkstra aula_7.pdf Saiu lista 3
8 3/10 Corretude de Dijkstra, fila de prioridades, heap binário, Dijkstra eficiente, Dijkstra - o próprio, Documentário: Discipline in Thought (2000) aula_8.pdf Fazer lista 3
9 5/10 Problema do labirinto (pathfinding), busca informada, best-first search, A*
Introduction to A* no "Red Blob Games" por Amit Patel
aula_9.pdf Terminar lista 3, trabalho 1
10 10/10 Projetando redes, MST, algoritmos de Prim e Kruskal, propriedades do corte e do ciclo aula_10.pdf Entregar lista 3, saiu lista 4
- 12/10 Feriado Nacional: Dia de Nossa Senhora Aparecida (Padroeira do Brasil) Fazer lista 4, fazer trabalho 1
11 17/10 Primeira Prova. Início pontualmente às 13h.
Rever todas as listas em preparação para a prova.
Entregar lista 4
- 19/10 Não teremos aula: 7ª Semana de Integração Acadêmica da UFRJ.
Fazer lista 5: dois resumos da JIC (ver abaixo).
12 24/10 Construção de algoritmos, paradigma guloso, escalonando tarefas no tempo aula_12.pdf Entregar trabalho 1, entregar Lista 5
13 26/10 Coloração em grafos, algoritmo guloso, número cromático, teorema das 4 cores aula_13.pdf Saiu trabalho 2
14 31/10 Escalonamento de tarefas com pesos, estrutura da solução ótima, recursão, programação dinâmica aula_14.pdf Saiu lista 6, Fazer trabalho 2
- 2/11 Feriado Nacional: Dia de Finados Fazer trabalho 2
15 7/11 Problema da soma do subconjunto (subset sum), recursão, programação dinâmica, problema da mochila aula_15.pdf Fazer trabalho 2
16 9/11 Alinhamento de sequências, programação dinâmica, redução para problema em grafos aula_16.pdf Fazer lista 6
- 14/11 Enforcado por conta do Feriado Nacional: Proclamação da República do Brasil Terminar trabalho 2, lista 6
17 16/11 Entrega e apresentação do trabalho (Parte II)
Veja abaixo resultado da votação, com empate entre dois grupos!
Entregar relatório
18 21/11 Grafos com pesos negativos, caminho mais curto entre todos os pares, programação dinâmica, algortimo de Floyd-Warshall aula_18.pdf Entregar lista 6, saiu trabalho 3
19 23/11 Redes de fluxo, problema do fluxo máximo, problema do corte mínimo, dualidade aula_19.pdf Saiu lista 7
20 28/11 Fluxo máximo, algoritmo de Ford-Fulkerson, análise, melhorias aula_20.pdf Fazer trabalho 3
21 30/11 Aplicações do fluxo máximo: emparelhamento, caminhos distintos, corte mínimo, segmentação de imagens aula_21.pdf Fazer lista 7
22 5/12 Apanhado final, futuro em grafos (network science), avaliação da disciplina. aula_22.pdf Fazer lista 7 e trabalho 3
23 7/12 Segunda Prova. Início pontualmente às 13h.
Rever todas as listas desde a P1 em preparação para a prova.
Entregar lista 7
- 12/12 Não teremos aula. Fazer trabalho 3
24 14/12 Entrega e apresentação do trabalho (Parte III)
Veja abaixo resultados dos percursos dos diferentes grupos!
Entregar relatório
25 19/12 Vista e discussão da P2 Classificados para PF: refazer listas
26 21/12 Prova Final. Início pontualmente às 13h.
Refazer e rever todas as listas em preparação para a prova.


Listas de exercícios

As listas devem ser entregue em papel no início da aula na data de entrega. Não serão aceitas listas enviadas por email.



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.