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
- Turing machines
- Church-Turing thesis
- Decidability
- Halting problem
- Reducibility
- Recursion theorem
2. Complexity theory
- Time complexity and the classes P and NP
- NP-completeness and the Cook-Levin theorem
- Other NP-complete problems
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 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 Languages and Software Engineering
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