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
Teaching language
Português
Prerequisites
---
Subject matter
1- Introduction to computability;
2- Undecidability;
3- Introduction to complexity theory;
4- Basic results of complexity theory;
5- Nondeterminism and NP-completeness;
6- Relative complexity.
Bibliography
Main book: Computability and Complexity Theory, Steven Homer and Alan L. Selman, Springer.
Other books:
- Structural Complexity, vol. I and II, Balcázar, Días and Gabarró, Springer.
- Mathematical Logic, Part II, Cori and Lascar, Oxford.
- Computability, Klaus Weihrauch, Springer.
- Handbook of Logic and Computer Science, Gabbay and Maibaum (ed.), Oxford University Press.
- A Programming approach to computability, Kfoury, Moll and Arbib, Springer.
- Computers and Intractability. A Guide to the Theory of NP-Completeness, Garey and Johnson, W.H.Freeman and Co., San Francisco.
Evaluation method
The student must attend to 2/3 of the given lectures.
Evaluation is based on two seminars per student (presentation, discussion and report) and one test. Each seminar contributs with 40% to the final grade, and the test contributs with 20%.
Grades greater or equal than 10 points lead to approval.
Whenever the grade is more or equal than 18 points, an extra examination might be required. If the student declines it, the final grade of 17 points will be given.