A plataforma de comunicação principal será o grupo no classroom.
As aulas serão presenciais.
- Atendimento: sob demanda.
- Horário: Terça e Quinta, 10:00-12:00
- Local: F2-010 (CCMN)
- Monitor(a): Francisco Florencio
Algoritmos e Grafos
Nesta disciplina, iremos ver problemas clássicos em Teoria dos Grafos, que servirão de pano de fundo para a compreensão de técnicas de desenvolvimento e análise de algoritmos, ao mesmo tempo em que familiarizam o aluno com a representação e manipulação de grafos no computador.
Informação Básica
Ementa
Representação de Grafos; Ordenação Topológica; Buscas em grafos e Digrafos (largura e profundidade); Técnicas de Desenvolvimento de Algoritmos; Decomposição; Recursão; Algoritmo Guloso; Programação Dinâmica; Aplicação das Técnicas Usadas; Fluxo Máximo.Cronograma Planejado
| Data | Leituras | Conteúdo | Material |
|---|---|---|---|
| Ter 11/08 | Capítulo 20.1 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Representação de grafos no computador; algoritmos básicos de inserção, remoção e consulta em grafos direcionados e não direcionados | |
| Qui 13/08 | Capítulo 20.1 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Representação de grafos no computador; algoritmos básicos de inserção, remoção e consulta em grafos direcionados e não direcionados | |
| Ter 18/08 | Capítulo 20.1 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Representação de grafos no computador; algoritmos básicos de inserção, remoção e consulta em grafos direcionados e não direcionados | |
| Qui 20/08 | Capítulo 20.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Busca em Largura e Subgrafo Predecessor | |
| Ter 25/08 | Capítulo 20.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Busca em Largura e Subgrafo Predecessor | |
| Qui 27/08 | — | Atividade de Busca em Largura | — |
| Ter 01/09 | Capítulo 20.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Busca em Largura e Subgrafo Predecessor | |
| Qui 03/09 | Capítulos 20.3 e 20.4 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Busca em Profundidade, Classificação de arestas e Ordenação Topológica | |
| Ter 08/09 | Capítulo 20.5 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Aplicações de DFS: Componentes Fortemente Conexos | |
| Qui 10/09 | — | Atividade de Busca em Profundidade | — |
| Ter 15/09 | — | Outras aplicações e problemas de DFS | — |
| Qui 17/09 | Capítulo 15.1 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Problemas de otimização, método guloso, o problema da árvore geradora mínima | |
| Ter 22/09 | Capítulos 21.0, 21.1 e 21.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Árvore geradora mínima: algoritmo genérico, arestas seguras e os algoritmos de Kruskal e Prim | |
| Qui 24/09 | — | Exercícios da Lista 1 | — |
| Ter 29/09 | P1 | ||
| Qui 01/10 | — | Resolução da P1 | — |
| Ter 06/10 | Sem aula: semana da integração acadêmica (SIAC) | ||
| Qui 08/10 | Sem aula: semana da integração acadêmica (SIAC) | ||
| Ter 13/10 | Capítulo 22 (introdução) do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | O problema do caminho mínimo de origem única: propriedade do subcaminho, arestas negativas e ciclos, subgrafo predecessor e a intuição do algoritmo de Dijkstra | |
| Qui 15/10 | — | Atividade de Dijkstra | — |
| Ter 20/10 | Capítulo 22.3 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | O algoritmo de Dijkstra: relaxamento, corretude e complexidade | |
| Qui 22/10 | Capítulos 14.1, 14.2 e 14.3 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Programação dinâmica: subestrutura ótima, memoização e tabulação | |
| Ter 27/10 | Capítulos 22.1 e 22.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Caminhos mínimos com pesos negativos: o algoritmo de Bellman-Ford e caminhos mínimos em dags | |
| Qui 29/10 | Capítulos 23.1 e 23.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Caminhos mínimos entre todos os pares: o algoritmo de Floyd-Warshall | |
| Ter 03/11 | — | Atividade de Floyd-Warshall | — |
| Qui 05/11 | Capítulo 24.1 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Redes de fluxo: fluxo máximo, rede residual e caminhos aumentantes | |
| Ter 10/11 | Capítulo 24.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | O método de Ford-Fulkerson e o teorema do fluxo máximo e corte mínimo | |
| Qui 12/11 | — | Atividade de fluxo máximo | — |
| Ter 17/11 | Capítulo 24.3 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Emparelhamento máximo em grafos bipartidos: modelagem como um problema de fluxo máximo | |
| Qui 19/11 | Capítulo 24.3 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Emparelhamento máximo: o teorema da integralidade, complexidade e aplicações | |
| Ter 24/11 | P2 | ||
| Qui 26/11 | — | — | — |
| Ter 01/12 | PR | ||
| Qui 03/12 | — | — | — |
| Ter 08/12 | PF | ||
| Qui 10/12 | — | — | — |
| Ter 15/12 | — | — | — |
| Qui 17/12 | — | — | — |
Bibliografia
Bibliografia Primária
- Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.
Bibliografia Secundária
- Teoria Computacional de Grafos; os algoritmos. Jayme Luiz Swarcfiter, Fabiano S. Oliveira e Paulo E. D. Pinto. Elsevier, 2018.
Avaliação
- ✅ 2 Provas (P1/P2)
- ✅ 1 Prova de Reposição (PR) - apenas com comprovante de acordo com o regulamento da universidade. Substitui apenas uma nota (P1 ou P2).
- ✅ 1 Prova Final (PF)
MP = (P1 + P2) / 2
Se MP < 3 → Reprovado
Se MP ≥ 7 → Aprovado
Se 3 ≤ MP < 7 → Então o aluno faz a Prova Final (PF)
Se (MP + PF) / 2 ≥ 5 → Aprovado
Se (MP + PF) / 2 < 5 → Reprovado
Se MP < 3 → Reprovado
Se MP ≥ 7 → Aprovado
Se 3 ≤ MP < 7 → Então o aluno faz a Prova Final (PF)
Se (MP + PF) / 2 ≥ 5 → Aprovado
Se (MP + PF) / 2 < 5 → Reprovado