Teoria dos Grafos

COS242 - 2018/2



Retirado do Wikipedia

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

Aula Data Comentário Slides Tarefa
1 6/08 Logística e regras do jogo. Definindo grafos, abstração para estrutura, problemas reais aula_0.pdf
aula_1.pdf
Saiu lista 1
2 8/08 Definições importantes, algumas propriedades, algumas classes de grafos aula_2.pdf Fazer lista 1
3 13/08 Representando grafos, matriz e lista, tempos de acesso aula_3.pdf Fazer lista 1
4 15/08 Explorando grafos, algoritmo genérico, BFS, camadas, distâncias, árvore geradora, caminho mínimo aula_4.pdf Entregar lista 1, saiu lista 2
5 20/08 Implementando a BFS, DFS e sua implementação, complexidade aula_5.pdf Fazer lista 2, saiu TP 1
6 22/08 Componentes conexos, grafos direcionados, busca em grafos direcionados, DAG, ordenação topológica aula_6.pdf Fazer lista 2, começar TP 1
7 27/08 Grafos com pesos, comprimento, distâncias, ideia e algoritmo de Dijkstra, Dijkstra - o próprio, Documentário: Discipline in Thought (2000) aula_7.pdf Entregar lista 2, saiu lista 3
8 29/08 Corretude de Dijkstra, fila de prioridades, heap binário, Dijkstra eficiente aula_8.pdf Fazer TP 1, lista 3
9 3/09 Entrega e apresentação do trabalho (Parte I).
Iremos eleger o melhor trabalho (ver resultado da votação abaixo)
Entregar TP 1
10 5/09 Problema do labirinto (pathfinding), busca informada, best-first search, A*
Introduction to A* no "Red Blob Games" por Amit Patel
aula_10.pdf Terminar lista 3
11 10/09 Projetando redes, MST, algoritmos de Prim e Kruskal, propriedades do corte e do ciclo aula_11.pdf Entregar lista 3, saiu lista 4
12 12/09 Monitoria: tragam suas dúvidas, perguntas e respostas! Fazer lista 4
13 17/09 Primeira Prova. Início pontualmente às 13h.
Rever todas as listas em preparação para a prova.
Entregar lista 4
14 19/09 Construção de algoritmos, paradigma guloso, escalonando tarefas no tempo aula_14.pdf Saiu TP 2
15 24/09 Coloração em grafos, algoritmo guloso, número cromático, teorema das 4 cores aula_15.pdf Saiu lista 5
16 26/09 Escalonamento de tarefas com pesos, estrutura da solução ótima, recursão, programação dinâmica aula_16.pdf Fazer TP 2, lista 5
17 1/10 Problema da soma do subconjunto (subset sum), recursão, programação dinâmica, problema da mochila aula_17.pdf Fazer TP 2, lista 5
18 3/10 Alinhamento de sequências, programação dinâmica, redução para problema em grafos aula_18.pdf Fazer TP 2, lista 5
19 8/10 Grafos com pesos negativos, caminho mais curto entre todos os pares, programação dinâmica, algortimo de Floyd-Warshall aula_19.pdf Fazer TP 2, lista 5
20 10/10 Entrega e apresentação do trabalho (Parte II).
Iremos eleger o melhor trabalho (ver resultado da votação abaixo)
Entregar TP 2
- 15/10 Não teremos aula. 9ª Semana de Integração Acadêmica da UFRJ. Fazer dois resumos de palestras da JIC (ver detalhes abaixo). Fazer resumos JIC
21 17/10 Aula opcional em função da 9ª Semana de Integração Acadêmica da UFRJ
Turing e von Neumann: dois gigantes da Computação
Alan Turing por Luis Menasché Schechter
aula_21.pdf Fazer resumos JIC. Saiu TP 3
- 22/10 Não teremos aula. Professor participando do Encontro Nacional de Inteligência Artificial e Computacional - ENIAC 2018. Terminar Lista 5, começar Trabalho Prático 3. Fazer lista 5
- 24/10 Não teremos aula. Professor participando do Encontro Nacional de Inteligência Artificial e Computacional - ENIAC 2018. Terminar Lista 5, começar Trabalho Prático 3. Fazer lista 5
22 29/10 Caminho mínimo em grafos com pesos negativos, algoritmo de Bellman-Ford, programação dinâmica, algoritmo distribuído aula_22.pdf Entregar resumos JIC e lista 5
23 31/10 Redes de fluxo, problema do fluxo máximo, problema do corte mínimo, dualidade aula_23.pdf Saiu lista 7, fazer TP 3
24 5/11 Fluxo máximo, algoritmo de Ford-Fulkerson, análise, melhorias aula_24.pdf Fazer TP 3
25 7/11 Aplicações do fluxo máximo: emparelhamento, caminhos distintos, corte mínimo, segmentação de imagens aula_25.pdf Fazer lista 7
26 12/11 Apanhado final, futuro em grafos (network science), avaliação da disciplina aula_26.pdf Fazer lista 7 e TP 3
- 14/11 Não teremos aula. Terminar TP 3
- 19/11 Não teremos aula. Feriado (enforcado): Dia da Consciência Negra, dia 20/11 Fazer lista 7, TP 3
27 21/11 Segunda Prova. Início pontualmente às 13h.
Rever todas as listas desde a P1 em preparação para a prova.
Entregar lista 7
28 26/11 Entrega e apresentação do trabalho (Parte III)
Veja abaixo resultados dos percursos dos diferentes grupos!
Entregar relatório
29 28/11 Vista e discussão da P2 Classificados para PF: refazer listas
30 3/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.