|
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 | |
| 13 | 27/9 | Árvore do jogo em jogos de uma pessoa (quebra-cabeças) e duas pessoas, jogando de forma ótima, algoritmo minimax | Quadro! | Saiu lista 4 | |
| 14 | 2/10 | Apresentação do TP1 (sob demanda). Discussão, dúvidas, e perguntas visando a P1. Tragam suas dúvidas! | Entregar TP 1 | ||
| 15 | 4/10 | Primeira Prova. Início pontualmente às 13h. Rever todas as listas em preparação para a prova |
Entregar lista 4 | ||
| 16 | 9/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 | 11/10 | Problema da soma do subconjunto (subset sum), recursão, programação dinâmica, problema da mochila | aula_12b.pdf | Fazer TP 2 | |
| 18 | 16/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 | Saiu Lista 5 |
| 19 | 18/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 | 23/10 | Emparelhamentos em grafos bipartidos, algoritmo, análise de complexidade | aula_15.pdf | Aula 15 | Fazer Lista 5 |
| 21 | 25/10 | Apresentação e discussão do TP2. Iremos votar no melhor trabalho (ver resultado abaixo) | Entregar TP2 | ||
| 22 | 30/10 | Redes de fluxo, problema do fluxo máximo, problema do corte mínimo, dualidade | aula_16.pdf | Aula 16 | Fazer Lista 5 |
| 23 | 1/11 | Fluxo máximo, algoritmo de Ford-Fulkerson, análise, melhorias | aula_17.pdf | Aula 17 | Fazer Lista 5 |
| 24 | 6/11 | Aplicações do fluxo máximo: emparelhamento, caminhos distintos, corte mínimo, segmentação de imagens | aula_18.pdf | Aula 18 | Entregar Lista 5 |
| 25 | 8/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 | Saiu TP 3 e Lista 6 |
| - | 13/11 | Não teremos aula. Avançar na Lista 6 e TP 3! | Fazer TP 3 e Lista 6 | ||
| - | 15/11 | Não teremos aula. Feriado em função do Dia da Proclamação da República | Fazer TP 3 | ||
| - | 20/11 | Não teremos aula. Feriado em função do Dia da Consciência Negra | Fazer TP 3 | ||
| 26 | 22/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 6 | ||
| 28 | 29/11 | Segunda Prova. Início pontualmente às 13h. Rever todas as listas depois da P1 em preparação para a prova |
Entregar Lista 6 | ||
| - | 4/12 | Não teremos aula: Se preparar para a PF, tirar dúvidas com monitores! | |||
| 29 | 6/12 | Prova Final. Início pontualmente às 13h. Refazer e rever todas as listas em preparação para a prova |
|||
| 30 | 11/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]
Resultado da votação dos alunos no melhor trabalho (juri popular). Parabéns a Beatriz Nascimento e Barbara Cerqueira pelo primeiro lugar convicto, com 25 votos de 69 votos (máximo de 2 votos por aluno)!
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]
Resultado da votação dos alunos no melhor trabalho (juri popular). Parabéns a William P. Pfaltzgraff pelo primeiro lugar com 16 votos de 69 votos (máximo de 2 votos por aluno)!
grafo_rf_1.txt.gz [< 1 MB]
grafo_rf_2.txt.gz [1 MB]
grafo_rf_3.txt.gz [4 MB]
grafo_rf_4.txt.gz [49 MB]
grafo_rf_5.txt.gz [104 MB]
grafo_rf_6.txt.gz [159 MB]
Resultado da votação dos alunos no melhor trabalho (juri popular). Parabéns aos alunos Matheus Cardoso e João Pedro Sales pelo primeiro lugar com 14 votos de 46 votos (máximo de 2 votos por aluno)!
As notas de aulas serão tiradas principalmente dos seguintes referências: