Programação das aulas de MAC6711
Primeiro semestre de 2010
Março
- 3 de março (Aula 1):
- Problema do número de inversões
- Notação assintótica
Leitura recomendada: notas de aulas do
Prof. Paulo Feofiloff sobre
notação
assintótica, seções 5.1 a 5.3 do livro de Kleinberg e Tardos (KT)
Transparências
[pdf][ps.gz],
com alguns exercícios de notação assintótica incluídos.
- 5 de março (Aula 2):
- Algoritmo O(n lg n) para o número de inversões
- Divisão e conquista
- Recorrências
- Par de pontos mais próximos
- Lista 1
Leitura recomendada: sec. 33.4 do CLRS,
seções 5.3 a 5.4 do livro de Kleinberg e Tardos (KT), sec 7.3 do
capítulo 7 das
JAI 2009.
Transparências da primeira parte da aula 2,
com mais exercícios de notação assintótica
[pdf][ps.gz].
Transparências sobre o segundo problema
[pdf]
[ps.gz].
- 10 de março (Aula 3):
- Animação dos algoritmos do par mais próximo
- Produto de polinômios e convoluções
Leitura recomendada: começo do cap 30 até
a sec. 30.1 do CLRS e sec. 5.6 do KT.
- 12 de março (Aula 4):
- Transformada discreta de Fourier (DFT)
- Transformada rápida de Fourier (FFT)
Leitura recomendada: sec. 30.2 do
CLRS e sec. 5.6 do KT.
O algoritmo em formato de transparências
[pdf].
- 17 de março (Aula 5):
Exercício: Modifique o algoritmo visto em aula para
calcular a inversa da transformada discreta de Fourier em tempo
Theta(n lg n).
- 19 de março (Aula 6):
- Multiplicação de números grandes - algoritmo quadrático
- Algoritmo de Karatsuba
- Algoritmo de Strassen.
Leitura recomendada: sec 28.2 do CLRS,
sobre o algoritmo de Strassen, e sec 5.5 do KT, sobre o algoritmo de
Karatsuba.
Para resolução de recorrências, leia o cap 4 do CLRS.
Exercício: Prove, por indução em n, que a solução da
recorrência T(1) = 1 e T(n) = 8T(n/2)+n2 para n
potência de 2 é T(n) = 2n3-n2.
Exercício: Resolva a recorrência T(1) = 1 e T(n) =
7T(n/2)+n2 para n potência de 2. Deduza depois qual é
o comportamento assintótico de T(n), ou seja, qual é a sua ordem
de crescimento.
Exercício: Se pensarmos que o tamanho da entrada do
algoritmo de Strassen é m=2n^2, podemos deduzir que o tempo do
algoritmo, em função do m é dado pela seguinte recorrência:
T(m) = 8T(m/4) + m. Resolva essa recorrência e conclua qual
é o consumo de tempo do algoritmo em função do m. Isso é
ou não consistente com o que deduzimos na aula?
Transparências
[pdf][ps.gz].
- 24 de março (Aula 7):
Leitura recomendada: Cap 9 do CLRS.
Transparências [pdf][ps.gz].
- 26 de março (Aula 8):
- Algoritmos probabilísticos
- Teste de igualdade de polinômios
- Problema da contenção
Leitura recomendada: Sec 1.1 do livro
Probability and Computing: Randomized Algorithms and
Probabilistic Analysis, de Computing and Probability (QA274
.M574 2005), e começo do Cap 13 e Sec 13.1 do KT.
- 31 de março: Semana Santa (não há aula)
Abril
Last modified: Tue Apr 6 17:37:51 BRT 2010