Theory of Computing III: Computability and Complexity

Autor*innen: Prof. Dr. Andreas Schäfer
Anbietende Hochschule: Technische Hochschule Lübeck
Kurssprache: Englisch
Wissensgebiet: Wirtschaftsinformatik Kostenfrei
Durchschnittlicher Arbeitsaufwand: 50 Stunden Kostenfrei Einschreiben
teilen
tweeten
teilen
teilen
teilen
teilen

Was erwartet Sie in diesem Kurs?

Formal Languages and Automata provide the basis for analyzing user input from addresses in web forms to complex Java code. This 3-part course provides the basics of the theory. It also shows the limits of each machine model and finally the limits of computability in general.

This course, building on the previous two, discusses Turing machines and problems of decidability 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
  • Undecidable Problems
  • Semi-decidable 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. 


Lizenz

Creative Commons