Portal do Ementário

Compreender os fundamentos da análise do desempenho de algoritmos clássicos. Aplicar técnicas de projeto de algoritmos em problemas práticos de computação.

Fundamentos de matemática concreta. Fundamentos de análise de eficiência: análise assintótica, pior caso e caso médio. Análise de desempenho de algoritmos iterativos. Análise de desempenho de algoritmos recursivos. Análise de desempenho de paradigmas clássicos de projetos de algoritmo: guloso, divisão e conquista, programação dinâmica. Teoria de complexidade: classes de problemas P, NP, NP-Complete e P-Space. Redução de problemas e complexidade. Problemas de otimização NP-hard e algoritmos de aproximação. Classes de complexidade derivadas.

CORMEN, T.H. et al, Algoritmos: teoria e prática, 1a. edição, Editora Elsevier, 2002. AHO, A.V.; HOPCROFT, J.E.; ULLMAN, J.D., The design and analysis of computer algorithms, 1a. edição, Editora Addison-Wesley, 1974. LEWIS, H.R.; PAPADIMITRIOU, C.H., Elementos de teoria da computação, 2a. edição, Editora Bookman, 2000.

SUDKAMP, T.A., Languages and Machines, 2a. edição, Editora Addison-Wesley, 1997. SEDGEWICK, R.; FLAJOLET, P., An introduction to the analysis of algorithms, 1a. edição, Editora Addison-Wesley, 1996. GAREY, M.R.; JOHNSON, D.S., Computers and intractability: a guide to the theory of NP-completeness, 1a. edição, Editora Freeman, 1979. ARORA, S.; BARAK, B., Computational complexity: a modern approach, 1a. edição, Editora Cambridge, 2009. GRAHAM, R.L.; KNUTH, D.E.; PATASHNIK, O., Matemática concreta: fundamentos para a ciência da computação, 2a. edição, Editora LTC, 1995.