3 ECTS credits
75 u studietijd
Aanbieding 1 met studiegidsnummer 4021173FNR voor alle studenten in het 1e semester met een gespecialiseerd master niveau.
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.
De beoordeling bestaat uit volgende opdrachtcategorieën:
Examen Schriftelijk bepaalt 100% van het eindcijfer
Binnen de categorie Examen Schriftelijk dient men volgende opdrachten af te werken:
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.
Deze aanbieding maakt deel uit van de volgende studieplannen:
Master in Applied Sciences and Engineering: Computer Science: Artificial Intelligence (enkel aangeboden in het Engels)
Master in Applied Sciences and Engineering: Computer Science: Multimedia (enkel aangeboden in het Engels)
Master in Applied Sciences and Engineering: Computer Science: Software Languages and Software Engineering (enkel aangeboden in het Engels)
Master in Applied Sciences and Engineering: Computer Science: Multimedia for Northwestern Polytechnical University (NPU) (enkel aangeboden in het Engels)
Master in Applied Sciences and Engineering: Computer Science: Data Management and Analytics (enkel aangeboden in het Engels)