Complexidade de Algoritmos I - MAB704

Ementa: 

Algoritmos. Notação O, O e T. Problemas em P: Programação Dinâmica, Método Guloso, Backtracking, Limites inferiores. Problemas de decisão. Problemas em NP. Certificados. Classe NP-completo. Conceito de Problema NP-completo Forte. Problemas de Otimização. Algoritmos Aproximativos. Esquemas de Aproximação em Tempo Polinomial.  

Bibliografia: 
  • Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, McGraw-Hill, 2002. 
  • M. R. Garey e D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co.,New York, 1979. 
  • Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.