Programação das aulas de MAC338
Primeiro semestre de 2005
CLR refere-se à primeira edição do livro do Cormen, Leiserson e Rivest.
Há uma diferença na numeração em relação à edição mais nova, que tem
alguns capítulos a mais.
Olhe aqui para
uma correspondência da numeração da primeira para a segunda edição, em que o
livro ganhou mais um autor (CLRS, de Cormen, Leiserson, Rivest e Stein).
Março
Abril e maio
Junho
- 1 de junho (aula 19)
- Método guloso: problema fracionário da mochila.
Formato comprimido para impressão:
[ps.gz] [pdf]
Transparências. [pdf] [ps.gz]
- 3 de junho (aula 20)
- Método guloso: problema da coleção disjunta máxima de
intervalos.
- Coloração de intervalos.
Formato comprimido para impressão:
[ps.gz] [pdf]
Transparências. [pdf] [ps.gz]
- 8 de junho (aula 21)
- Método guloso: algoritmo de Kruskal.
- Lista 7 [pdf] [ps.gz]
- Análise amortizada: contador binário.
Formato comprimido para impressão:
[ps.gz] [pdf]
Transparências. [pdf] [ps.gz]
- 10 de junho (aula 22 - previsão)
- Análise amortizada: operações sobre uma pilha.
- ED para conjuntos disjuntos.
[pdf] [ps.gz]
- Lista 8 [pdf] [ps.gz]
- 15 de junho (aula 23)
Formato comprimido para impressão:
[ps.gz] [pdf]
Transparências. [pdf] [ps.gz]
- 17 de junho (aula 24)
Formato comprimido para impressão:
[ps.gz] [pdf]
- 22 de junho (aula 25)
- Teoria de Complexidade Computacional
- 24 de junho (aula 26)
- Reduções
- Algoritmos de aproximação
Formato comprimido para impressão da parte de aproximação:
[ps.gz] [pdf]
Transparências. [pdf] [ps.gz]
- 29 de junho (aula 27)
- 1 de julho
Matéria da prova: método guloso,
análise amortizada, complexidade computacional.
Last modified: Fri Jun 24 12:38:41 BRT 2005