Programação das aulas de MAC5711
Primeiro semestre de 2004
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
- 20 de maio (aula 19)
- Análise amortizada.
- Union-find [ps.gz]
[pdf].
- 1 de junho (aula 20)
- Busca de padrão: algoritmo ingênuo e KMP.
- 3 de junho (aula 21)
- Complexidade computacional [ps.gz]
[pdf].
- 8 de junho
- 15 de junho (aula 22)
- Teorema de Cook (enunciado e comentários apenas).
- Redução do SAT para o 3-SAT.
- 17 de junho (aula 23)
- Redução do 3-SAT para o VC.
- Redução do 3-SAT para 3-COLORAÇÃO.
- 22 de junho
- 24 de junho
- 29 de junho
Matéria da prova: Análise amortizada, union-find, Kruskal,
busca de padrão, complexidade computacional.
Last modified: Thu Jun 17 11:23:36 BRT 2004