■
Team
■
Teaching
Oberseminar der Theorie
■
Winter 2023
■
Summer 2023
■
Winter 2022
■
Summer 2022
■
Winter 2021
■
Summer 2021
■
Winter 2020
■
Summer 2020
■
Winter 2019
■
Summer 2019
■
Winter 2018
■
Summer 2018
■
Winter 2017
■
Summer 2017
■
Winter 2016
Algorithmische Gruppentheorie
Ausgewählte Themen der Theoretischen Informatik
Berechenbarkeit und Komplexität
Ergänzungen zu Mathematik I
Formale Sprachen und Automatentheorie
Quantencomputing
■
Summer 2016
■
Winter 2015
■
Summer 2015
■
Winter 2014
■
Summer 2014
■
Winter 2013
■
Summer 2013
■
Winter 2012
■
Summer 2012
■
Winter 2011
Former Semester
BSc, Master-, Student-, Diplomathesis
StuPro/ ProjektINF/ SoPra/ FaPra
Exam Archive
Standard Textbooks
Descriptive Theory
■
Research
■
Publications
 

Berechenbarkeit und Komplexität

Ankündigungen

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:

  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.

News

[Jun’23] The paper “Parallel algorithms for power circuits and the word problem of the Baumslag group” by Caroline Mattes and Armin Weiß has been accepted at Computational Complexity.

[Oct’22] The paper “Lower Bounds for Sorting 16, 17, and 18 Elements” by Florian Stober and Armin Weiß has been accepted at ALENEX 2023.

[Sep’22] The paper “Conelikes and Ranker Comparisons” by Viktor Henriksson and Manfred Kufleitner has been accepted at LATIN 2022.

[Sep’22] The paper “Improved Parallel Algorithms for Generalized Baumslag Groups” by Caroline Mattes and Armin Weiß has been accepted at LATIN 2022.

[Apr’22] The paper “Reachability Games and Parity Games” by Volker Diekert and Manfred Kufleitner has been accepted at ICTAC 2022.

[Apr’22] The paper “Satisfiability Problems for Finite Groups” by Pawel M. Idziak, Piotr Kawalek, Jacek Krzaczkowski and Armin Weiß has been accepted at ICALP 2022.

[Mar’22] The paper “The Power Word Problem in Graph Products” by Florian Stober and Armin Weiß was accepted at DLT 2022.

[Nov’20] Volker Diekert is Partner Investigator in the Australian ARC grant “Geodetic groups: foundational problems in algebra and computer science” at University of Technology Sydney.

[Apr’20] The paper “Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems” by Laurent Bartholdi, Michael Figelius, Markus Lohrey and Armin Weiß has been accepted at CCC 2020.

[Apr’20] The paper “Hardness of equations over finite solvable groups under the exponential time hypothesis” by Armin Weiß has been accepted at ICALP 2020.

[Dec’19] The paper “An Automaton Group with PSPACE-Complete Word Problem” by Jan Philipp Wächter and Armin Weiß has been accepted at STACS 2020.

[Nov’19] Carlos Camino was awarded the stuvus Special Prize for exceptional commitment in teaching.

[Jun’19] The paper “The power word problem” by Markus Lohrey and Armin Weiß has been accepted at MFCS 2019.

[May’19] The paper “On the Average Case of MergeInsertion” by Florian Stober and Armin Weiß has been accepted at IWOCA 2019.

[Oct’18] The paper “Worst-Case Efficient Sorting with QuickMergesort” by Stefan Edelkamp and Armin Weiß has been accepted at ALENEX 2019.

[Jun’18] At CCC 2018, Lukas Fleischer received a Best Student Paper Award for his submission “On the Complexity of the Cayley Semigroup Membership Problem”.

[Jun’18] The paper “Testing Simon’s congruence” by Lukas Fleischer and Manfred Kufleitner was accepted at MFCS 2018.

[Jun’18] The paper “The Intersection Problem for Finite Semigroups” by Lukas Fleischer was accepted at DLT 2018.

[Apr’18] The paper “The isomorphism problem for finite extensions of free groups is in PSPACE” by Géraud Sénizergues and Armin Weiß was accepted at ICALP 2018.

[Apr’18] The paper “On the Complexity of the Cayley Semigroup Membership Problem” by Lukas Fleischer was accepted at CCC 2018.

[Jan’18] On March 24-29, 2019 Volker Diekert, Markus Lohrey, Olga Kharlampovich and Alexei Miasnikov will organize the Schloss Dagstuhl Seminar “Algorithmic Problems in Group Theory”.

[Dec’17] The paper “The Intersection Problem for Finite Monoids” by Lukas Fleischer and Manfred Kufleitner was accepted at STACS 2018.

[Jun’17] At the 12th International Computer Science Symposium in Russia (CSR), Lukas Fleischer and Manfred Kufleitner received a Best Paper Award for their publication “Green’s Relations in Finite Transformation Semigroups”, and Armin Weiss received a Best Paper Award for “The conjugacy problem in free solvable groups and wreath product of abelian groups is in $\text{TC}^0$ \text{TC}^0 “ which is joint work with Alexei Miasnikov and Svetla Vassileva.