|
COS242 - 2024/2 |
Retirado do Wikipedia |
|
COS242 - 2024/2 |
Retirado do Wikipedia |
Todos devem se inscrever no Moodle da discilina. O código de acesso para auto-inscrição é codigo242.
| 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 1 | Saiu lista 1 |
| 2 | 19/8 | Definições importantes, algumas propriedades, algumas classes de grafos | aula_2.pdf | Aula 2 | Fazer lista 1 |
| - | 21/8 | Não teremos aula. Trabalhar na Lista 1 e nos conceitos de grafos | Fazer lista 1 | ||
| 3 | 26/8 | Representando grafos, matriz e lista, operações básicas, tempos de acesso | aula_3.pdf | Aula 3 | Fazer lista 1 |
| 4 | 26/8 | Explorando grafos, algoritmo genérico, BFS, camadas, distâncias, árvore geradora, caminho mínimo | aula_4.pdf | Aula 4 | Terminar lista 1 |
| 5 | 28/8 | Implementando a BFS, DFS e suas implementações, complexidade | aula_5.pdf | Aula 5 | Entregar lista 1, saiu lista 2 |
| 6 | 2/9 | Crescimento de funções, notação O e Omega, classes de funções importantes, tempo de execução | aula_O.pdf | Fazer lista 2 | |
| 7 | 4/9 | Componentes conexos, grafos direcionados, busca em grafos direcionados, grafos fortemente conexos | aula_6.pdf | Aula 6 | Fazer lista 2 e saiu TP 1 |
| 8 | 9/9 | DAG, execução de tarefas, ordenação topológica, algoritmo eficiente | aula_7.pdf | Aula 7 | Fazer lista 2 |
| 9 | 11/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 | Entregar lista 2 |
| 10 | 16/9 | Corretude de Dijkstra, fila de prioridades, heap binário, Dijkstra eficiente, tempos de execução | aula_9.pdf | Aula 9 | Saiu Lista 3 |
| 11 | 18/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 |
| 12 | 23/9 | Projetando redes, MST, algoritmos de Prim e Kruskal, propriedades do corte e do ciclo | aula_11.pdf | Aula 11 | Terminar TP 1 |
| 13 | 25/9 | Apresentação do TP1 (voluntária e sob demanda) | Entregar TP 1 | ||
| 14 | 30/9 | Dúvidas e discussão sobre a matéria (preparação para P1) | Fazer Lista 3 | ||
| 15 | 2/10 | Primeira Prova. Início pontualmente às 13h. Rever todas as listas em preparação para a prova |
Entregar Lista 3 | ||
| 16 | 7/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 | 9/10 | Problema da soma do subconjunto (subset sum), recursão, programação dinâmica, problema da mochila | aula_12b.pdf | Saiu Lista 4 | |
| 18 | 14/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 | 16/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 | 21/10 | Emparelhamentos em grafos bipartidos, algoritmo, análise de complexidade | aula_15.pdf | Aula 15 | Fazer Lista 4 |
| 21 | 23/10 | Dicussão e dúvidas sobtre trabalho prático e listas. Tragam duas dúvidas! | |||
| - | 28/10 | Feriado: Dia do Funcionário Público | Terminar TP2 | ||
| 21 | 30/10 | Apresentação e discussão do TP2. Iremos votar no melhor trabalho (ver resultado abaixo) | Entregar TP2 | ||
| 22 | 4/11 | Redes de fluxo, problema do fluxo máximo, problema do corte mínimo, dualidade | aula_16.pdf | Aula 16 | Entregar Lista 4 |
| 23 | 6/11 | Fluxo máximo, algoritmo de Ford-Fulkerson, análise, melhorias | aula_17.pdf | Aula 17 | Saiu Lista 5 |
| 24 | 11/11 | Aplicações do fluxo máximo: emparelhamento, caminhos distintos, corte mínimo, segmentação de imagens | aula_18.pdf | Aula 18 | Saiu TP 3 |
| 25 | 13/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 |
| - | 18/11 | Feriado: Encontro do G20 no Rio de Janeiro! | Fazer TP 3 e Lista 5 | ||
| - | 20/11 | Feriado: Dia da Consciência Negra | Fazer TP 3 e Lista 5 | ||
| 26 | 25/11 | Apresentação e discussão do TP 3. Iremos votar no melhor trabalho (ver resultado abaixo) | Entregar TP 3 | ||
| 27 | 27/11 | Discussão, dúvidas, e perguntas visando a P2. Tragam suas dúvidas! | Fazer Lista 5 | ||
| 28 | 2/12 | Segunda Prova. Início pontualmente às 13h. Rever todas as listas depois da P1 em preparação para a prova |
Entregar Lista 5 | ||
| - | 4/12 | Não teremos aula: Se preparar para a PF, tirar dúvidas com monitor! | |||
| 29 | 9/12 | Prova Final. Início pontualmente às 13h. Refazer e rever todas as listas em preparação para a prova |
|||
| 30 | 16/12 | Vista e discussão das provas: P2 e PF |
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.
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.
grafo_1.txt.gz [< 1 MB]
grafo_2.txt.gz [7 MB]
grafo_3.txt.gz [5 MB]
grafo_4.txt.gz [51 MB]
grafo_5.txt.gz [95 MB]
grafo_6.txt.gz [335 MB]
grafo_W_1.txt.gz [1 MB]
grafo_W_2.txt.gz [6 MB]
grafo_W_3.txt.gz [46 MB]
grafo_W_4.txt.gz [265 MB]
grafo_W_5.txt.gz [382 MB]
As notas de aulas serão tiradas principalmente dos seguintes referências: