Análise de Algoritmos

• Carga horária: 60 horas
• Tipo: Eletiva
• Pré-requisito:
  • Estruturas de Dados e Algoritmos
  • Matemática Discreta
• Professor: Alexandre Rademaker

Ementa

Complexidade de algoritmos: notação O, análise de consumo de tempo e espaço em memória. Complexidade de problemas: redução polinomial, classes de problemas de decisão (P, NP, NP-difícil, etc.). Técnicas algorítmicas: algoritmos gulosos, divisão e conquista programação dinâmica. Análise de problemas: busca e ordenação, problemas em grafos, problemas de geometria computacional.

Bibliografia

Obrigatória

1. Kleinberg, J., & Éva Tardos. (2005). Algorithm Design. Addison Wesley.
2. Dasgupta, S., Papadimitriou, C. H., & Vazirani, U. V. (2008). Algorithms. McGraw-Hill.
3. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT press Cambridge.

Complementar

1. Leiserson, C. E., Rivest, R. L., Cormen, T. H., & Stein, C. (2002). Algoritmos: Teoria e Prática (7th ed.). Campus.
2. Lucchesi, C. L., Simon, I., Simon, I., Simon, J., & Kowaltowski, T. (1979). Aspectos Teóricos da Computação. IMPA.
3. Bentley, J. L. (2000). Programming Pearls. Addison-Wesley Professional.
4. Skiena, S. S. (2008). The Algorithm Design Manual. Springer.