MAC0338 - Análise de Algoritmos

Objetivos Análise do desempenho de alguns algoritmos clássicos. Estudo de ferramentas de matemática discreta úteis para a análise de algoritmos. Aprimoramento da capacidade de projetar e descrever algoritmos em que a correção seja transparente e da capacidade de estimar o desempenho de um algoritmo. Programa Elementos de análise assintótica (notação O, Omega e Theta). Solução de recorrências. Análise da correção e desempenho de algoritmos iterativos. Análise da correção e desempenho de algoritmos recursivos. Análise de pior caso e análise probabilística (caso médio). Algoritmos de busca e ordenação. Tabelas de dispersão (hashing). Algoritmos de programação dinâmica. Algoritmos gulosos. Algoritmos para busca de padrões. Análise amortizada de desempenho. Introdução à teoria da complexidade: problemas completos em NP.