Programação das aulas de MAC338
Primeiro semestre de 2013
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.
Fevereiro e Março
Abril
- 3 de abril
Matéria da prova: notação assintótica,
recorrências, divisão e conquista, ordenação.
- 5 de abril (aula 9)
- Lista 3
- Filas de prioridade (heaps)
- Heapsort
Transparências. [pdf]
Leitura recomendada: CLRS cap 6.
- 10 de abril (aula 10)
- Cota inferior para ordenação
- Ordenação em tempo linear
Transparências. [pdf]
Leitura recomendada: CLRS cap 8.
- 12 de abril (aula 11)
- Análise probabilística do Bucketsort
- Dicas sobre algoritmos de ordenação
Transparências. [pdf]
Leitura recomendada: CLRS cap 8.4 e SW cap 2.
- 17 de abril (aula 12)
- Programação dinâmica: introdução
- Linhas de produção
Transparências. [pdf]
Leitura recomendada: CLRS cap 15.1 da
segunda edição.
- 19 de abril (aula 13)
- Programação dinâmica
- Produto de cadeias de matrizes
Transparências. [pdf]
Leitura recomendada: CLRS secs 15.2 e 15.3.
- 24 de abril (aula 14)
- Programação dinâmica
- Subsequência comum mais longa
- AAB otima - apresentação do problema
Transparências. [pdf]
Leitura recomendada: CLRS cap 15.4.
- 26 de abril (aula 15)
- Programação dinâmica
- ABB otima
- Problema da mochila: próxima aula!
Transparências. [pdf]
Leitura recomendada: CLRS cap 15.5.
Maio
Last modified: Fri Apr 26 10:23:36 BRT 2013