■
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
Algorithmische Gruppentheorie
Berechenbarkeit und Komplexität
Graphentheorie
Theoretische Informatik I
Ergänzungen zu Theoretische Informatik I
■
Summer 2017
■
Winter 2016
■
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

Vorlesung

  • Dozent: Prof. Dr. Ulrich Hertrampf

  • 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).

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

Termine

Zeit Raum Termine
Mo 15:45-17:15 V38.04 wöchentlich ab 16.10.2017
Mi 17:30-19:00 V38.04 wöchentlich ab 25.10.2017, außer am 15.11., 22.11., 6.12., 20.12.

Wichtige Ankündigungen

  • Die Scheinliste hängt jetzt neben Raum 1.101 aus. Bitte vergewissern Sie sich dort vor Prüfungsantritt, dass Sie einen Schein erhalten haben!
  • Es gibt ein weiteres Übungsblatt zur Wiederholung und Prüfungsvorbereitung. Die gewissenhafte Bearbeitung dieses Blattes wird allen Prüfungsteilnehmern empfohlen!
  • Die Modulprüfung Berechenbarkeit und Komplexität findet im Wintersemester 2017/18 für alle Teilnehmer in Raum V47.01 statt!
  • Zugelassene Hilfsmittel in der Prüfung: siehe C@MPUS unter Studium → Prüfungsan-/abmeldung → Berechenbarkeit und Komplexität → Prüfungsservice.
  • Für Gruppe A2 wurde die Frist der schriftlichen Abgaben zu Blatt 1 aufgrund des Feiertages bis zum 13.11.2017 verlängert (Abgabe zusammen mit den B-Gruppen).
  • Die Anmeldung zu den Übungsgruppen wurde auf Freitag, den 20.10.2017, um 12:00 Uhr verschoben!
  • Aufgrund der großen Nachfrage wurde eine weitere Übungsgruppe A4 hinzugefügt. Bitte tragen Sie sich im C@MPUS-System entsprechend um. Wartelisten-Plätze können leider nicht vergeben werden.

Vorlesungsplan und Folien

Die Einheiten der nächsten Vorlesung sind stets grün unterlegt.

Die zugreifbaren Folien werden entsprechend in der Vorlesung erarbeitet.

Einheit Datum Inhalt Folien
0 16.10. Organisation, Termine, Arbeitsweise pdf
1 23.10. Berechenbarkeitsbegriff, Churchsche These pdf
2 23.10. Turing-Berechenbarkeit, Bandreduktion pdf
3 25.10. Spezielle Maschinenkonstruktionen pdf
4 25.10. LOOP- und WHILE-Berechenbarkeit pdf
5 30.10. GOTO-Berechenbarkeit, Normalform-Theorem pdf
6 30.10. Turing-Berechenbarkeit = GOTO-Berechenbarkeit pdf
7 6.11. Primitiv rekursive Funktionen (1) pdf
8 6.11. Primitiv rekursive Funktionen (2) pdf
9 8.11. Partiell rekursive Funktionen, Satz von Kleene pdf
10 8.11. Eigenschaften der Ackermann-Funktion pdf
11 13.11. Die Ackermann-Funktion ist nicht primitiv rekursiv pdf
12 13.11. Entscheidbarkeit und Semi-Entscheidbarkeit pdf
13 20.11. Unentscheidbarkeit, das spezielle Halteproblem pdf
14 20.11. Reduktionen, allgemeines Halteproblem pdf
15 27.11. Der Satz von Rice, Postsches Korrespondenzproblem pdf
16 27.11. MPCP, Unentscheidbarkeit von PCP pdf
17 29.11. Unentscheidbare Grammatik-Probleme pdf
18 29.11. Weitere Unentscheidbarkeitsresultate pdf
19 04.12. Der Satz von Gödel, Arithmetik pdf
20 04.12. Arithmetische Repräsentierbarkeit pdf
21 11.12. WA ist nicht rekursiv aufzählbar pdf
22 11.12. Der Unvollständigkeitssatz pdf
23 13.12. Komplexitätsklassen, P und NP pdf
24 13.12. NP-Vollständigkeit pdf
25 18.12. Der Satz von Cook pdf
26 18.12. Beweisdetails zum Satz von Cook pdf
27 08.01. Weitere NP-vollständige Probleme: 3KNF-SAT pdf
28 08.01. CLIQUE, FÄRBBARKEIT pdf
29 10.01. Platzklassen pdf
30 10.01. Varianten algorithmischer Probleme pdf
31 15.01. Grapherreichbarkeit, Grundlegende Beziehungen -- NEUE VERSION von Folie 31.5 !!! pdf
32 15.01. Weitere Beziehungen zwischen Komplexitätsklassen pdf
33 17.01. Satz von Savitch pdf
34 17.01. Hierarchiesätze pdf
35 22.01. Lückensatz von Borodin pdf
36 22.01. Komplementabschluss nichtdeterministischer Platzklassen pdf
37 24.01. Die Translationstechnik pdf
38 24.01. logspace-Reduktionen pdf
39 29.01. NL-vollständige Probleme pdf
40 29.01. Vollständige Probleme in P und PSPACE pdf

Übungen

