Programação das aulas de MAC338
Primeiro semestre de 2008
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).
Fevereiro
- 26 de fevereiro (aula 1):
- Introdução [ps.gz]
[pdf]
- Ordenação - método de inserção
- 28 de fevereiro (aula 2):
- Notação O (Oh grande)
- Ordenação - mergesort
Transparências: do professor Paulo.
[pdf]
Leitura recomendada: CLR, sec 1.1 e 1.2.
Março
- 4 de março (aula 3):
- Divisão e conquista
- Cálculo do máximo recursivo
- Mergesort
- Recorrências
- 6 de março (aula 4):
- Notação assintótica
- Recorrências
- Lista 1
Transparências. [pdf]
[ps.gz]
- 11 de março (aula 5)
- Resolução de recorrências
Exercício para entregar na aula de quinta.
[pdf] [ps.gz]
- 13 de março (aula 6)
- Divisão e conquista
- Multiplicação de inteiros grandes: algoritmo de Karatsuba
- Multiplicação de matrizes: método de Strassen
- Lista 2
Exercícios para entregar dia 25/3:
L1-6c) e L1-7b)
Exercícios para entregar dia 27/3:
L2-1a) e L2-6.
Leitura recomendada: sec 5.5 do livro
de Kleinberg e Tardos. Sec 28.2 do CLRS.
Transparências. [pdf] [ps.gz]
- 25 de março (aula 7)
- Análise probabilística
- Cálculo do máximo
Transparências. [pdf] [ps.gz]
- 27 de março (aula 8)
- Quicksort
- Análises de pior e melhor caso
- Quicksort probabilístico
- Lista 3
Transparências. [pdf] [ps.gz]
Referências bibliográficas: CLRS sec 5.1, C.2, C.3, cap 7.
Abril
Maio
Junho
Last modified: Tue Jun 10 12:20:53 BRT 2008