3 ECTS credits
75 h study time
Offer 1 with catalog number 4021173FNR for all students in the 1st semester at a (F) Master - specialised level.
1. Computability theory
- Recall: Turing Machines, Decidability and the Halting Problem
- Reducibility
- Recursion Theorem
2. Complexity theory
- Time complexity
+ the classes P and NP
+ NP-completeness and the Cook-Levin theorem
+ Other NP-complete problems
- Space Complexity
+ Savitch's Theorem
+ PSPACE and PSPACE-completeness
+ The classes L and NL
This course is based on the book
Introduction to the theory of computation (third edition) by Michael Sipser
Additional material:
1. Chapters 9 and 10 of Hopcroft, J.E., Motwani, R. and J.D. Ulmann, Introduction to Automata theory, Languages and Computation, 3rd edetion, Addison-Wesley, 2006.
2. Parts IV and V and the Appendices G–N of Rich, E. Automata, Computability and Complexity: Theory and Applications, Prentice-Hall, 2007.
3. Hofstadter, D.R. (1979) Godel, Escher, Bach: an Eternal Golden Braid, The Harvester Press, 1979.
To introduce the basic concepts of the theory of computation and complexity theory and to show the relevance of this theory for a computer scientist.
• Knowledge and insight: After successful completion of the course the student should have insight into which problems and functions can in principle be solved or computed and which ones cannot. (S)he also will have insight in how efficiently computable problems can be computed and how to classify such problems into the different complexity classes.
• Use of knowledge and insight: The student should be able to solve computability and complexity problems (s)he encounters in practice.
• Judgement ability: The student should also be able to understand and apply the available techniques to shown that a problem is computable or not and when it is computable to which complexity class the problem belongs.
• Communication: The student should be able to communicate with experts when studying the computational and complexity aspects of problems.
• Skills: The student should be able to state formally a problem, to prove that statement and to show some creativity in finding that proof.
The final grade is composed based on the following categories:
Oral Exam determines 60% of the final mark.
Written Exam determines 40% of the final mark.
Within the Oral Exam category, the following assignments need to be completed:
Within the Written Exam category, the following assignments need to be completed:
There is a written exercise exam (40% of the points) and an oral theory exam (60% of the points). Both exams are closed-book.
The exercises on the written exam are similar, but not identical, to those covered during the exercise sessions.
In the theory exam, students make a written preparation in which they write out their full answer so that it is readable for the professor. During the oral discussion, they are asked to further explain parts of their written preparation.
Not attending either exam will result in a grade of "Absent" for the entire course. If students obtain a grade of 10/20 or higher on either exam in the first exam period, that partial grade is carried over to the second exam period. However, there is no transfer of grades to the next academic year.
This offer is part of the following study plans:
Master of Applied Sciences and Engineering: Computer Science: Artificial Intelligence
Master of Applied Sciences and Engineering: Computer Science: Multimedia
Master of Applied Sciences and Engineering: Computer Science: Software Systems
Master of Applied Sciences and Engineering: Computer Science: Multimedia for Northwestern Polytechnical University (NPU)
Master of Applied Sciences and Engineering: Computer Science: Data Management and Analytics