Zur Startseite der Abteilung Theoretische Informatik

Berechenbarkeit und Komplexität (WiSe 2016/17)

Ankündigungen

Die Ergebnisse der Modulprüfung vom Sommersemester 2017 am 23.08.17 hängen aus. Die Einsicht findet am Montag, den 11. September, um 10:00 Uhr statt.

Die Ergebnisse der Modulprüfung hängen aus.

Hinweis zur Modulprüfung:Bei der Raumaufteilung hat sich eine Änderung ergeben. Bitte prüfen Sie regelmäßig vor der Prüfung beim Prüfungsamt, ob sich andere Änderungen ergeben.

Mittlerweile hängt die endgültige Scheinliste aus. Bitte prüfen Sie, ob Ihre Matrikelnummer darauf aufgeführt ist. Bitte überprüfen Sie dies auch, wenn Sie davon ausgehen, dass Sie den Schein nicht erhalten haben.

Am Montag, den 20. Februar 2017 um 14:00 Uhr in V 38.03 findet eine Fragestunde zur Modulprüfung statt.

Alle, die die anderen Scheinkriterien erfüllt haben, in der Scheinklausur jedoch weniger als 8,5 Punkte erreicht haben, können am 03. April 2017 um 14:00 Uhr in Raum 0.108 an einer Nachhol-Scheinklausur teilnehmen.

Vorlesung

Prof. Dr. Volker Diekert

Lernziele

Die Teilnehmer beherrschen wichtige theoretische Grundlagen der Informatik und können Probleme in Kategorien einordnen wie entscheidbar/unentscheidbar oder effizient lösbar (durch deterministische/nichtdeterministische Berechnungen).

Termine

Zeit Raum Termine
Mo 17:30–19:00 V38.04 Die erste Vorlesung findet am 17.10.16 statt.
Di 15:45–17:15 V38.04  

Am Montag, den 05. Dezember findet keine Vorlesung statt.

Am Dienstag, den 13. Dezember findet keine Vorlesung statt.

Am Dienstag, den 20. Dezember findet keine Vorlesung statt.

Am 17. Januar findet die Lehrveranstaltungsbefragung in der Vorlesung statt.

Am Montag, den 23. Januar entfällt die Vorlesung krankheitsbedingt!

Am Montag, den 30. Januar findet keine Vorlesung statt.

Am Montag, den 06. Februar findet keine Vorlesung statt.

Scheinklausur

Die Ergebnisse der Scheinklausur stehen im eClaus-System unter Aufgabenblatt 10 zur Verfügung.

Die Scheinklausur findet am 07. Februar während des normalen Vorlesungstermins in Raum V 38.04 statt.

Wenn Sie an der Scheinklausur teilnehmen möchten, melden Sie sich bitte bis spätestens Freitag, den 27. Januar 2017 um 14:00 Uhr (kurz nach der Abgabe von Blatt 6) über Aufgabenblatt 10 im eClaus-System an. Wenn Sie sich unsicher sind, ob Sie an der Scheinklausur teilnehmen möchten, melden Sie sich bitte trotzdem dazu an.

Die Scheinklausur wird eine Multiple-Choice-Klausur sein,

Inhalt

Gleichwertigkeit der verschiedenden Konkretisierungen des Algorithmenbegriffs, Churchsche These, Grenzen zwischen Entscheidbarbkeit und Unentscheidbarkeit. Turing-Berechenbarkeit, Halteproblem, Satz von Rice. Wichtige Komplexitätsklassen, P-NP-Problem, NP-Vollständigkeit, Satz von Cook.

Woche Inhalt
1 Berechenbarkeitstheorie: Diagonalisierung (Cantor-Verfahren), Nichtexistenz der Menge aller Mengen, Unentscheidbarkeit des Halteproblems, Fleißige Biber: 1. Existenz unberechenbarer, totaler Funktionen (Java-Biber) 2. Existenz berechenbarer, aber nicht loop-berechenbarer Funktionen (primitive Biber)
2 entscheidbar, aufzählbar, L entscheidbar ⇔ L und Komplement von L aufzählbar, Satz von Rice (entscheidbar, aufzählbar)
3 Postsches Korrespondenz-Problem, Universalität kontextfreier Sprachen
4 Chinesischer Restsatz, Syntax und Semantik von Imp, arithmetische Formeln und arithmetische Darstellungen, Gödelsches β-Prädikat, arithmetische Darstellung berechenbarer Funktionen, Beweissysteme (korrekt, konsistent, vollständig), Herleitungen
5 Gödelscher Unvollständigkeitssatz, Komplexitätstheorie: XTIME, XSPACE, Komplexitätsklassen von L bis PSPACE, Polynomialzeitreduktionen
6 Einfache Sätze zu den Beziehungen zwischen Komplexitätsklassen, Band-Kompression, Satz von Savitch, Satz von Immerman/Szelepcsényi, Hierarchiesätze (Platzhierarchie)
7 Lückensatz von Borodin, NP-Vollständigkeit, Satz von Cook/Levin
8 Fluchtweg bei Feueralarm*
9 HORNSAT ist P-vollständig; KNF ∩ SAT, 3-SAT, NAE-SAT sind NP-vollständig; ILP ist NP-schwierig
10 Transitivität von logspace-Reduktionen; NL-Vollständigkeit von 2-SAT und GAP; NP-Vollständigkeit von Vertex Cover
11
12
Weihnachtsferien*
13 NP-Vollständigkeit von 3-Färbbarkeit und Hamilton-Kreis; Mengen zwischen P und NP; dünne Mengen und Satz von Mahaney*; P-Vollständigkeit der Leerheit kontextfreier Sprachen und von Straight Line Programmen; P-Vollständigkeit des Auswertungsproblems von (monotonen und nicht monotonen) Schaltkreisen
14 QBF ist PSPACE-Vollständig
15
16
Monotone Schaltkreise und Satz von Rasborow*
17 Scheinklausur

 Die mit * gekennzeichneten Inhalte sind nicht prüfungsrelevant.

