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
- 2 de setembro (aula 7)
- Filas de prioridade (heaps)
- Heapsort
- Lista 4
Transparências. [pdf]
Leitura recomendada: CLRS Cap 6 Heapsort.
- 4 de setembro (aula 8)
- Cota inferior para ordenação
- Ordenação em tempo linear
Transparências. [pdf]
Leitura recomendada: CLRS Cap 8 Sorting in Linear Time.
- 15 de setembro (aula 9)
- Análise probabilística do Bucketsort
- Dicas sobre algoritmos de ordenação
- Lista 5
Transparências. [pdf]
Leitura recomendada: CLRS Sec 8.4 Bucket sort e SW cap 2.
- 17 de setembro
Matéria da prova: notação assintótica,
recorrências, análise de pior caso, de melhor caso, de caso médio, ordenação.
- 22 de setembro (aula 10)
- Programação dinâmica: introdução
- Linhas de produção
Transparências. [pdf]
Leitura recomendada: CLRS Sec 15.1 da segunda edição.
- 24 de setembro (aula 11)
- Programação dinâmica
- Produto de cadeias de matrizes
- Lista 6
Transparências. [pdf]
Leitura recomendada: CLRS secs 15.2 e 15.3.
- 29 de setembro (aula 12)
- Programação dinâmica
- Subsequência comum mais longa
- AAB otima - apresentação do problema
Transparências. [pdf]
Leitura recomendada: CLRS Secs 15.4 e 15.5.
Outubro
Novembro
Last modified: Fri Apr 26 10:23:36 BRT 2013