Banner Topo 2

Teoria da Computação

Departamento Unidade
Ciência da Computação CAC - Campus de Catalão
Nome da Disciplina Código Período
Teoria da Computação 185  
Carga Horária Semestral Carga horária Semanal Ano Semestre
64h Teórica: 4h Práticas: 0h 2013 02
Conteúdo:
Classe Np, classe NP-Completa, Computabilidade, Lidando com problemas NP Completos.
Ementa:

Evidências para a tese de Church. Equivalência de modelos de computação: linguagem PL, Máquinas de Turing e Lambda Calculus; técnicas de programação nesses modelos. Máquina universal, problema da parada, problemas indecidíveis; conjuntos recursivamente enumeráveis; conjuntos recursivos.Teorema de Rice e Teorema de Rogers. Complexidade computacional: reducibilidade, classes naturais de problemas.

Bibliografia:
  • LEWIS, H.R., PAPADIMITRIOU, C.H. Elementos de Teoria da Computação. 2 ed. Porto Alegre : Bookman Cia. Editora, 2000.
  • Divério Tiaraju.  Teoria da Computação: máquinas universais e computabilidade.  Sagra  Luzzatto, Porto Alegre, 1999.
  • SIPSER, M. Introduction to the Theory of Computation.EUA : PWS Pub. Co., 1997.
  • LEWIS, H.R., PAPADIMITRIOU, C.H. Elementos de Teoria da Computação. 2 ed. Porto Alegre : Bookman Cia. Editora, 2000.
  • GAREY, Michael. JOHNSON, David - Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.
  • SIPSER, M. Introduction to the Theory of Computation.EUA : PWS Pub. Co., 1997.