Theory of Computing: Computability and Complexity
Author: | Prof. Dr. Andreas Schäfer | ||
Offering Institution: | Technische Hochschule Lübeck |
||
Course Language: | English | ||
Field of Knowledge: | Information Systems | Free of Charge | |
Average Workload: | 50 Hours | Free of Charge | Enrol |
What can you learn in this course?
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.
Outline
- Organization
- Turing machines
- Undecideable Problems
- Semi-decideable Problems
- Time Complexity
- Space Complexity
Further authors
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.