Jupiterweb

Disciplina

Informações da Disciplina

Preparar para impressão

Júpiter - Sistema de Graduação

Instituto de Matemática e Estatística

Ciência da Computação

Disciplina: MAC0423 - Introdução à Teoria da Computabilidade

Créditos Aula:	4
Créditos Trabalho:	0
Tipo:	Semestral

Objetivos

Estudo de funções computáveis, estabelecimento da existência de funções não computáveis.

Programa Resumido

Programa

Formalização da noção de algoritmo.
Enumeração de funções computáveis e a existência de funções universais.
A existência de problemas indecidíveis.
O teorema da recursão.
Conjuntos recursivos e recursivamente enumeráveis.
Outros modelos para computabilidade.

Avaliação

	Método


	Critério
	Média ponderada de provas e exercícios.

	Norma de Recuperação

Bibliografia

M. Minsky, "COMPUTATION: FINITE AND INFINITE MACHINES", Prentice Hall, 1967.
H.R. Lewis, C.H. Papadimitriou, "ELEMENTS OF THE THEORY OF COMPUTATION", Prentice Hall, 1981.
A.F. Kfoury, R.N. Moll, M.A. Arbib, "A PROGRAMMING APPROACH TO COMPUTABILITY", Springer, 1982.

Requisitos

Os Requisitos variam conforme o curso para o qual ela é oferecida.

Clique para consultar o oferecimento para MAC0423.