Semesterwochenstunden 4 Vorlesung + 2 Übung
ECTS-Punkte 9

Ziele

Die Studierenden kennen verschiedene Rechenmodelle und ihre relativen Stärken und Mächtigkeiten. Sie können für ausgewählte Probleme zeigen, ob diese in bestimmten Rechenmodellen lösbar sind oder nicht. Sie verstehen den formalen Begriff der Berechenbarkeit wie auch der Nicht-Berechenbarkeit. Sie können Probleme aufeinander reduzieren.

Sie sind vertraut mit den Grundzügen der Ressourcenbeschränkung (Zeit, Platz) für Berechnungen und der sich daraus ergebenden Komplexitätstheorie.

Inhalt

  • Die Sprachen der Chomsky Hierarchie und ihre verschiedenen Definitionen über Grammatiken und Automaten; Abschlusseigenschaften; Klassifikation von bestimmten Sprachen („Pumping lemmas“); Determinismus und Nicht-Determinismus;
  • Turing Maschinen und äquivalente Modelle von allgemeiner Berechenbarkeit (z.B. μ-rekursive Funktionen, Random Access Machines)
  • Reduzierbarkeit, Entscheidbarkeit, Nicht-Entscheidbarkeit;
  • Die Komplexitätsmaße Zeit und Platz; die Komplexitätsklassen P und NP; Grundzüge der Theorie der NP-Vollständigkeit