MAC0338

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.
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.

PRÉ-REQUISITO NO CURRÍCULO DO BCC:
MAC0323.

CARGA HORÁRIA SEMANAL E NÚMERO DE CRÉDITOS:
4 horas, 4 créditos-aula.

CRITÉRIO DE AVALIAÇÃO DA APRENDIZAGEM:
Média ponderada de provas e exercícios.

BIBLIOGRAFIA BÁSICA:

Livro do N�vio

Tradu��o da 3a edi�ao est� boa (pelo am). 

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein,
Introduction to Algorithms, 3rd ed., McGraw-Hill, 2009.

S. Dasgupta, C.H. Papadimitriou, U.V. Vazirani,
Algorithms,
Mc Graw Hill, 2007.

U. Manber,
Introduction to Algorithms: A Creative Approach,
Addison-Wesley, 1989.

J. Kleinberg, É. Tardos,
Algorithm Design Addison-Wesley, 2005.

R. Neapolitan, K. Naimipour,                        
Foundations of Algorithms,
Fourth Edition,  Jones and Bartlett Publishers, 2009.