Teaching

Theoretische Informatik 2: Berechenbarkeit und Komplexität

Vorlesung im Sommersemester 2018


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 mitgeschrieben werden. Hier etwas zum Thema: wie liest man einen mathematischen Text?

Organisation der Tutorien

Nähere Infos zu Terminen, Tutor_innen und Einschreibung gibt es zu gegebener Zeit auf Stud.IP.

Aufgabenblätter

An dieser Stelle In Stud.IP wird jede Woche ein Aufgabenblatt zur Verfügung gestellt. Die Aufgaben werden in Kleingruppen von 2–3 Personen bearbeitet und in den Tutorien gemeinsam besprochen.

Dozent:
Prof. Dr. Tobias Mömke (Email)
Zeit & Raum:

Vorlesung:
Montags 14:00 – 16:00 in Raum NW1 H 1 - H0020
Literatur:
  • Juraj Hromkovič, Theoretische Informatik, Springer Verlag, 2011
  • Michael Sipser, Introduction to Theory of Computation. Cengage Learning, 2013 (3rd edition)
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullmann, Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Pearson Studium, 2011 (3. Auflage)
  • Ingo Wegener, Theoretische Informatik, Teubner-Verlag, 1993
  • Uwe Schöning, Theoretische Informatik - kurzgefaßt, Spektrum Akademischer Verlag, 1999

Valid XHTML 1.0 Transitional