Computability and Complexity
Code
8415
Academic unit
Faculdade de Ciências e Tecnologia
Department
Departamento de Matemática
Credits
6.0
Teacher in charge
Isabel Maria Oitavem Fonseca da Rocha Kahle
Weekly hours
4
Total hours
84
Teaching language
Português
Prerequisites
-
Subject matter
1. Partial Recursive Functions
2. Turing Machines
3. The Halting Problem
4. Complexity Classes
5. NP completeness of SAT
Bibliography
- 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.
Teaching method
Usual university-style Math teaching.
Evaluation method
Seminar + Report + oral examination (optional): 100%