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: Grundbegriffe der Aussagenlogik und der Prädikatenlogik. 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
Di 15:45-17:15 V47.02  
Do 14:00-15:30 V47.02  

Die Vorlesung wird auf Video aufgezeichnet und im Ilias zur Verfügung gestellt.

Vorlesungsplan und Folien

Die Vorlesung besteht aus 40 Einheiten. An jedem Termin werden zwei Einheiten präsentiert.

Die Folien aller Einheiten sind in der folgenden Tabelle zugreifbar, dabei sind die für die nächste Vorlesung stets grün unterlegt.

Zunächst finden Sie hier die Folien des Vorjahres, aber Zug um Zug werden sie durch die aktuellen Folien ersetzt. Die Unterschiede werden allerdings sehr gering sein, so dass einer Verwendung der alten Folien nicht entgegensteht.

Einheit Datum Inhalt Folien
1 21.04. Aussagenlogik: Syntax, Semantik, Baumstruktur pdf-alt
2 21.04. Wahrheitswerte, Äquivalenzen, Ersetzbarkeitstheorem pdf-alt
3 23.04. Normalformen: DNF und KNF pdf-alt
4 23.04. Grundbegriffe der Prädikatenlogik pdf-alt
5 28.04. Churchsche These, Turing-Berechenbarkeit pdf-alt
6 28.04. Konstruktionen mit Turingmaschinen pdf-alt
7 30.04. LOOP-Berechenbarkeit pdf-alt
8 30.04. WHILE- und GOTO-Programme pdf-alt
9 05.05. Normalform-Theorem von Kleene, Turing- vs. GOTO-Berechenbarkeit pdf-alt
10 05.05. Primitiv-rekursive Funktionen, beschränkte Operatoren pdf-alt
11 07.05. Primitive Rekursion entspricht LOOP-Berechenbarkeit, partiell rekursive Funktionen pdf-alt
12 07.05. Satz von Kleene, die Ackermannfunktion pdf-alt
13 12.05. Ackermannfunktion nicht LOOP-berechenbar: Satz und Beweis pdf-alt
14 12.05. Halteproblem, Entscheidbarkeit, rekursive Aufzählbarkeit pdf-alt
15 14.05. Unentscheidbarkeit des speziellen Halteproblems pdf-alt
16 14.05. Reduktionen, allgemeines Halteproblem, Satz von Rice pdf-alt
17 19.05. Postsches Korrespondenzproblem, MPCP pdf-alt
18 19.05. Unentscheidbarkeit des PCP, Grammatikprobleme pdf-alt
19 26.05. Unentscheidbarkeiten für DCFL pdf-alt
20 26.05. Gödelscher Satz, Arithmetische Repräsentierbarkeit pdf-alt
21 28.05. Beweis des Gödelschen Satzes pdf-alt
22 28.05. Der Unvollständigkeitssatz pdf-alt
23 09.06. Komplexitätstheorie pdf-alt
24 09.06. NP-Vollständigkeit pdf-alt
25 16.06. Satz von Cook pdf-alt
26 16.06. Zum Beweis des Satzes pdf-alt
27 18.06. Weitere NP-vollständige Probleme pdf-alt
28 18.06. NP-Härte von CLIQUE und FÄRBBARKEIT pdf-alt
29 23.06. Platzklassen pdf-alt
30 23.06. Varianten algorithmischer Probleme pdf-alt
31 25.06. Grapherreichbarkeit, Grundlegende Beziehungen pdf-alt
32 25.06. Weitere Beziehungen zwischen Komplexitätsklassen pdf-alt
33 30.06. Satz von Savitch pdf-alt
34 30.06. Hierarchiesätze pdf-alt
35 02.07. Lückensatz von Borodin pdf-alt
36 02.07. Komplementabschluss nichtdeterministischer Platzklassen pdf-alt
37 07.07. Die Translationstechnik pdf-alt
38 07.07. logspace-Reduktionen pdf-alt
39 09.07. NL-vollständige Probleme pdf-alt
40 09.07. Vollständige Probleme in P und PSPACE pdf-alt

Ergänzung

Dieses Semester besteht die Ergänzung aus einer Sammlung von Aufgaben zum Selbststudium. Nach der Bearbeitung der vorausgesetzten Vorlesungseinheiten können diese jederzeit entweder selbstständig oder in Lerngruppen gelöst werden.

Zu allen Aufgaben werden Musterlösungen zur Verfügung gestellt. Zu einigen gibt es außerdem Verweise auf Videoaufzeichnungen älterer Ergänzungen, in denen die Aufgabe diskutiert wurde. Die Zusaztfolien enthalten Informationen, die für das Lösen des entsprechenden Ergänzungsblattes hilfreich sein könnten.

Gefundene Fehler werden in den Dateien laufend verbessert. Fragen, Anregungen und Fehlermeldungen bitte per E-Mail an Carlos Camino. Vielen Dank!

