Computation & Information Theory
Teachers
Professor: Bernard Manderick (Computation Theory) and Leo van Biesen (Information Theory)
Teaching Assistant: David Catteeuw (Computation Theory)
Goal (computation theory part)
To introduce the basic concepts of the theory of computation in particular the theory of (undecidable) problems and the several complexity classes and to show the relevance of this theory for the computer science practice.
Prerequisites
BA computer science or BA mathematics option computer science or equivalent.
Content
- Undecidability
- A Language That Is Not Recursively Enumerable
- An Undecidable Problem That Is Recursively Enumerable
- Undecidable Problems About Turing Machines
- Post’s Correspondence Problem
- Other Undecidable Problems
- Intractable Problems
- The Classes P and NP
- An NP-Complete Problem
- A Restricted Satisfiability Problem
- Additional NP-Complete Problems
Course Material
Sipser, M. Introduction to the Theory of Computation, Course Technology, 2nd edition, 2005.
You can find additional material, such as exercises, on the PointCarré website of this course: VUB14134.
Supplementary Material
- Chapters 9 and 10 of Hopcroft, J.E., Motwani, R. and J.D. Ulmann Introduction to Automata theory, Languages and Computation, 3rd edition, Addison-Wesley, 2006.
- Hofstadter, D.R. Gödel, Escher, Bach: an Eternal Golden Braid, The Harvester Press, 1979.
Exam
The final grade depends 50% on Computation Theory and 50% on Information Theory.
The exam of Computation Theory is written and closed book.
