|
UNIVERSIDADE DO ESTADO DO RIO DE JANEIRO
|
| UNIDADE: INSTITUTO POLITÉCNICO | ||
| DEPARTAMENTO: DEPARTAMENTO DE MODELAGEM COMPUTACIONAL | ||
| DISCIPLINA: Computabilidade | ||
| CARGA HORÁRIA: 45 | CRÉDITOS: 3 | CÓDIGO: IPRJ01-10776 |
| MODALIDADE DE ENSINO: Presencial | TIPO DE APROVAÇÃO: Nota e Frequência | |
| STATUS | CURSO(S) / HABILITAÇÃO(ÕES) / ÊNFASE(S) |
| Obrigatória | IPRJ - Engenharia de Computação (versão 1) |
| TIPO DE AULA | CRÉDITO | CH SEMANAL | CH TOTAL |
| Teórica | 3 | 3 | 45 |
| TOTAL | 3 | 3 | 45 |
EMENTA:
Máquina de Turing. Funções recursivas. Tese de Church. Teorema da incompletude de Godel. Introdução ao Cálculo Lambda. Classes de problemas P, NP, NP-Completo e NP-Difícil. Métodos de redução de problemas.
OBJETIVO(S):
Fornecer os fundamentos da Teoria da Computabilidade.
BIBLIOGRAFIA: 1. SPISER, M., Introduction to the Theory of Computation, PWS, 1997.
2. PAPADIMITRIOU, C., HARRY, L., Elementos de Teoria da Computação, Bookman, 2000.
3. MENEZES, P. F.B., DIVERIO, T.A., Teoria da Computação, Sagra-Luzzatto, 1999.