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.