Alle 14 Tage wird auf der Webseite der Veranstaltung ein Übungsblatt veröffentlicht. Auf jedem Blatt gibt es Präsenzaufgaben und schriftliche Aufgaben.

  • Präsenzaufgaben: Die Präsenzaufgaben werden am darauffolgenden Besprechungstermin in der Gruppe gelöst. Bereiten Sie diese Aufgaben bitte ausreichend vor. Idealerweise sollten Sie die Aufgabe schon im Vorfeld lösen oder Lösungsansätze erarbeiten. Mindestens sollten Sie jedoch die Aufgabenstellung vollständig erfasst haben, einschließlich aller hierfür relevanten Konzepte aus der Vorlesung.

  • schriftliche Aufgaben: Die Abgaben zu den schriftlichen Aufgaben sind fristgerecht und mit Namen, Matrikelnummern und Übungsgruppennummer versehen in den Abgabekästen im Mittelgang des ersten Obergeschosses einzuwerfen. Die bewerteten Abgaben werden in der Regel am darauffolgenden Besprechungstermin zurückgegeben. Musterlösungen zu den schriftlichen Aufgaben werden in den Vortragsübungen vorgestellt.

  • Quiz: Zu Beginn jeder Übungsgruppe gibt es ein Quiz von 10min Dauer, in dem Grundlagen und Konzepte aus den aktuellen Vorlesungsinhalten (insbesondere solche, die für das Verständnis und die Bearbeitung der Präsenzaufgaben relevant sind) abgefragt werden. Dieses ist in Einzelarbeit auszufüllen und wird anschließend von den Tutoren eingesammelt und bewertet.

Scheinkriterien

Zur Teilnahme an der schriftlichen Prüfung benötigen Sie einen Übungsschein. Einen Schein erhält, wer mindestens 50% der maximal erreichbaren schriftlichen Punkte erhält. Schriftliche Punkte können durch Abgaben zu den schriftlichen Aufgaben und durch Abgaben von bearbeiteten Quiz erhalten werden.

Übungsgruppen

Die Besprechungen der Übungen finden jeweils alle 14 Tage statt. Die genauen Termine finden Sie weiter unten.

Die Anmeldung zu den Übungsgruppen erfolgt über das C@MPUS-Portal. Die Freischaltung der Anmeldung erfolgt am Freitag, den 20.10.2017, um 12:00 Uhr.

Gruppe Slot Raum Tutor
A1 Mo. 11:30-13:00 0.124 Böpple
A2 Mi. 15:45-17:15 0.457 Hasler
A3 Do. 15:45-17:15 0.457 Camino
A4 Fr. 15:45-17:15 V38.02 Fleischer
B1 Mo. 11:30-13:00 0.124 Böpple
B2 Mi. 15:45-17:15 0.457 Gaißert
B3 Do. 15:45-17:15 0.457 Camino
B4 Fr. 15:45-17:15 V38.02 Hasler

Vortragsübungen

Zusätzlich zur Vorlesung und den Übungen wird von Marcial Gaißert und Sebastian Hasler eine Ergänzung angeboten. Details finden Sie auf der Homepage der Ergänzungen.

Zeit Raum Termine
Mo 09:45-11:15 V7.04 wöchentlich ab 23.10.2017

Übungsblätter

Die folgende Übersicht enthält die Übungsgruppen-Termine (in denen die Präsenzaufgaben und die zugehörigen Quiz bearbeitet werden), sowie die Abgabetermine und Besprechungstermine der schriftlichen Abgaben zu jedem Blatt.

Die Übungsblätter werden im Laufe des Semesters hochgeladen.

  • Update Blatt 1 (03.11.2017 10:45 Uhr): In der zweiten schriftlichen Aufgabe wurde ein Hinweis hinzugefügt. Für Gruppe A2 wurde die Frist der schriftlichen Abgaben zu Blatt 1 aufgrund des Feiertages bis zum 13.11.2017 verlängert (Abgabe zusammen mit den B-Gruppen).
Blatt Download Bearbeitung Präsenzaufgaben und Quiz Abgabe schriftlich Besprechung
schriftlich
A1 A2 A3 A4 B1 B2 B3 B4 A B
1 pdf 30.10. 08.11.* 02.11. 03.11. 06.11. 08.11. 09.11. 10.11. 06.11. 13.11. 13.11.
2 pdf 13.11. 15.11. 16.11. 17.11. 20.11. 22.11. 23.11. 24.11. 20.11. 27.11. 27.11.
3 pdf 27.11. 29.11. 30.11. 01.12. 04.12. 06.12. 07.12. 08.12. 04.12. 11.12. 11.12.
4 pdf 11.12. 13.12. 14.12. 15.12. 18.12. 20.12. 21.12. 22.12. 18.12. 08.01. 08.01.
5 pdf 08.01. 10.01. 11.01. 12.01. 15.01. 17.01. 18.01. 19.01. 15.01. 22.01. 22.01.
6 pdf 22.01. 24.01. 25.01. 26.01. 29.01. 31.01. 01.02. 02.02. 29.01. 05.02. 05.02.
7 pdf — — — — — — — — — — —

* Der erste Übungsgruppentermin von Gruppe A2 findet am 08.11.2017 in Raum 0.453 statt.

Literatur

Die Inhalte der Vorlesung entstammen im ersten Teil im Wesentlichen dem Buch von Uwe Schöning. Der zweite Teil stützt sich hauptsächlich auf das Skript der früheren Vorlesung Komplexitätstheorie:

  • Uwe Schöning: Theoretische Informatik – kurzgefasst, 5. Auflage, Spektrum, 2008.
  • Volker Diekert: Komplexitätstheorie, Skript, Universität Stuttgart, 10.12.2007

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.