Skript

Übungen

Jan Philipp Wächter

Die Anmeldung zu den Übungen erfolgt über das eClaus-System https://eclaus.informatik.uni-stuttgart.de/. Benutzername und Passwort werden in der ersten Vorlesung bekannt gegeben.

Weitere Informationen zum Übungsbetrieb finden sich auf Blatt 0.

Hinweise

  • Um an der Modulprüfung "Berechenbarkeit und Komplexität" teilzunehmen, benötigen Sie den Übungsschein dieser Veranstaltung.
  • Falls Sie einen benoteten Schein benötigen (z.B. Lehramt oder Nebenfach), melden Sie sich bitte beim Übungsleiter.

Scheinkriterien

Einen Schein erhält, wer

  • die Scheinklausur bestanden,
  • ≥ 50% der Punkte aus den schriftlichen Abgaben erreicht und
  • mindestens einmal in seiner Übungsgruppe vorgerechnet hat.

Übungsgruppen

Hinweis: In der wöchentlich stattfindenden Übungsgruppe 4 werden die Übungen langsamer besprochen.

Theo, der fleißige FMI-Biber Theo, der fleißige FMI-Biber, hilft Ihnen beim Finden des richtigen Abgabekastens.

Gr. Tutor Zeit Raum Besprechung
Blatt 0 Blatt 1 Blatt 2 Blatt 3 Blatt 4 Blatt 5 Blatt 6
1 Theo, der fleißige FMI-Biber
J. Wächter
Mi. 15:45-17:15 0.457 26.10. 09.11. 23.11. 07.12. 21.12. 18.01. 08.02.
2 Theo, der fleißige FMI-Biber
J. Liedtke
Do. 15:45-17:15 0.457 27.10. 10.11. 24.11. 08.12. 22.12. 19.01. 02.02,
3 Theo, der fleißige FMI-Biber
J. Stadelmaier
Fr. 09:45-11:15 0.108 28.10. 11.11. 25.11. 09.12. 13.01.
(0.453)
20.01. 03.02.
4 Theo, der fleißige FMI-Biber
J. Stadelmaier
Fr. 11:30-13:00 0.363 28.10. &
04.11.
11.11. &
18.11.
25.11. &
02.12.
09.12. &
16.12.
13.01. 20.01. &
27.01.
03.02. &
10.02.
5 Theo, der fleißige FMI-Biber
J. Liedtke
Do. 15:45-17:15 0.457 03.11. 17.11. 01.12. 15.12. 12.01. 26.01. 09.02.
6 Theo, der fleißige FMI-Biber
J. Stadelmaier
Fr. 09:45-11:15 0.453 04.11. 18.11. 02.12. 16.12. 13.01. 27.01. 10.02.

Ausnahmen:

Der 23.12. ist vorlesungsfrei. Daher entfallen die entsprechenden Termine für Übungsgruppe 3 und 4. In Übungsgruppe 4 wird Blatt 4 nur an einem Termin besprochen. Teilnehmer von Übungsgruppe 3 können den entsprechenden Termin für Übungsgruppe 6 besuchen.

Übungsblätter

  • Blatt 0 (ohne Abgabe, Besprechung in der ersten Übungsgruppe)
  • Blatt 1
  • Blatt 2 geändert: Hinweise zur Bearbeitung eingefügt.
  • Blatt 3 geändert: H statt K in Aufgabe 2, Definitionen der Sprachen in Aufgabe 2 geändert
  • Blatt 4 (Vorschau-Aufgabe geändert)
  • Blatt 5 geändert: Zusätzliche Konstante bei 3 b) (i), 2. Änderung: Weihnachtsaufgabe präzisiert
  • Blatt 6

Hinweis: Die Aufgaben 3 a) und 4 von Blatt 4 werden nach Weihnachten in den Ergänzungen besprochen.

Simulator für die Turingmaschinen von Blatt 0, Aufgabe 1 (externe Links!):

  1. Palindrome
  2. Inkrementierung
  3. ähnlich zum Beispiel für die Addition zweier Binärzahlen von turingmachinesimulator.com

Die Ergebnisse der Abstimmung über den beliebtesten Biber-Fakt stehen hier zur Verfügung.

Ergänzungen

Julian Liedtke

Zeit: Do 17:30 — 19:00

Raum: V38.03

Folien

Erster Termin: 27.10.

Krankheitsbedingt findet am 12.01.17 keine Ergänzung statt.

Literatur

Die Vorlesung baut im Wesentlichen auf dem Buch von Uwe Schöning und dem Skript zur Komplexitätstheorie von Volker Diekert auf:


Zur weiterführenden Lektüre sei empfohlen:

  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Addison-Wesley, 2002.
  • Christos Papadimitriou: Computational Complexity. Addison-Wesley, 1994.