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
• 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.
Turmas Ofertadas
Turma | Período | Vagas | Matriculados | Curso / Horários | Professores | ||||||
---|---|---|---|---|---|---|---|---|---|---|---|
T1 | 2024 / 2 | 43 | 43 |
Ciência da Computação (Bacharelado) Engenharia de Computação (Bacharelado) Horários
|
SIMONE ANDRE DA COSTA CAVALHEIRO Professor responsável pela turma |
Disciplinas Equivalentes
Disciplina | Curso |
---|---|
TEORIA DA COMPUTAÇÃO | Ciência da Computação (Bacharelado) |
TEORIA DA COMPUTAÇÃO | Engenharia de Computação (Bacharelado) |