|
COS242 - 2023/2 |
Retirado do Wikipedia |
|
COS242 - 2023/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 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 | ...
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]
As notas de aulas serão tiradas principalmente dos seguintes referências: