Theoretische Informatik 2 – Berechenbarkeit und Komplexität

Vortragender: Prof. Dr. Thomas Schneider

V2Ü2, 4. Semester

Vorlesung: Mo 14–16 NW1 H1 H0020

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 Skriptes von Prof. Dr. Carsten Lutz umfassen. Auf Inhalte, die über das Skript hinausgehen, wird in der Vorlesung explizit hingewiesen. Diese sollten dann mitgeschrieben werden.

Errata zum Skript, Stand 11.7.2016

Organisation der Tutorien

Es stehen verschiedene Termine für Tutorien zur Auswahl, siehe unten. Die Einschreibung wird zu gegebener Zeit über Stud.IP stattfinden. Die Tutorien beginnen voraussichtlich in der 15. Kalenderwoche (ab 11.4.).

Tutor(inn)en

Übungstermine

Tutorium    Ort    Tutor(in)
Di. 10–12 MZH 1110 Leif Sabellek
Di. 14–16 MZH 1100 Jan Mantei
Mi. 8–10 MZH 1110 Jean Christoph Jung
Mi. 12–14 MZH 1100 Arved Friedemann
Do. 10–12 MZH 1460 Leif Sabellek
Do. 16–18 MZH 1110 Alicia Pagel

Aufgabenblätter

Die Aufgabenblätter werden ab jetzt im Stud.IP zur Verfügung gestellt.

Literatur

AG Theorie der künstlichen Intelligenz   11. Jul. 2016  Thomas Schneider
Valid HTML 4.0 Transitional