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
- 2 de setembro (aula 8)
- Cota inferior para ordenação
- Ordenação em tempo linear
Slides. [pdf]
Leitura recomendada: CLRS Cap 8 Sorting in Linear Time.
- 5 a 9 de setembro (Semana da Pátria)
- 14 de setembro (aula 9)
- Programação dinâmica: introdução
- Linhas de produção
- Lista 5
Slides: [pdf]
Leitura recomendada: CLRS Sec 15.1 da segunda edição do CLRS.
- 16 de setembro - não houve aula
- 21 de setembro (aula 10)
- Programação dinâmica
- Produto de cadeias de matrizes
- Lista 6
Slides: [pdf]
Leitura recomendada: CLRS Secs 15.2 e 15.3.
- 23 de setembro (aula 11)
- Programação dinâmica
- Subsequência comum mais longa
Slides: [pdf]
Leitura recomendada: CLRS Sec 15.4.
- 28 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 e programação dinâmica.
- 30 de setembro (aula 12)
- Programação dinâmica
- AAB otima
- Comentários sobre a prova
Slides: [pdf]
Leitura recomendada: CLRS Sec 15.5.
Outubro
Novembro