Dieser Vorlesungsteil orientiert sich an der bisher eigenständigen Vorlesung von Prof. Lang. Im Gegensatz zum Teil Algorithmik wird der Teil Berechenbarkeit auch in diesem Semester auf Deutsch gehalten.

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.

Entsprechend der noch zur Verfügung stehenden Zeit werden noch algorithmische Techniken vorgestellt und die Verfahren des Vorlesungsteils Algorithmik darin eingeordnet.

Dieser Vorlesungsteil richtet sich größtenteils nach einem Foliensatz, der von meinem Vorgänger Prof. Lang eingerichtet 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 die von Prof. Lang für diesen Teil zur Verfügung gestellten Unterlagen eingerichtet. Es gibt zusätzlich 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.

Der Foliensatz wird von mir mit pdf-Kommentaren versehen, die im Laufe der Vorlesung ergänzt werden.

Die grobe Gliederung dieses Vorlesungsteils entspricht auch der des Foliensatzes:

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

3. Komplexitätstheorie

4. Lösungsstrategien für Algorithmen mit Beispielen
    (optional je nach verfügbarer Zeit)

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