Análise de Algoritmos
Professor Murilo V. G. da Silva
Horários de Aula: 3a-feira (15h30) e 5a-feira (15h30)
Horário de atendimento ao aluno:
3a-feira: (18h30 - 19h30) (agendar por e-mail)
4a-feira: (10h30 - 11h30)
Data da primeira prova: 24/10/2019 -- RESULTADOS (P1)
Data da segunda prova: 03/12/2019 -- RESULTADOS (P2)
Data da prova final: 12/12/2019 -- RESULTADO FINAL
PARTE 1 (FUNDAMENTOS)
Slides 01 -- Introdução
Slides 02 -- Exemplo Comentado de Análise
Slides 03 -- Notação Assintótica: O(1)
Slides 04 -- Notação Assintótica: O(f(n))
Slides 05 -- Notação Assintótica: Notação Omega
Slides 06 -- Notações Theta, O* e Õ
Slides 07 -- Notação Assintótica: o(1), o(f(n)), definições de "aproximadamente" e de "muito menor"
Slides 08 -- Notação Assintótica: Famílias notáveis
PARTE 2 (DIVISÃO E CONQUISTA)
Slides 09 -- Análise de algoritmos recursivos
Slides 10 -- Algoritmo de Karatsuba
Slides 11 -- Algoritmo de Strassen
PARTE 3 (ALGORITMOS GULOSOS)
Slides 12 -- Código de Huffman
PARTE 4 (PROGRAMAÇÃO DINÂMICA)
Slides 13 -- Subsequência Crescente Máxima
Slides 14 -- Distância de Edição
Slides 15 -- Algoritmo de Bellman-Held-Karp
PARTE 5 (ANÁLISE AMORTIZADA)
Slides 16 -- Incrementador Binário
Slides 17 -- Union-find
Sistema de Avaliação: Média = (P1 + P2)/2
Lista de Exercícios
Bibliografia
-
[DPV06] -- DASGUPTA, S.; PAPADIMITRIOU C. H.; VAZIRANI, U.
Algorithms , McGraw-Hill, 2006
-
[CLRS09] CORMEN, T.H.; LEISERSON, C.E.; RIVEST, R.L.; STEIN, C. Introduction to Algorithms , MIT Press, 2009.
-
[KTA05] KLEINBERG, J; TARDOS, E. Algorithm Design, Addison Wesley, 2005 .
-
[MUP17] MITZENMACHER, M ; UPFAL, E. Probability and Computing Cambridge University Press (2nd ed), 2017.