• 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 e P-Completos

Avaliações     28/09 -  P1 28/11  -  P2    MP  = (P1+P2)/2 07/12  -  PO   MA = 0,7MP+0,3Listas     14/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