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

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,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.

Disciplinas Equivalentes

Disciplina Curso
TEORIA DA COMPUTAÇÃO Ciência da Computação (Bacharelado)
TEORIA DA COMPUTAÇÃO Engenharia de Computação (Bacharelado)

Página gerada em 06/07/2022 22:47:46 (consulta levou 0.105158s)