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.

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: 

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

OBSERVAÇÃO:  Disciplina obrigatória no currículo do BCC.

[Veja dados da disciplina no JúpiterWeb]