Theory of Computing III: Computability and Complexity
Was können Sie in diesem Kurs lernen?
With the help of this course, we want you to achieve the following learning outcomes:
- You can describe basic principles of Turing machines.
- You can discuss the problem of undecidability and name multiple examples.
- You can distinguish between undecidable and semi-decidable problems.
- You can describe the idea of the time complexity classes P and NP.
- You can elaborate on the basic idea of space complexity.
Gliederung
- Organization
- Turing machines
- Undecideable Problems
- Semi-decideable Problems
- Time Complexity
- Space Complexity
Autoren*innen
Prof. Dr. Andreas Schäfer
Andreas Schäfer received his PhD 2007 from the Carl von Ossietzky University in Oldenburg, Germany.
He then worked at the European Patent Office for 5 years. Since 2012 he is Professor of Computer
Science at the Technische Hochschule Lübeck. His interests include Automata Theory, Logic and Formal Methods.