Nome da Atividade
TEORIA DA COMPUTAÇÃO
CÓDIGO
1110042
Carga Horária
68 horas
Tipo de Atividade
DISCIPLINA
Periodicidade
Semestral
Unidade responsável
CARGA HORÁRIA TEÓRICA
4
FREQUÊNCIA APROVAÇÃO
75%
CARGA HORÁRIA OBRIGATÓRIA
4
CRÉDITOS
4

Ementa

Programas e máquinas. Máquinas universais. Funções recursivas. Computabilidade.

Objetivos

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.

Conteúdo Programático

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

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, Martin D., SIGAL, Ron, WEYUKER, Elaine. Computability, complexity, and languages: fundamentals of theorical computer 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.

Página gerada em 19/03/2024 04:40:04 (consulta levou 0.128327s)