Nr Thema Voraussetzungen Aufgaben Lösungen Zusatzfolien
1 Turingmaschinen Einheiten 35-36 von TI 1 [PDF] [PDF] -
2 Aussagen- und Prädikatenlogik Einheiten 1-4 [PDF] [PDF] [PDF]
3 Turing-, GOTO-, WHILE- und LOOP-Berechenbarkeit Einheiten 5-9 [PDF] [PDF] [PDF]
4 Primitive Rekursion Einheiten 10-11 [PDF] [PDF] [PDF]
5 Partielle Rekursion Einheiten 12-13 [PDF] [PDF] [PDF]
6 Entscheidbarkeit, Semi- und Co-Semi-Entscheidbarkeit Einheit 14 [PDF] [PDF] [PDF]
7 Reduktionen und der Satz von Rice Einheiten 15-16 [PDF] [PDF] [PDF]
8 Das Postsche Korrespondenzproblem Einheiten 17-19 [PDF] [PDF] -
9 Der Gödelsche Unvollständigkeitssatz Einheiten 20-22 [PDF] [PDF] -
10 Die Klassen P und NP Einheiten 23-28 [PDF] [PDF] -
11 Inklusionsbeziehungen zwischen Sprachklassen Einheiten 29-34 und 36 [PDF] [PDF] [PDF]
12 Der Lückensatz von Borodin Einheit 35 [PDF] [PDF] -
13 Die Translationssätze Einheit 37 [PDF] [PDF] -
14 Die Klassen NL und PSPACE Einheiten 38-40 [PDF] [PDF] [PDF]
15 Prüfungsvorbereitung Gesamte Vorlesung TI 2 [PDF] [PDF] -

Übungen

Lehrevaluation

Aufgrund regen Interesses findet auch dieses Semester eine Lehrevaluation statt. Dazu können Sie bis zum 24. Juni den Online-Fragebogen ausfüllen.

Anmeldung & Scheinkriterien

Die Anmeldung für die Übungen beginnt am 23.04. um 16:00 im Campus-System. Die Anmeldung ist möglich bis 28.04. um 23:59. Sollten Sie sich schon vor dem 23.04. für die Übungen angemeldet haben, müssen Sie das leider im Anmeldezeitraum wiederholen.

Zur Teilnahme an der schriftlichen Prüfung benötigen Sie einen Übungsschein. Die Scheinkriterien sind wie folgt:

  • 50% der Punkte aus den schriftlichen Abgaben
  • 30% der Aufgaben votiert (Aufgaben, bei denen Sie weniger als 50% der schriftlichen Punkte erreicht haben, zählen als nicht votiert)
  • 2x vorrechnen

Bitte beachten Sie auch die weiteren Hinweise zum Übungsbetrieb auf dem ersten Übungsblatt.

Übungsgruppen

Die Übungsgruppen finden wöchentlich per Videokonferenz (Webex) mit einer Dauer von jeweils 45-60 Minuten statt.

Bitte melden Sie sich über das Campus-System zu den Übungsgruppen an. Die Termine entnehmen Sie folgender Tabelle.

Gruppe Tag Beginn Tutor(in)
01 Dienstag 11:30 Mundinger
02 Dienstag 16:15 Egger
03 Dienstag 15:45 Stober
04 Dienstag 17:30 Egger
05 Dienstag 17:30 Schmid
06 Mittwoch 10:15 Kittelberger
07 Mittwoch 10:15 Lenk
08 Mittwoch 11:30 Kittelberger
09 Mittwoch 14:30 Bauer
10 Mittwoch 15:45 Bienias
11 Mittwoch 14:30 Gaißert
12 Mittwoch 16:15 Kotowsky
13 Mittwoch 15:45 Lenk
14 Mittwoch 17:30 Bauer
15 Mittwoch 17:30 Kotowsky
16 Donnerstag 09:45 Kischkat
17 Donnerstag 10:15 Mattes
18 Donnerstag 11:30 Gaißert
19 Donnerstag 11:30 Mundinger
20 Donnerstag 11:30 Mattes
21 Donnerstag 14:30 Bienias
22 Donnerstag 15:45 Egger
23 Donnerstag 15:45 Kischkat
24 Donnerstag 15:45 Mattes
25 Donnerstag 17:30 Schmid
26 Freitag 16:15 Schmid
27 Dienstag 16:15 Schmid

Übungsblätter

Achtung Bei Aufgabe 3 a) auf Blatt 2 gab es eine Änderung, bitte beachten!

Achtung Bei Aufgabe 2 b) auf Blatt 3 gab es eine Änderung, bitte beachten!

  • Blatt 1 (Abgabe bis 01.05.20 , 23:59 Uhr)
  • Blatt 2 (Abgabe bis 08.05.20 , 23:59 Uhr)
  • Blatt 3 (Abgabe bis 15.05.20 , 23:55 Uhr)
  • Blatt 4 (Abgabe bis 22.05.20 , 23:55 Uhr)
  • Blatt 5 (Abgabe bis 29.05.20 , 23:55 Uhr)
  • Blatt 6 (Abgabe bis 12.06.20 , 23:55 Uhr)
  • Blatt 7 (Abgabe bis 19.06.20 , 23:55 Uhr)
  • Blatt 8 (Abgabe bis 26.06.20 , 23:55 Uhr)
  • Blatt 9 (Abgabe bis 03.07.20 , 23:55 Uhr)
  • Blatt 10 (Abgabe bis 10.07.20 , 23:55 Uhr)

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

[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.