Portal do Ementário

A disciplina Teoria da Computação visa dotar os acadêmicos de conhecimentos dos elementos da Teoria da Computabilidade: os fundamentos teóricos do processo de computação, os modelos computacionais utilizados para representar sistemas computacionais na teoria da computabilidade, os limites daquilo que pode ser computado; bem como de suas aplicações em Ciência da Computação. Ao final da disciplina, os alunos deverão ser capazes de: utilizar funções recursivas para especificar algoritmos; construir máquinas de Turing para decidir determinadas linguagens ou realizar certas tarefas computacionais; entender a tese de Church-Turing e o que ela significa para a Ciência da Computação e identificar problemas de decisão decidíveis e indecidíveis.

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

[1] Hopcroft, J. E.; Motwani, R.; Ullman, J. D.; Introdução à teoria de autômatos: linguagens e computação. 2ed, Ed. Campus, 2002. ISBN: 8535210725. [2] Lewis, H. R.; Papadimitriou, C.; Elementos de Teoria da computação. 2ed, Ed. Bookman, 2000. ISBN: 8573075341. [3] DIVERIO, T. A.; MENEZES, P. B.. Teoria da Computação: Máquinas Universais e Computabilidade. 3ed. Porto Alegre: Bookman, 2011. ISBN:9788577808243.

[1] Vieira, N. J.; Introdução aos Fundamentos da Computação: Linguagens e Máquinas. Ed. Thomson, 2006. ISBN: 8522105081. [2] Sipser, M.; Introdução à Teoria da Computação. Ed. Thomson, 2007. ISBN: 9878522104994. [3] MENEZES, P. B.: Linguagens Formais e Autômatos. Porto Alegre: Sagra-Luzzato, 2001.