A plataforma de comunicação principal será o grupo no classroom.
As aulas serão presenciais.
- Atendimento: sob demanda, pessoalmente ou via email.
- Horário: Terça e Quinta, 10:00-12:00
- Local: F3-007 (CCMN)
- Monitores: Lucas Tsai e Yasmim Lima
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 05/08 | Introdução ao curso | ||
| Qui 07/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 12/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 14/08 | Capítulo 20.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Busca em Largura | |
| Ter 19/08 | Capítulos 20.2 e 20.3 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Subgrafo Predecessor e Busca em Profundidade | |
| Qui 21/08 | Capítulo 20.3 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Busca em Profundidade | |
| Ter 26/08 | Capítulos 20.3 e 20.4 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Aplicações de DFS: Classificação de arestas e Ordenação Topológica | — |
| Qui 28/08 | Capítulo 20.5 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Aplicações de DFS: Componentes Fortemente Conexos | |
| Ter 02/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 04/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 09/09 | — | Exercícios da Lista 1 | — |
| Qui 11/09 | Capítulos 21.0 e 21.1 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Árvore geradora mínima: algoritmo genérico e prova para identificar arestas seguras | |
| Ter 16/09 | Capítulo 21.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Árvore geradora mínima: algoritmos de Kruskal e Prim | |
| Qui 18/09 | Capítulo 21.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Complexidade do algoritmo de Prim, comparação de Kruskal e Prim; Lista 1 | |
| Ter 23/09 | Sem aula: semana da integração acadêmica (SIAC) | ||
| Qui 25/09 | Sem aula: semana da integração acadêmica (SIAC) | ||
| Ter 30/09 | Plantão de Dúvidas | ||
| Qui 02/10 | — | ||
| Ter 07/10 | P1 | ||
| Qui 09/10 | Resolução da P1 | ||
| Ter 14/10 | Capítulo 22.0 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | O problema de caminhos mínimos de origem única | |
| Qui 16/10 | — | ||
| Ter 21/10 | Capítulo 22.3 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | O algoritmo de Dijkstra | |
| Qui 23/10 | Capítulo 14 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Programação Dinâmica | |
| Ter 28/10 | Apresentações | ||
| Qui 30/10 | Capítulos 22.1 e 22.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Bellman-Ford e distância mínima em DAGs | |
| Ter 04/11 | Capítulos 23.0 e 23.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | O problema de caminhos mínimos entre todos os pares de vértices; Floyd-Warshall | |
| Qui 06/11 | Apresentações | ||
| Ter 11/11 | Capítulos 24.0, 24.1, e 24.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Fluxo máximo, corte mínimo, redes residuais e caminhos aumentantes | |
| Qui 13/11 | Capítulos 24.0, 24.1, e 24.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022. | Ford-Fulkerson, Edmonds-Karp; revisão de Floyd-Warshall | |
| Ter 18/11 | Apresentações | ||
| Qui 20/11 | Sem aula: dia da consciência negra | ||
| Ter 25/11 | PR | ||
| Qui 27/11 | Vista da PR | ||
| Ter 02/12 | Apresentações | ||
| Qui 04/12 | Apresentações | ||
| Ter 09/12 | Apresentações | ||
| Qui 11/12 | PF | ||
| Ter 16/12 | Vista da PF | ||
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
- ✅ 1 Prova (P1)
- ✅ 1 Trabalho (P2)
- ✅ 1 Prova Final (PF)
- ✅ 1 Prova de Reposição (PR) - apenas com comprovante de acordo com o regulamento da universidade
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