Zielstellung

Die Lehrveranstaltung Theoretische Informatik II bietet eine Einführung die Berechenbarkeitstheorie und Komplexitätstheorie.

Während der ersten Hälfte des 20. Jahrhunderts entdeckten Mathematiker wie Kurt Gödel, Alan Turing und Alonzo Church, dass bestimmte grundlegende Probleme nicht mit Computern gelöst werden können. Ein Beispiel für dieses Phänomen ist das Problem, zu bestimmen, ob eine beliebige mathematische Aussage wahr oder falsch ist. Die Beschäftigung mit dieser Frage erforderte die Entwicklung eines präzisen Algorithmenbegriffs. Dieser Begriff ermöglicht es, in der Berechenbarkeitstheorie Fragen nach den prinzipiellen Grenzen von Computern zu untersuchen.

Wo die Berechenbarkeitstheorie nur nach der grundsätzlichen Lösbarkeit von Problemen fragt, ist es das Anliegen der Komplexitätstheorie, Probleme danach zu klassifizieren, ob sie einfach oder aufwändig zu lösen sind. Dazu werden Konzepte entwickelt, mit denen der Schwierigkeitsgrad eines Problems charakterisiert werden kann. Interessanterweise ist die zentrale Frage der Komplexitätstheorie, welche Eigenschaften eines Problems darüber entscheiden, ob das Problem algorithmisch handhabbar ist, bislang weitgehend ungeklärt.

Gliederung der Theoretischen Informatik II

• Berechenbarkeitstheorie
  • Turingmaschinen, Turing-Akzeptierbarkeit vs. Berechenbarkeit
  • Äquivalenz von Berechenbarkeitsmodellen: Rekursive Funktionen, funktionale und logische Programme
    Church-Turing-These
  • Berechenbarkeitstheorie: Grundgesetze, Berechenbarkeit, Aufzählbarkeit und Entscheidbarkeit; Abschlusseigenschaften
  • Beweismethoden für die Unlösbarkeit von Problemen:
    Diagonalisierung, Monotonieargumente, funktionale Reduktion, Satz von Rice
  • Post'sches Korrespondenzproblem, Unentscheidbarkeit von Eigenschaften kontextfreier Grammatiken
• Komplexitätstheorie
  • Zeitkomplexität von Algorithmen und Problemen
  • Komplexitätsklassen P und NP
  • NP-Vollständigkeit und die Nichthandhabbarkeit algorithmischer Probleme
  • Platzkomplexität, PSPACE-Vollständigkeit
  • Probabilistische Algorithmen zur Behandlung nichthandhabbarer Probleme

Lehrveranstaltungen

• In der Vorlesung werden die zentralen Konzepte der theoretischen Informatik vorgestellt und an Beispielen illustriert. Die in der Vorlesung verwendeten Folien werden auf den Servern des Lehrgebiets bereitgestellt.
• Die (Gruppen-)Übungen dienen der Vertiefung und Anwendung der in der Vorlesung vorgestellten Themen. Dies geschieht durch Bearbeitung von ad hoc Übungsaufgaben unter Betreuung von Tutoren, einem 5-Minuten "Quiz" zur Überprüfung eigener Kenntnisse, durch Diskussion von Fragen zur Vorlesung, und durch die Korrektur von Lösungen zu Hausaufgaben. Die Übungsblätter werden wöchentlich herausgegeben.
• Das Tutorium/Hörsaalübung ist eine freiwillige Zusatzveranstaltung, die zur Besprechung allgemeiner Fragen und zur Besprechung der Lösungen komplexerer Hausaufgaben vorgesehen ist.
• Im Kontrast zum Tutorium dienen die Sprechstunden der persönlichen Beratung. Das Ziel ist dabei vor allem Optimierung des individuellen Lernstils und die Klärung von spezifischen Schwierigkeiten.