Teoria dos Grafos

COS242 - 2021/2



Retirado do Wikipedia

Professores
Monitor
Local / Horário
Moodle

Todos devem se inscrever no Moodle da discilina. O código de acesso para auto-inscrição é codigo242.


Programação

Aula Data Comentário Slides Vídeos Tarefa
1 17/11 Logística e regras do jogo.
Objetivo, definindo grafos, exemplos, e problemas reais
aula_0.pdf
aula_1.pdf
Aula 0
Discussão

Aula 1
Discussão

Saiu lista 1
2 22/11 Definições importantes, algumas propriedades, algumas classes de grafos aula_2.pdf Aula 2
Discussão
Fazer lista 1
3 24/11 Representando grafos, matriz e lista, operações básicas, tempos de acesso aula_3.pdf Aula 3
Discussão
Fazer lista 1
4 29/11 Explorando grafos, algoritmo genérico, BFS, camadas, distâncias, árvore geradora, caminho mínimo aula_4.pdf Aula 4
Discussão
Entregar lista 1, saiu lista 2
5 1/12 Implementando a BFS, DFS e suas implementações, complexidade aula_5.pdf Aula 5
Discussão
Fazer lista 2, saiu TP 1
6 6/12 Componentes conexos, grafos direcionados, busca em grafos direcionados, grafos fortemente conexos aula_6.pdf Aula 6
Discussão
Fazer lista 2, começar TP 1
7 8/12 DAG, execução de tarefas, ordenação topológica, algoritmo eficiente aula_7.pdf Aula 7
Discussão
Entregar lista 2
8 13/12 Grafos com pesos, comprimento, distâncias, ideia e algoritmo de Dijkstra, Dijkstra - o próprio.
Documentário: Discipline in Thought (2000)
aula_8.pdf Aula 8 Saiu lista 3, fazer TP 1
9 15/12 Corretude de Dijkstra, fila de prioridades, heap binário, Dijkstra eficiente, tempos de execução aula_9.pdf Aula 9
Discussão
Fazer TP 1
10 20/12 Problema do labirinto (pathfinding), busca informada, best-first search, A*
Introduction to A* no "Red Blob Games" por Amit Patel
aula_10.pdf Aula 10
Discussão
Terminar TP 1
11 22/12 Projetando redes, MST, algoritmos de Prim e Kruskal, propriedades do corte e do ciclo aula_11.pdf Aula 11
Discussão
Entregar TP 1, saiu lista 4
- 27/12 Recesso de final de ano!
12 3/1 Discussão, dúvidas, e perguntas sobre TP 1 e restante da matéria. Tragam suas dúvidas!
Discussão
Entregar lista 3
13 5/1 Primeira Prova. Início pontualmente às 13h.
Rever todas as listas em preparação para a prova
Entregar lista 4


Listas de exercícios

As listas devem ser entregue no Moodle da disciplina, até o final do dia de entrega. Listas entregues com atraso serão penalizadas em 10% ao dia.



Trabalhos práticos

Os trabalhos práticos devem ser entregue no Moodle da disciplina, até o final do dia de entrega. Trabalhos entregues com atraso serão penalizadas em 10% ao dia.



Provas



Referências

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

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