Computabilidade e Complexidade
2011/2012
(MMat)
Departamento de Matemática
Faculdade de Ciências e Tecnologia da Universidade de Coimbra
Doutor Pedro Quaresma de Almeida (Professor Auxiliar)
14 de Outubro de 2011
- Programa
-
- Introdução
- Funções Recursivas Parciais
- Funções Recursivas Primitivas
- Função de Ackermann
- A função de Ackermann não é recursiva primitiva
- Funções recursivas parciais
- Máquinas de Turing
- Máquinas de Turing deterministas
- Toda a função recursiva parcial e T-computável
- Toda a funcao T-computável é recursiva parcial
- Máquina de Turing Universal
- Conjuntos Recursivos Enumeráveis
- O Problema da Paragem
- Teoria da Complexidade
- PTIME
- Máquinas não deterministas
- Problema SAT (``Satisfiability'')
- Bibliografia
-
- Homer, S., Selman, A.L. Computability and Complexity Theory,
D. Gries and F.B. Schneider eds., Texts in Computer Science
Springer, New York, 2001.
- René Cori and Daniel Lascar. Mathematical Logic, Part
II. Oxford University Press, 2001.
- Apontamentos
-
apontamentosCmpCmp.pdf (28/11/2011)
- Folhas Práticas
-
- Tópicos
- A - A linguagem de programação WHILE
Definição da linguagem de programação WHILE;
equivalência entre a classe das funções programáveis
em WHILE e a classe de funções recursivas parciais.
A. J. Kfoury, Robert N. Moll, and Michael A. Arbib, A
Programming Approach to Computability, Springer, 1982
Rui Jorge Nunes Sequeira
- B - Cálculo lambda sem tipos
Definição do cálculo lambda sem tipos;
demonstração de que todas as funções recursivas
parciais são computáveis no cálculo lambda sem tipos
através dos números de Church.
Henk Barendregt. Lambda Calculi with Types. In S. Abramsky, Dov
Gabbay, and T. Maibaum (eds.), Handbook of Logic in Computer Science, Oxford
University Press, 1992.
Francisco Jose Nibau Antunes
- C - Máquinas de Registos
Definição de máquinas de registos e as suas
ilustrações com "flowcharts"; demonstração da
equivalência com as funções recursivas parciais.
Klaus Weihrauch. Computability. Springer, 1987
Filipe Valeriano
- D - Autómatos finitos
Definição de autómatos finitos e a
caracterização das linguagens aceites.
Cristina Sernadas. Introdução à Teoria da
Computação. Editorial Presença, 1993.
Isabel Juliana Raposo Primo
- E - Gramáticas regulares
Definição de gramáticas regulares e sua
caracterização.
Cristina Sernadas. Introdução à Teoria da
Computação. Editorial Presença, 1993.
Rita Daniela Larangeiro da Costa Ferreira
- F - Cálculo lambda com tipos simples
Definição do cálculo lambda com tipos simples e as
funções computáveis nesta teoria.
Helmut Schwichtenberg. Functions definable in the simply-typed lambda
calculus, Archiv für Mathematische Logik, 17:113 114, 1976
Jason Nobre Bolito
- G - Redução de máquinas de Turing com k fitas, k >
1, para máquinas de Turing com uma só fita
Comparação formal de máquinas de Turing com diferentes
números de fitas.
Steven Homer and Alan L. Selman. Computability and Complexity
Theory. Springer, 2001
Benvindo Évora
- Pauta Provisória
-
Pedro Quaresma de Almeida
Departamento de Matemática
Faculdade de Ciências e Tecnologia
Universidade de Coimbra
3000 COIMBRA, PORTUGAL
pedro - mat uc pt