• Objetivos

Capacitar o aluno a dominar os conceitos ligados à máquina de Turing e reconhecer as principais classes de complexidade, bem como demonstrar problemas NP-completos através da técnica de redução. 

Ementa Algoritmos e Complexidade Máquinas de Turing Problema da Parada Classes de Complexidade Redução e Completude Tópicos: Problemas NP-Completos, P-Completos e Classe NC

Avaliações     04/10  -  P1 29/11  -  P2       MP  = (P1+P2)/2 06/12  -  PO      MA = 0,7MP+0,3Listas     15/12  -  Exame

• Bibliografia
  

• PAPADIMITRIOU, C. H. .
Computational Complexity
Ed. Addison Wesley - 1994

• GAREY, M; JOHNSON, D. 
  Computers and Intratability  
  Freeman, 1979
• SIPSER, M.  
  Introduction to the Theory of Computation  
  PWS Publishing Company - 1997
  
• HOPCROFT, MOTWANI e ULLMAN
  Introduction to Automata Theory, Languages and Computation
  Ed. Addison Wesley - 2001 -2nd edition