Theoretische Informatik 2 - Berechenbarkeit und Komplexität
Vortragender: Prof. Carsten Lutz
V2Ü2, 4. Semester
Vorlesung: wöchentlich Mo 10-12 MZH 1380/1400
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 (zuletzt aktualisiert
am 2.5.2013). Auf Inhalte, die
über das Skript hinausgehen, wird in der Vorlesung explizit
hingewiesen. Diese sollten dann mitgeschrieben werden. Hier sind
die Folien aus der Einführungsveranstaltung.
Und hier der Einschub zur Logik (inkl. Horn-Formeln,
die nicht im Skript sind).
Organisation der Tutorien
Es stehen verschiedene Termine für Tutorien zur Auswahl, siehe unten.
Die Einschreibung erfolgt über Stud.IP.
Die Tutorien beginnen in der 16. Kalenderwoche.
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 ab.
Diese werden dann korrigiert und benotet. Das ist
das erste mal in KW 16 der Fall. Die Bearbeitung der
Übungsaufgaben erfolgt in Kleingruppen von 2-3 Personen.
Tutor(inn)en
Übungstermine
Aufgabenblätter
- Ungewertetes Blatt 1
(PDF)
(PS)
(Besprechung KW 16)
- Gewertetes Blatt 1
(PDF)
(PS)
(Besprechung KW 17)
- Ungewertetes Blatt 2
(PDF)
(PS)
(Besprechung KW 18)
- Gewertetes Blatt 2
(PDF)
(PS)
(Besprechung KW 19) Aufgaben 3c) und 3e) wurden aktualisiert, Do. 2.5. 19:50
- Ungewertetes Blatt 3
(PDF)
(PS)
(Besprechung KW 20)
- Gewertetes Blatt 3
(PDF)
(PS)
(Besprechung KW 21)
Bitte geben Sie dieses Aufgabenblatt bis Di., den 21.5.2013, 9.00 ab, entweder (ausnahmsweise) elektronisch per Mail oder ins Postfach Ihrer Tutorin/Ihres Tutors
- Ungewertetes Blatt 4
(PDF)
(PS)
(Besprechung KW 22)
- Gewertetes Blatt 4
(PDF)
(PS)
(Besprechung KW 23)
- Ungewertetes Blatt 5
(PDF)
(PS)
(Besprechung KW 24)
- Gewertetes Blatt 5
(PDF)
(PS)
(Besprechung KW 25)
- Ungewertetes Blatt 6
(PDF)
(PS)
(Besprechung KW 26)
- Gewertetes Blatt 6
(PDF)
(PS)
(Besprechung KW 27)
Literatur
- Dexter Kozen, Automata and Computability, Springer Verlag, 2007
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullmann,
Introduction to Automata Theory, Languages, and Computation, Addison
Wesley, 2006 (3rd edition)
- Uwe Schöning, Theoretische Informatik - kurzgefaßt,
Spektrum Akademischer Verlag, 1999
- Ingo Wegener, Theoretische Informatik, Teubner-Verlag, 1993
AG Theorie der künstlichen Intelligenz