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

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

Vorlesungstermin: Fr 08:00 Uhr - 09:15 Uhr, HS 6

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. In diesem Semester handelt es sich um ein Notprogramm für alle neuen Masterstudierenden, die das unbedingt schon im 1. Semester bestehen müssen. In Zukunft wird es auch noch eine Übung dazu geben. Diese ist in diesem Semester in die Vorlesung integriert.

Aber auch Studierende aus älteren Studienordnungen sind willkommen. Diese müssen allerdings eine Prüfung gemeinsam mit Algorithmik ablegen, welche immer im Sommersemester angeboten wird und im Verhältnis 1:2 (BK:Alg) gewertet wird. Berechenbarkeit und Komplexität wird als Teil des neuen Moduls Berechenbarkeit/Verifikation dagegen zusammen mit der Vorlesung Formale Spezifikation und Verifikation immer im Winter angeboten.

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 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 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