Programação das aulas de MAC5711
Segundo semestre de 2016
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.
Agosto
Setembro
Outubro
- 5 de outubro (aula 13)
- Programação dinâmica
- Problema da mochila
- Exercício 21 (das bandeiras) e exercício 12 da L6
Slides: [pdf]
Leitura recomendada: KT Sec 6.4.
- 7 de outubro (aula 14)
- Representações de grafos
- Algoritmos elementares para grafos: BFS
Slides: [pdf]
Leitura recomendada: CLRS Sec 22.1 e 22.2.
- 10 e 14 de outubro: Segunda semana de break
- 19 de outubro (aula 15)
- Algoritmos elementares para grafos: BFS e DFS
- Ordenação topológica usando DFS
- Lista 7
Slides: [pdf]
Leitura recomendada: CLRS Sec 22.2, 22.3 e 22.4.
- 21 de outubro (aula 16)
- Aplicação de DFS: Algoritmo Kosaraju-Shamir
Slides: [pdf]
Referências bibliográficas: CLRS sec 22.5.
- 26 de outubro (aula 17)
- Caminhos mínimos: algoritmo de Dijkstra
- Caminhos mínimos: algoritmo de Floyd-Warshall
- Lista 8
Slides: [pdf]
Leitura recomendada: CLRS cap 25 até a sec 25.2 e sec 26.2.
- 28 de outubro - feriado
Novembro