Institutional PortalUFPEL

Objetivo Geral:

Apresentar os fundamentos teóricos da Ciência da Computação. Capacitar o aluno a entender a natureza dos problemas reais sob o ponto de vista da computabilidade dos mesmos.

1. Programas e máquinas
• Estruturas de programas
• Estrutura de máquinas
• Computações e funções computadas
• Equivalência entre programas
• Equivalência entre máquinas
2. Máquinas universais
• Máquina de Turing
• Máquinas Norma, Post, e outras máquinas universais
• A classe de equivalência das máquinas universais
3. Funções Recursivas
• Funções iniciais
• Composição Generalizada, Recursão e Minimização
• Funções Recursivas Primitivas
• Funções Recursivas
• Funções Computáveis
4. Computabilidade
• A Tese de Church-Turing
• Decidibilidade
• Redutibilidade

Bibliografia Básica:

• BIRD, Richard. Programs and machines: an introduction to the theory of computation. John Wiley & Sons, 1976.
• SIPSER, Michael. Introdução à teoria da computação. Editora Thompson, 2007.
• TAYLOR, R. Gregory. Models of Computation and Formal Languages. New York: Oxford University Press, 1998.

Bibliografia Complementar:

• DIVÉRIO, Tiaraju Asmuz, MENEZES, Paulo F. B. Teoria da computação: máquinas universais e computabilidade. Editora Sagra Luzzatto, 1999.
• DAVIS,MartinD.,SIGAL,Ron,WEYUKER,Elaine. Computability,complexity,andlanguages: fundamentalsoftheoricalcomputer science. Academic Press, 1994.
• LEWIS, Harry R., PAPADIMITRIOU, Christos. Elementos de teoria da computação. Editora Bookman, 2008.
• HOPCROFT, John, ULLMAN, Jeffrey, MOTWANI, Rajeev. Introdução à teoria de automatos, linguagens e computação. Editora Elsevier, 2002.
• SUDKAMP, Thomas A. Languages and Machines: An Introduction to the Theory of Computer Science. Addison-Wesley, 2006. 672 p.