Teoria dos Grafos

COS242 - 2026/2



Retirado do Wikipedia
Professor
Monitora
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 10/8 Logística e regras do jogo.
Objetivo, definindo grafos, exemplos, e problemas reais		 aula_0.pdf
aula_1.pdf 		Aula 1 Saiu lista 1
2 12/8 Definições importantes, algumas propriedades, algumas classes de grafos aula_2.pdf Aula 2 Fazer lista 1
3 17/8 Representando grafos, matriz e lista, operações básicas, tempos de acesso, tabela hash aula_3.pdf Aula 3 Fazer lista 1
4 19/8 Explorando grafos, algoritmo genérico, BFS, camadas, distâncias, árvore geradora, caminho mínimo aula_4.pdf Aula 4 Terminar lista 1
5 24/8 Implementando a BFS, DFS e suas implementações, complexidade aula_5.pdf Aula 5 Entregar lista 1, saiu lista 2
6 26/8 Componentes conexos, grafos direcionados, busca em grafos direcionados, grafos fortemente conexos aula_6.pdf Aula 6 Fazer lista 2, saiu TP 1
7 31/8 DAG, execução de tarefas, ordenação topológica, algoritmo eficiente aula_7.pdf Aula 7 Fazer lista 2
8 2/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 Fazer lista 2
- 7/9 Feriado nacional: Dia do Independência do Brasil Fazer lista 2
9 9/9 Corretude de Dijkstra, fila de prioridades, heap binário, Dijkstra eficiente, tempos de execução aula_9.pdf Aula 9 Entregar lista 2, saiu lista 3
10 14/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 Fazer TP 1, Lista 3
11 16/9 Árvore geradora mínima (MST), algoritmos de Prim e Kruskal, propriedades do corte e do ciclo aula_11.pdf Aula 11 Fazer TP 1, Lista 3
12 21/9 Apresentação do TP1 (alunos com nome entre A e L, considerando o menor nome da dupla). Iremos votar no melhor trabalho (ver resultado abaixo) Entregar TP 1
13 23/9 Apresentação do TP1 (alunos com nome entre M e Z, considerando o menor nome da dupla). Iremos votar no melhor trabalho (ver resultado abaixo) Entregar TP 1
14 28/9 Primeira Prova. Início pontualmente às 13h.
Rever todas as listas em preparação para a prova		 Entregar Lista 3
15 30/09 Paradigma guloso, coloração em grafos, número cromático, algoritmo guloso, Teorema das 4 cores aula_12.pdf Aula 12 Saiu TP 2
16 05/10 Problema da soma do subconjunto (subset sum), recursão, programação dinâmica, problema da mochila aula_12b.pdf Saiu Lista 4
17 07/10 (Presença Opcional) Vista e correção da P1; dicussão e dúvidas sobre trabalho prático e listas. Tragam duas dúvidas! Fazer TP2
- 12/10 Feriado: Dia de Nossa Senhora Aparecida, a Padroeira do Brasil Fazer TP2
- 14/10 Não teremos aula: professor visitando o Inria at Université Côte d'Azur (grupo de pesquisa NEO) Fazer TP2
18 19/10 Grafos com pesos negativos, caminho mais curto entre todos os pares, programação dinâmica, algortimo de Floyd-Warshall, melhorias aula_13.pdf Aula 13 Fazer TP 2 e Lista 4
19 21/10 Caminho mínimo com pesos negativos, programação dinâmica, algoritmo de Bellman­-Ford, melhorias, roteamento em redes aula_14.pdf Aula 14 Fazer TP 2
20 26/10 Emparelhamentos em grafos bipartidos, algoritmo, análise de complexidade, corretude aula_15.pdf Aula 15 Fazer Lista 4
- 28/10 Feriado: Dia do Funcionário Público Fazer Lista 4
- 2/11 Feriado: Dia de Finados Entregar Lista 4
21 4/11 Apresentação e discussão do TP2. Iremos votar no melhor trabalho (ver resultado abaixo) Entregar TP2
22 9/11 Redes de fluxo, problema do fluxo máximo, problema do corte mínimo, dualidade aula_16.pdf Aula 16 Saiu Lista 5 e TP 3
23 11/11 Fluxo máximo, algoritmo de Ford-Fulkerson, análise, melhorias aula_17.pdf Aula 17 Fazer Lista 5
24 16/11 Aplicações do fluxo máximo: emparelhamento, caminhos distintos, corte mínimo, segmentação de imagens aula_18.pdf Aula 18 Fazer TP 3
25 18/11 Apanhado final, caminho trilhado, futuro em grafos (ciência das redes e teoria dos grafos), avaliação da disciplina

Veja palestra-duelo dos professores sobre Ciência das Redes e Teoria dos Grafos

aula_19.pdf Aula 19 Fazer Lista 5
26 23/11 Apresentação e discussão do TP 3. Iremos votar no melhor trabalho (ver resultado abaixo) Entregar TP 3
27 25/11 Segunda Prova. Início pontualmente às 13h.
Rever todas as listas depois da P1 em preparação para a prova		 Entregar Lista 5
- 30/11 Não teremos aula: Se preparar para a PF (rever todas as listas e trabalhos)
28 02/12 Prova Final. Início pontualmente às 13h.
Refazer e rever todas as listas em preparação para a prova
29 09/12 Vista e discussão das provas: P2 e PF

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.