Theoretische Informatik 2 - Berechenbarkeit und Komplexität

Vortragender: Prof. Carsten Lutz

V2Ü2, 4. Semester

Vorlesung: Mo 10-12 MZH 1400

Kurzbeschreibung

Die Theoretische Informatik beschäftigt sich auf systematische Weise und unter Verwendung mathematischer Mittel mit zentralen Fragen der Informatik. Sie besteht aus zahlreichen Teildisziplinen, von denen in dieser Vorlesung hauptsächlich die Theorie der Berechenbarkeit und die Komplexitätstheorie behandelt werden. In der Theorie der Berechenbarkeit geht es um die Definition abstrakter Modelle von Berechnung und um die fundamentale Frage, welche Probleme prinzipiell berechenbar sind und welche nicht. Eine zentrale Rolle spielen dabei Turingmaschinen als elementares Berechnungsmodell, das aber dennoch äquivalent zu komplexeren und praxisnäheren Modellen wie modernen Programmiersprachen ist. Die Komplexitätstheorie betrachtet zusätzlich die zur Berechnung verwendeten Ressourcen wie Laufzeit und Speicherplatz. Eine zentrale Frage ist dann, welche Probleme mit vertretbarem Aufwand berechenbar sind, wobei "vertretbarer Aufwand" meist mit "in polynomieller Zeit" gleichgesetzt wird. Zusätzlich zu den erwähnten Themen werden wir auch einige in Theoretische Informatik 1 offen gebliebene Fragen aus dem Gebiet der formalen Sprachen klären und beispielsweise ein Automatenmodell für kontextsensitive Sprachen und Typ-0 Sprachen angeben. Im letzteren Fall sind das Turingmaschinen, was eine direkte Verbindung zwischen formalen Sprachen und der Theorie der Berechenbarkeit liefert.

Skript

Die Vorlesung wird im wesentlichen die Kapitel III und IV des folgenden Skriptes umfassen. Auf Inhalte, die über das Skript hinausgehen, wird in der Vorlesung explizit hingewiesen. Diese sollten dann mitgeschrieben werden.

Ausgewählte Folien:

Organisation der Tutorien

Es stehen verschiedene Termine für Tutorien zur Auswahl, siehe unten. Die Einschreibung erfolgt über Stud.IP. Die Tutorien beginnen in der 15. Kalenderwoche.

Auf dieser Seite wird jede Woche ein Aufgabenblatt zur Verfügung gestellt. Die Aufgaben werden in den Tutorien gemeinsam gelöst. Jede zweite Woche geben Sie Ihre Lösungen ab. Diese werden dann korrigiert und benotet. Das ist das erste mal in KW 16 der Fall. Die Bearbeitung der Übungsaufgaben erfolgt in Kleingruppen von 2-3 Personen.

Tutor(inn)en

Übungstermine

Aufgabenblätter

Literatur

AG Theorie der künstlichen Intelligenz