Programação das aulas de MAC5711
Segundo semestre de 2015
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
- 1 de outubro (aula 13)
- Programação dinâmica
- ABB ótima
- Problema da mochila - apresentação do problema
Transparências. [pdf]
Leitura recomendada: CLRS Sec 15.5.
- 6 de outubro (aula 14)
- Programação dinâmica
- Problema da mochila
Transparências. [pdf]
Leitura recomendada: KT Sec 6.4.
- 8 de outubro (aula 15)
- Representações de grafos
- Algoritmos elementares para grafos: BFS
Leitura recomendada: CLRS Sec 22.1 e começo da 22.2.
- 12 e 16 de outubro: Segunda semana de break
- 20 de outubro (aula 16)
- Algoritmos elementares para grafos: continuação de BFS
Leitura recomendada: CLRS Sec 22.2.
- 22 de outubro
Matéria da prova: ordenação em tempo
linear, cota inferior para ordenação e programação dinâmica.
- 27 de outubro (aula 17)
- Algoritmos elementares para grafos: DFS
- Lista 7
Transparências. [pdf]
Referências bibliográficas: CLRS sec 22.3.
- 29 de outubro (aula 18)
- Árvores geradoras mínimas: algoritmo de Kruskal
- Union-find
Transparências. [pdf]
Referências bibliográficas: CLRS secs 23.1, 23.2 e 21.3 para o union-find.
Novembro
Last modified: Thu May 23 18:34:28 BRT 2013