Programa do curso

1. Algoritmos e Complexidade
2. Máquinas de Turing
3. Problema da Parada
4. Classes de Complexidade
5. Redução e Completude
6. Tópicos: Problemas NP-Completos, P-Completos e Classe NC

Avaliação

P1	03/10	MP = (P1 + P2)/2
P2	28/11	MA = (MP*0,7) + (Listas*0,3)
P0	05/12
Exame	17/12

Bibliografia básica

• PAPADIMITRIOU, C. H.
  Computational Complexity
  Ad. Addison Wesley - 1994
  
• GAREY, M; JOHNSON, D.
  Computers and Intratability
  Freeman, 1979
  
• SISPER, M.
  Introduction to the Theory of Computation
  PWS Publishing Company - 1997
  

TRABALHOS E LISTAS DE EXERCÍCIOS
Lista 1 [ps] [pdf]
Lista 2 [ps] [pdf]
Lista 3 [ps] [pdf]

MATERIAL SUPLEMENTAR
complex-lovasz.ps

NOTAS
[Notas]