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