Portal do Ementário

Compreender o ferramental teórico que descreve os mecanismos de computação do ponto de vista matemático. Compreender os limites da computação algorítmica e suas implicações práticas.

Funções computáveis. Funções recursivas. Tese de Church. Máquinas de Turing. Decidibilidade. Conjuntos recursivamente enumeráveis.

LEWIS, H.R.; PAPADIMITRIOU, C.H., Elementos de teoria da computação, 2a. edição, Editora Bookman, 2000. DIVERIO, T.A.; MENEZES, P.B., Teoria da computação: máquinas universais e computabilidade, 2a. edição, Editora Sagra, 2000. HOPCROFT, J.E.; MOTWANI, R.; ULLMAN, J.D., Introdução à teoria de autômatos, linguagens e computação, 1a. edição, Editora Campus, 2003.

SIPSER, M., Introdução à teoria da computação, 1a. edição, Editora Thompson, 2007. SUDKAMP, T.A., Languages and machines, 2a. edição, Editora Addison-Wesley, 1997. VIEIRA, N.J., Introdução aos fundamentos da computação: linguagens e máquinas, 1a. edição, Editora Thomson, 2006. FERNÁNDEZ, M., Models of computation: an introduction to computability theory, 1a. edição, Editora Springer, 2009. MORET, B. M. E., The theory of computation, 1a. edição, Editora Addison-Wesley, 1998.