Clique para ir ao início Universidade de Brasília - UnB
Decanato de Ensino de Graduação - DEG
Secretaria de Administração Acadêmica - SAA
MatrículaWeb
GRADUAÇÃO
  Seja bem-vindo(a).
  Para ter acesso ao menu de Aluno, faça o login.
MatrículaWeb  clique aqui para fazer o login.
 


Período Atual
2017/2


Disciplina - Listagem de Ementa/Programa
Disciplina: 116360 - TEORIA DA COMPUTACAO
(Ver Oferta)

Graduação

Curso
Oferta
Telefones
Calendário
Mensagem da SAA
Benefícios DAC


Órgão: CIC - Departamento de Ciência da Computação
Código: 116360
Denominação: TEORIA DA COMPUTACAO
Nível: Graduação
Vigência: 1971/2
Pré-req: MAT-113107 Algebra 1 E
FIL-137481 Lógica 1 OU
FIL-137481 Lógica 1 E
MAT-113115 Teoria dos Números 1 OU
MAT-113107 Algebra 1 E
CIC-117366 Lógica Computacional 1 OU
CIC-117366 Lógica Computacional 1 E
MAT-113115 Teoria dos Números 1
Ementa:

FUNCOES COMPUTAVEIS. FUNCOES RECURSIVAS PRIMITIVAS. TESE DE CHUR-

CH. ENUMERACAO DE GODEL. MAQUINAS ABSTRATAS. MAQUINAS DE TURING. O DE-

CIMO PROBLEMA DE HILBERT. EQUACOES DIOFANTINAS. INDECIDIBILIDADE.

Programa:

1. FUNCOES COMPUTAVEIS

1.1 - CONJUNTOS RECURSIVAMENTE ENUMERAVEIS

1.2 - FUNCOES RECURSIVAS PRIMITIVAS

1.3 - FUNCOES RECURSIVAS PARCIAIS

1.4 - TESE DE CHURCH

1.5 - ENUMERACAO DE GODEL

2. MAQUINAS ABSTRATAS

2.1 - DEFINICAO DE MAQUINA DE TURING

2.2 - COMBINACAO DE MAQUINAS DE TURING

2.3 - MAQUINAS DE TURING ESPECIAIS

2.4 - MAQUINAS UNIVERSAIS

2.5 - ENUMERACAO DE GODEL DE MAQUINAS DE TURING

3. O DECIMO PROBLEMA DE HILBERT

3.1 - CONJUNTOS E FUNCOES DIOFANTINAS

3.2 - O ENUNCIADO DO DECIMO PROBLEMA DE HILBERT

3.3 - ENUMERACAO DE GODEL DE EQUACOES DIOFRANTINAS

4. INDECIDIBILIDADE

4.1 - ALGUNS PROBLEMAS INDECIDIVEIS

4.2 - MAQUINAS DOTADAS DE ORACULO

Bibliografia:

.3 - ENUMERACAO DE GODEL DE EQUACOES DIOFANTINAS

D. E. COHEN EGLAND

"COMPUTABILITY AND LOGIC" ELLIS HORWOOD LI1987

W.S. BRAINERD AND L.H. LANDWEBERNEW YORK

"THEORY OF COMPUTATION" JOHN WILEY & SON1974

J.E. HOPCROFT AND J.D. ULLMAN MASS.,

"INTRODUCTION TO AUTOMATA THEORY, LANGUAGES

AND COMPUTATION". ADDISON WESLEY 1979

D. HOFSTADTER

"GODEL, ESCHER, BACH: AN ETHERNAL GOLDEN BRAID" PEQUIM BOOKS 1980

H.HERMES BERLIN

"ENUMERABILITY, DECIDABILITY, COMPUTABILITY" SPRINGER VERLAG 1969

© 2017 CPD - Centro de Informática
UnB - Universidade de Brasília