Detalhes

Nome da Disciplina: TEORIA DE COMPLEXIDADE II

Carga Horária: 60

Créditos: 4

Disciplina Regular: Sim

Algoritmos Polinomiais. Problemas de decisão. Certificados. Problemas em NP. Resolver = verificar? (P = NP?) US$1.000.000. Teoria da NP-completude. Maquina de Turing. Teorema de Cook. SAT. Reduções polinomiais. Provas de NP-dificuldade. Exemplos. A dicotomia polinomial x NP-completo. Casos interessantes. Considerações sobre complexidade de algoritmos. Pior caso, caso médio, complexidade amortizada, limites superiores e inferiores. NP-completude do corte máximo. NP-completude do conjunto independente máximo. NP-completude do ciclo hamiltoniano. (estes três problemas serão revisitados nas abordagens randomizadas e/ou aproximativas.). Hierarquia de complexidade. Teoria das Probabilidades. Revisão Variáveis Aleatórias / Linearidade da Esperança. Desigualdades de Markov e Chebyshev. Geração de números (pseudo-)aleatórios / Python . Algoritmos Randomizados. Algoritmos aproximativos.

C.H. Papadimitriou , Computational complexity, Addison-Wesley, Reading, Mass. 1994.
T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to algorithms, The MIT Press, McGraw-Hill Book Company, 1990.
M.R. Garey and D.S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, Freman, New York, 1979.
Vazirani, Vijay V., Approximation Algorithms, 2003.