MAC0338 Análise de Algoritmos
[Edição do 2o. semestre de 2026]
(Página eternamente minimal e em mutação)
Slides usados em aula
Sinopse das aulas
Agosto
- Introdução. Ordenação por inserção; análise de complexidade; análise assintótica
- Análise de ordenação por inserção (cont.). Divisão e conquista: ordenação por intercalação (mergesort)
- Análise de mergesort; recorrências
- Quicksort; sobre invariantes: veja aula04b.pdf
- Quicksort (cont.): algoritmos de partição variados (veja aula05a_23Quicksort.pdf e aula05b_23DemoPartitioning.pdf e uma tese de doutorado sobre quicksort de 2016). Análise de caso médio
- Quicksort e select aleatorizados
- Ordenação em tempo linear. Select determinístico: \(k\)-ésimo menor elemento em tempo linear determinístico
- \(k\)-ésimo menor elemento em tempo linear determinístico (cont.)
Setembro
- Multiplicação de inteiros grandes. Multiplicação de matrizes (curiosidade: \(\omega<2.371177\))
- Multiplicação de matrizes (curiosidade: \(\omega<2.371177\); cont.). Programação dinâmica
- Semana da Pátria
- Semana da Pátria
- Programação dinâmica (cont.)
- Programação dinâmica (cont.)
- Programação dinâmica (cont.)
- Algoritmos gulosos
- Algoritmos gulosos (cont.)
Outubro
- Algoritmos gulosos (cont.)
- Algoritmos gulosos (cont.). LIS: longest increasing sequence
- Aula cancelada
- Break
- Aula de exercícios online (link Zoom será disponibilizado no e-Disciplinas). Conteúdo visto até esta data. Um pequeno simulado
- Prova 1 adiada, a pedidos (Não haverá aula. Professor no evento Combinatorics, Number Theory and Dynamical Systems)
- Não haverá aula (Professor no evento Combinatorics, Number Theory and Dynamical Systems)
- Prova 1
- Aula cancelada
Novembro
- Análise amortizada
- Análise amortizada (cont.). Notas de Fiebrink