Ementa de Disciplina

INF1015 | COMPUTABILIDADE

4 créditos

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

CARNIELLI , WALTER; EPSTEIN, RICHARD L. COMPUTABILIDADE, FUNÇÕES COMPUTÁVEIS, LÓGICA E OS FUNDAMENTOS DA MATEMÁTICA; SÃO PAULO: UNESP, 2009. DIVERIO, TIARAJÚ ASMUZ; MENEZES, PAULO BLAUTH. TEORIA DA COMPUTAÇÃO: MÁQUINAS UNIVERSAIS E COMPUTABILIDADE; PORTO ALEGRE: SAGRA LUZZATTO, 2000. LEWIS, H.,; PAPADIMITRIOU, C. ELEMENTOS DE TEORIA DA COMPUTAÇÃO; PORTO ALEGRE: BOOKMAN, 2000.

Bibliografia Complementar

Nenhuma biliografia complementar encontrada para INF1015

Pré-requisitos

INF1022 e INF1721

ou

INF1626 e INF1721

Co-requisitos

Nenhum co-requisito encontrado para INF1015

Última atualização da ementa: 06/02/2014