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.