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
- 9 de agosto (aula 1):
- Introdução. [ps.gz][pdf]
- Olhe as 4 funções abaixo e execute cada um dos programas para
alguns valores de x e y.
Sinta a diferença de comportamento entre eles.
[f1]
[f2]
[f3]
[f4]
- Por que desprezamos as constantes?
- Ordenação - método de inserção.
- Lista 1
Leitura recomendada: CLRS, cap 1, cap 2 (sec 2.1 e 2.2).
Se não tiver uma boa formação em matemática, estude também os
apêndices A, B e, brevemente, o C também do CLRS.
- 11 de agosto (aula 2):
- Notação assintótica.
- Exercício 2.
[ps.gz]
[pdf]
Leitura recomendada: CLRS, cap 3.
Transparências em formato compacto. [pdf]
[ps.gz]
- 16 de agosto (aula 3)
- Divisão e conquista.
- Mergesort.
- Resolução de recorrências.
[ps.gz]
[pdf]
- Exercício 3.
[ps.gz]
[pdf]
Leitura recomendada: além das anotações acima sobre
recorrências, CLRS, sec 2.3 e sec 4.1.
- 18 de agosto (aula 4)
Leitura recomendada: CLRS, cap 4.
- 23 de agosto (aula 5)
- 25 de agosto (aula 6 - previsão)
Leitura recomendada: CLRS, sec 7.1, 7.2 e começo da 7.3.
Transparências. [pdf]
[ps.gz]
- 30 de agosto (aula 7)
- Análise probabilística
- Algoritmo do máximo
- Quicksort aleatorizado
- Lista 3.
Leitura recomendada: CLRS, apêndice C e cap 5, se você
não tem familiaridade com probabilidade, secs 7.3 e 7.4.
Transparências. [pdf]
[ps.gz]
Setembro
Last modified: Tue Oct 18 14:47:06 EDT 2005