Theoretische Informatik 2 – Berechenbarkeit und Komplexität, SoSe 2019
Vortragender: Prof. Dr. Thomas Schneider
V2Ü2, 4. Semester
Vorlesung: Do 12–14 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 Veranstaltungsverzeichnis.
Die Einschreibung wird zu gegebener Zeit über Stud.IP stattfinden.
Die Tutorien beginnen voraussichtlich in der zweiten Vorlesungswoche (ab 8. 4. 17).
Aufgabenblätter
... werden auch über Stud.IP zur Verfügung gestellt werden.
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
8. Feb 2019
Thomas Schneider
