Portal do Ementário

Consolidar conceitos de análise da correção e do desempenho de algoritmos. [Familiaridade] Explicar o significado de "melhor", "esperado" e "pior" caso de um algoritmo. [Familiaridade] Desenvolver a habilidade de projetar algoritmos e estimar seu desempenho. [Familiaridade] Descrever o uso de relações de recorrência para determinar a complexidade de tempo de algoritmos definidos recursivamente. [Uso] Resolver relações de recorrência elementares usando, por exemplo, o Teorema Mestre. [Uso] Analisar a complexidade dos principais algoritmos de ordenação (simples e eficientes) e apresentar uma cota inferior de tais algoritmos. [Familiaridade] Descrever os conceitos dos paradigmas de projeto de algoritmos: força bruta, programação dinâmica, divisão e conquista e algoritmo guloso. [Familiaridade] Identificar exemplos aplicáveis a cada um dos paradigmas de projeto de algoritmos. [Avaliação] Apresentar as características que diferenciam os problemas que podem ser resolvidos por algoritmos gulosos dos que devem ser resolvidos usando programação dinâmica. [Familiaridade] Apresentar um estudo de caso da análise de alguns problemas clássicos como: algoritmo quicksort aleatorizado, tabelas de hashing, problema da mochila, multiplicação de inteiros (algoritmo de Karatsuba) e matrizes (algoritmo de Strassen), árvores geradoras mínimas de grafos (algoritmos de Prim e Kruskal), entre outros. [Uso] Introduzir noções da teoria da complexidade computacional, incluindo as As classes P, NP, e NP-completo, e redução entre problemas. [Familiaridade]

Complexidade de tempo e espaço de algoritmos. Análise assintótica. Introdução à classes de complexidade. Relação de recorrência. Análise de pior caso e análise probabilística. Cota inferior de ordenação. Paradigmas de projeto de algoritmos e métodos de análise. Estudo de casos. Introdução à teoria da complexidade computacional. As classes P, NP, e NP-completo. Redução entre problemas. Algoritmos probabilísticos.

CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford. Algoritmos. Teoria e Prática. 3a ed. Rio de Janeiro: Rio de Janeiro: Elsevier - Campus, 2012. KLEINBERG, Jon; TARDOS, Éva . Algorithm Design. 1a ed. Pearson, 2005. ZIVIANI, Nivio. Projeto de Algoritmos com Implementações em Java e C++. 1a ed. Cengage Learning, 2006.

CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford. Introduction to algorithms. 3rd ed. Cambridge, Mass.: The MIT Press; New York: McGraw-Hill, 2009. xix,1292 p. PAPADIMITRIOU, Christos H.; DASGUPTA, Sanjoy; VAZIRANI, Umesh. Algorithms. 1st ed. McGraw-Hill, 2007. KNUTH, Donald E. The Art of Computer Programming, vols. 1 e 3. 3th ed. Addison-Wesley, 1997. SKIENA, Steven S. The Algorithm Design Manual. 2nd ed. Springer, 2011. GOODRICH, Michael T.; TAMASSIA, Roberto. Algorithm Design and Applications. 1st ed. Wiley, 2014.