Teoria dos Grafos

COS242 - 2023/2



Retirado do Wikipedia

Professores
Monitores
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 14/8 Logística e regras do jogo.
Objetivo, definindo grafos, exemplos, e problemas reais
aula_0.pdf
aula_1.pdf
Aula 0
Aula 1
Livro texto
2 16/8 Definições importantes, algumas propriedades, algumas classes de grafos aula_2.pdf Aula 2 Saiu lista 1
3 21/8 Representando grafos, matriz e lista, operações básicas, tempos de acesso aula_3.pdf Aula 3 Fazer lista 1
4 23/8 Explorando grafos, algoritmo genérico, BFS, camadas, distâncias, árvore geradora, caminho mínimo aula_4.pdf Aula 4 Entregar lista 1
5 28/8 Implementando a BFS, DFS e suas implementações, complexidade aula_5.pdf Aula 5 Saiu TP 1
6 30/8 Crescimento de funções, notação O e Omega, classes de funções importantes, tempo de execução aula_O.pdf Fazer lista 2, começar TP 1
7 4/9 Componentes conexos, grafos direcionados, busca em grafos direcionados, grafos fortemente conexos aula_6.pdf Aula 6 Fazer lista 2, começar TP 1
8 6/9 DAG, execução de tarefas, ordenação topológica, algoritmo eficiente aula_7.pdf Aula 7 Entregar lista 2
- 11/9 Não teremos aula: Prof. Fábio participando da 1ª Escola Brasileira de Combinatória, Prof. Daniel trabalhando com grupo de pesquisa Indy no EPFL Saiu lista 3, fazer TP 1
9 13/9 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
10 18/9 Corretude de Dijkstra, fila de prioridades, heap binário, Dijkstra eficiente, tempos de execução aula_9.pdf Aula 9 Fazer TP 1
11 20/9 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 Terminar TP 1
12 25/9 Projetando redes, MST, algoritmos de Prim e Kruskal, propriedades do corte e do ciclo aula_11.pdf Aula 11 Saiu lista 4
13 27/9 Apresentação do TP1 (sob demanda). Discussão, dúvidas, e perguntas visando a P1. Tragam suas dúvidas! Entregar TP 1
14 2/10 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.