Programação das aulas de MAC5711
Segundo 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 e seções 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).
Para o índice da segunda edição, olhe aqui.
Agosto
Setembro
Outubro
- 4 de outubro (aula 14)
- Análise amortizada - uma revisão
- Análise amortizada do union-find
[ps.gz]
[pdf]
Leitura recomendada: CLRS, sec 21.4.
- 6 de outubro (aula 15)
- Busca de padrão: algoritmo KMP
- Lista 6
Leitura recomendada: CLRS, sec 32.1 e sec 32.4.
- 11 de outubro - não haverá aula
- 13 de outubro - não haverá aula
- 18 de outubro
Matéria da prova: heaps, cotas
inferiores, algoritmos gulosos, análise amortizada, algoritmos
para árvore geradora mínima, busca de padrão.
- 20 de outubro (aula 16)
- Programação dinâmica
- Um exemplo: linha de produção
Leitura recomendada: CLRS, sec 15.1 e sec 15.3.
- 25 de outubro (aula 17)
- Programação dinâmica: subseqüência comum mais longa
- Programação dinâmica: problema da mochila
- Lista 7
Leitura recomendada: CLRS, sec 15.4 e, sobre mochila,
Manber, não lembro qual seção.
- 27 de outubro (aula 18)
- Programação dinâmica: problema da mochila
(primeira parte de [ps.gz][pdf])
- Programação dinâmica: árvore de busca binária ótima
- Lista 8
Leitura recomendada:
Primeira parte do ps/pdf acima e CLRS, sec 15.5 para ABBs ótimas.
- 1 de novembro (aula 19)
- Programação dinâmica: árvore de busca binária ótima
- Hashing
- 3 de novembro (aula 20)
- Hashing
- Complexidade computacional
Leitura recomendada: Secs 34.1 e 34.2 e/ou notas de aula
sobre complexidade
[ps.gz]
[pdf].
- 8 de novembro
- Adiamos a aula, por causa da palestra do Lamport.
- 10 de novembro (aula 21)
- Complexidade computacional: as classes P, NP e coNP e a
relação entre elas.
- 16 de novembro (aula 22)
- Complexidade computacional: reduções polinomiais,
problemas NP-completos, NP-difíceis e exemplos de
reduções.
- Lista 9
Leitura recomendada: Cap 34 do CLRS.
- 22 de novembro (aula 23 - previsão)
- Complexidade computacional
- Algoritmos de aproximação
Transparências
[pdf][ps.gz].
Formato enxuto [ps.gz].
O compendium de problemas de otimização que contém informações
sobre os melhores algoritmos de aproximação para eles e os
melhores resultados de inaproximabilidade conhecidos está
disponível na internet
aqui.
Se você gostou de algoritmos de aproximação, pode aprender um pouco
mais sobre isso lendo a introdução e um pouco mais deste
livro.
- 24 de novembro
Matéria da prova: Programação dinâmica,
hashing, complexidade computacional.
Last modified: Tue Nov 22 12:11:54 EDT 2005