Análise de Algoritmos

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: 

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

Complementar: 

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

Período: 

  • Eletiva