Theoretische Informatik 2 - Berechenbarkeit und Komplexität

Prof. Carsten Lutz

V2Ü2, 4. Semester

Vorlesung: wöchentlich Mo 14-16 HS1010

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 (letztes Update am 30.6.2015). Auf Inhalte, die über das Skript hinausgehen, wird in der Vorlesung explizit hingewiesen. Diese sollten dann mitgeschrieben werden.

Video-Vorlesung

Hier findet man die Vorlesung als "mobile lecture".

Organisation der Tutorien

Es stehen verschiedene Termine für Tutorien zur Auswahl, siehe unten. Die Einschreibung erfolgt über Stud.IP. Die Tutorien beginnen ab 20.4.

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 bis Montag 16:00 ab (ins Postfach Ihres Tutors). Die abgegebenen Lösungen werden korrigiert und benotet. Die erste Abgabe ist am 27.4. Die Bearbeitung der Übungsaufgaben erfolgt in Kleingruppen von 2-3 Personen.

Tutor(inn)en

Übungstermine

Tutorium    Ort    Tutor(in)
Mo. 16–18 MZH 5210 Dr. Sabine Kuske
Di. 10–12 MZH 1110 Christopher Nottrodt
Mi. 8–10 MZH 1470 M.Sc. Peter Hansen
Mi. 10–12 MZH 1460 Dr. Jean Christoph Jung
Mi. 12–14 MZH 5210 Leif Sabellek
Do. 10–12 MZH 1100 Dr. Jean Christoph Jung

Aufgabenblätter

Literatur

AG Theorie der künstlichen Intelligenz