UNIVERSIDADE DO ESTADO DO RIO DE JANEIRO

FORMULÁRIO DE IDENTIFICAÇÃO DA DISCIPLINA
 

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
 
STATUSCURSO(S) / HABILITAÇÃO(ÕES) / ÊNFASE(S)
ObrigatóriaIPRJ - Engenharia de Computação (versão 1)

TIPO DE AULA CRÉDITO CH SEMANAL CH TOTAL
Teórica3345
TOTAL 3 3 45

OBJETIVO(S):

Fornecer os fundamentos da Teoria da Computabilidade.
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.


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.