3 ECTS credits
75 h study time
Offer 1 with catalog number 4021170FNR 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:
Written Exam determines 100% of the final mark.
Within the Written Exam category, the following assignments need to be completed:
There is a written final exam. There are 2 theoretical questions marked on 6 points each and there are 2 exercises marked on 4 points each. These exercises are similar to but different from the exercises seen during the course.
This offer is part of the following study plans:
Master in Applied Sciences and Engineering: Computer Science: Artificial Intelligence (only offered in Dutch)
Master in Applied Sciences and Engineering: Computer Science: Multimedia (only offered in Dutch)
Master in Applied Sciences and Engineering: Computer Science: Software Languages and Software Engineering (only offered in Dutch)
Master in Applied Sciences and Engineering: Computer Science: Data Management and Analytics (only offered in Dutch)
Master of Teaching in Science and Technology: computerwetenschappen (120 ECTS, Etterbeek) (only offered in Dutch)