Computabilidade e Complexidade
Código
8415
Unidade Orgânica
Faculdade de Ciências e Tecnologia
Departamento
Departamento de Matemática
Créditos
6.0
Professor responsável
Isabel Maria Oitavem Fonseca da Rocha Kahle
Horas semanais
4
Total de horas
84
Língua de ensino
Português
Pré-requisitos
-
Conteúdo
1. Funções Recursivas Parciais
2. Máquinas de Turing
3. O Problema da Paragem
4. Classes de Complexidade
5. A NP-completude do Problema SAT (“Satisfiability”)
Bibliografia
- René Cori and Daniel Lascar. Mathematical Logic, Part II. Oxford University Press, 2001.
- Steven Homer and Alan L. Selman. Computability and Complexity Theory. Springer, 2011.
- Reinhard Kahle. Computabilidade e Complexidade. Sebentas.
Método de ensino
Métodos habituais de ensino universitário da Matemática.
Método de avaliação
Seminário + Relatório + Prova oral (opcional): 100%