Teoria dos Grafos

COS242 - 2025/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 4/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 6/8 Definições importantes, algumas propriedades, algumas classes de grafos aula_2.pdf Aula 2 Fazer lista 1
3 11/8 Representando grafos, matriz e lista, operações básicas, tempos de acesso aula_3.pdf Aula 3 Fazer lista 1
4 13/8 Explorando grafos, algoritmo genérico, BFS, camadas, distâncias, árvore geradora, caminho mínimo aula_4.pdf Aula 4 Terminar lista 1
5 18/8 Implementando a BFS, DFS e suas implementações, complexidade aula_5.pdf Aula 5 Entregar lista 1, saiu lista 2
6 20/8 Componentes conexos, grafos direcionados, busca em grafos direcionados, grafos fortemente conexos aula_6.pdf Aula 6 Fazer lista 2, saiu TP 1
7 25/8 DAG, execução de tarefas, ordenação topológica, algoritmo eficiente aula_7.pdf Aula 7 Fazer lista 2
8 27/8 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
9 1/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 3/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
- 8/9 Não teremos aula. Professor visitando o INDY no EPFL. Fazer TP 1, Lista 3
11 10/9 [Prof. Carlos Brito] Diferentes algoritmos para o problema de triplas engraçacas: melhorando a eficiência com ordenação! aula_TOrd.pdf Fazer TP 1, Lista 3
12 15/9 [Prof. Carlos Brito] Árvore geradora mínima (MST), algoritmos de Prim e Kruskal, propriedades do corte e do ciclo aula_MST.pdf
aula_11.pdf		 Aula 11 Fazer TP 1, Lista 3
- 17/9 Não teremos aula. Professor visitando o INDY no EPFL. Fazer TP 1, Lista 3
13 22/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
14 24/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
15 29/9 Primeira Prova. Início pontualmente às 13h.
Rever todas as listas em preparação para a prova		 Entregar Lista 3
- 1/10 Não teremos aula. Professor participando do BRACIS. Fazer TP 1, Lista 3
16 6/10 Paradigma guloso, coloração em grafos, número cromático, algoritmo guloso, Teorema das 4 cores aula_12.pdf Aula 12 Saiu TP 2
17 8/10 Problema da soma do subconjunto (subset sum), recursão, programação dinâmica, problema da mochila aula_12b.pdf Saiu Lista 4
18 13/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 15/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 20/10 Emparelhamentos em grafos bipartidos, algoritmo, análise de complexidade, corretude aula_15.pdf Aula 15 Fazer Lista 4
21 22/10 Vista da P1; dicussão e dúvidas sobre trabalho prático e listas. Tragam duas dúvidas!
- 27/10 Feriado antecipado: Dia do Funcionário Público (28/10) Terminar TP2
- 29/10 Aula cancelada: operação policial histórica no complexo do alemão Terminar TP2
22 3/11 Apresentação e discussão do TP2. Iremos votar no melhor trabalho (ver resultado abaixo) Entregar TP2
23 5/11 Aula cancelada: falta d'água no Centro de Tecnologia! Saiu TP 3 e Lista 5
24 10/11 Redes de fluxo, problema do fluxo máximo, problema do corte mínimo, fluxo máximo, algoritmo de Ford-Fulkerson, análise, melhorias aula_16_17.pdf Aula 16
Aula 17 		Fazer TP 3
25 12/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
26 17/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
27 19/11 Apresentação e discussão do TP 3. Iremos votar no melhor trabalho (ver resultado abaixo) Entregar TP 3
28 24/11 Segunda Prova. Início pontualmente às 13h.
Rever todas as listas depois da P1 em preparação para a prova		 Entregar Lista 5
- 26/11 Não teremos aula.
- 1/12 Não teremos aula: Se preparar para a PF (rever todas as listas e trabalhos)
29 3/12 Prova Final. Início pontualmente às 13h.
Refazer e rever todas as listas em preparação para a prova
31 10/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.