Hörerkreis:
Masterstudiengänge Informatik und IT-Sicherheit als Teil des Moduls Berechenbarkeit/Verifikation

Arbeitsaufwand: 2,5 ECTS-Punkte (für diesen Modulteil)

Vorlesungs- und Übungstermin: wird bekanntgegeben nach Veröffentlichung des Stundenplans

Der Übungstermin ist im Wechsel mit Formale Spezifikation und Verifikation, die zum selben Modul gehört, also zusammen mit dieser Vorlesung geprüft werden muss. Es wird von Woche zu Woche entschieden, welcher Vorlesungsteil den Übungstermin bekommt und in den jeweiligen Vorlesungen angesagt. Der erste Übungstermin wird für Berechenbarkeit wahrgenommen.

Diese Vorlesung orientiert sich an der bisher eigenständigen Vorlesung von Prof. Lang. Sie ist allerdings deutlich komprimierter, denn sie besteht nur aus 2 SWS, wobei die Übung - wie oben beschrieben - ausgelagert worden ist, was wieder etwas mehr Zeit verschafft.

Berechenbarkeit untersucht, ob ein Problem durch einen Computer überhaupt berechnet werden kann. Dazu ist es erforderlich, die Begriffe Problem, Algorithmus und Computer mathematisch zu formalisieren. Im Zentrum steht das Konzept der Turingmaschine. Erst damit kann bewiesen werden, dass es überhaupt Probleme geben kann, die nicht berechenbar sind. Der Nachweis der Nichtberechenbarkeit für einzelne Probleme ist meistens sehr schwierig. Wir werden diese Eigenschaft aber für einige Probleme zeigen.

Für berechenbare Probleme wird die Komplexität als Maß für ihre Schwierigkeit definiert. Auch diese Definition verwendet das Konzept der Turingmaschine. Die zentrale Frage, die in der Komplexitätstheorie und damit auch in dieser Vorlesung gestellt wird, besteht darin, ob ein Problem in polynomialer Zeit gelöst werden kann (was als effizient gilt) oder nicht. Diese Fragestellung ist für viele Probleme nicht gelöst. Als Charakterisierung für derartige Probleme gibt es die Klasse der NP-vollständigen Probleme, welche in dieser Vorlesung ebenfalls eingehend untersucht wird.

Dieser Vorlesungsteil richtet sich größtenteils nach einem Foliensatz, der von meinem Vorgänger Prof. Lang eingerichtet und von mir im Laufe der letzten Jahre überarbeitet wurde. Die Vorlesung wird anhand dieser Folien gehalten und an einigen Stellen an der Tafel vertieft.

Auf dem Handout-Server ist ein extra Bereich für zur Verfügung gestellten Unterlagen eingerichtet. Es gibt außer dem erwähnten Foliensatz noch ein Skript zur Theoretischen Informatik, von dem für diesen Vorlesungsteil nur die Kapitel 3 - 6 relevant sind. Die Kapitel 1 und 2 beziehen sich auf die Bachelorvorlesung Automaten und Formale Sprachen. Deren Inhalt wird für diese Vorlesung aber nicht benötigt. Wöchentlich werden Aufgaben formuliert, welche den jeweils durchgenommenen Stoff wiederholen und vertiefen. Diese Aufgaben werden in den Übungen besprochen.

Die grobe Gliederung dieses Vorlesung entspricht auch der des Foliensatzes:

2. Berechenbarkeit und Nichtberechenbarkeit von Problemen
    (mit Formalisierung über Turingmaschinen)

3. Komplexitätstheorie

Alle aufgeführten Bücher enthalten auch das mit Berechenbarkeit eng verwandte Gebiet der Automaten und Formalen Sprachen. Die Vorlesung wird aber so gehalten, dass Vorkenntnisse aus diesem Gebiet nicht vorausgesetzt werden.

John E. Hopcroft / Rajeev Motwani / Jeffrey D. Ullman: Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit, Pearson Studium 2011 (3. Aufl.), ISBN 978-3-86894-082-4
(in unserer Bibliothek befinden sich auch ältere Auflagen, darunter auch das englischsprachige Original von 1979)

Juraj Hromkovic: Theoretische Informatik, Teubner 2007 (3. Aufl.), ISBN 978-3-8351-0043-5
(in unserer Bibliothek befinden sich auch ältere Auflagen)

Rainer Lang: Theoretische Informatik, FH Wedel 2011, Skript (auf Handoutserver)

Gottfried Vossen / Karl-Ulrich Witt: Grundkurs Theoretische Informatik, Vieweg 2006 (4. Aufl.), ISBN 978-3-8348-0153-1