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

... werden zu gegebener Zeit in Stud.IP zugänglich gemacht.

Auf Inhalte, die über das Skript hinausgehen, wird in der Vorlesung explizit hingewiesen. Diese sollten dann mitgeschriben werden. Hier etwas zum Thema: wie liest man einen mathematischen Text?

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 in der zweiten Vorlesungswoche (ab 10.04.17). Es stehen die folgenden Termine für Tutorien zur Auswahl.

Aufgabenblätter

Im Stud.IP wird jeden Freitag ein Aufgabenblatt zur Verfügung gestellt. Die Aufgaben werden in Kleingruppen von 2–3 Personen bearbeitet und in den Tutorien gemeinsam besprochen. Ab dem zweiten Aufgabenblatt gibt es auch gewertete Aufgaben, deren Lösungen jeweils bis Montag 14:00 Uhr in das entsprechende Fach im Erdgeschoss des Cartesiums zur Korrektur abzugeben sind.

Literatur

Dexter Kozen: Automata and Computability. Springer Verlag, 2007
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullmann, Introduction to Automata Theory, Languages, and Computation (3rd edition). Pearson Education, 2014 (dt. Version von Pearson Studium 2011)
Uwe Schöning, Theoretische Informatik - kurzgefasst, Spektrum Akademischer Verlag, 2008
Ingo Wegener, Theoretische Informatik, Teubner, 2005

AG Theorie der künstlichen Intelligenz 23. Mar 2017 Jean Christoph Jung