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 StudiumPrüfungsan-/abmeldungBerechenbarkeit und KomplexitätPrü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’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.