Programação das aulas de MAC5711
Primeiro semestre de 2022
CLRS refere-se ao livro de Cormen, Leiserson, Rivest e Stein,
Introduction to Algorithms, 3a edição
(cuidado que as seções mudam de uma edição para a outra),
SW refere-se ao livro de Sedgewick e Wayne, Algorithms, e
KT refere-se ao livro de Kleinberg e Tardos, Algorithm Design.
Março
Abril
Maio
- 4 de maio (aula 9)
- Comentários sobre a primeira prova
- Programação dinâmica: introdução
- Números de Fibonacci
- Um problema para pensar: cortes de hastes
Slides: [pdf]
Leitura recomendada: Sec 15.1 da terceira edição do CLRS.
- 6 de maio (aula 10)
- Programação dinâmica
- Cortes de hastes
- Produto de cadeias de matrizes
- Lista 6
Slides: [pdf]
Leitura recomendada: CLRS Secs 15.2 e 15.3.
- 11 de maio (aula 11)
- Programação dinâmica
- Subsequência comum mais longa
Slides: [pdf]
Leitura recomendada: CLRS Secs 15.4.
- 13 de maio (aula 12)
- Programação dinâmica
- AAB otima
- Problema da mochila
Slides: [pdf]
Leitura recomendada: CLRS Secs 15.5 e KT Sec 6.4.
- 18 de maio (aula 13)
- Representações de grafos
- Algoritmos elementares para grafos: BFS
- Lista 7
Slides: [pdf]
Leitura recomendada: CLRS Sec 22.1 e 22.2.
- 20 de maio (aula 14)
- Aplicações de BFS
- Algoritmos elementares para grafos: DFS
Slides: [pdf]
Leitura recomendada: CLRS Sec 22.2 e 22.3.
- 25 de maio (aula 15)
- Ordenação topológica usando DFS
Slides: [pdf]
Leitura recomendada: CLRS Sec 22.3 e 22.4.
- 27 de maio
Matéria da prova: ordenação em tempo linear, cota inferior para ordenação, programação dinâmica, BFS e DFS.
Junho