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 ab 10.4. bis 12.6. und am 26.6. und 17.7.
Do 14:00-15:30 V47.02 ab 12.4. jeden Donnerstag, außer am 14.6. und 28.6.

Wichtige Ankündigungen

  • Die Modulprüfungen Theoretische Informatik II und Berechenbarkeit und Komplexität vom 05.09.2018 sind nun korrigiert und die Ergebnisse hängen aus! Die Einsicht findet am Donnerstag, den 11.10.2018 um 14:00 Uhr in Raum 1.168 statt!

  • Die Modulprüfung Theoretische Informatik II am 05.09.2018 findet für alle Teilnehmer in Raum V7.02 statt!
  • Die Scheinliste hängt jetzt neben Raum 1.101 aus. Bitte vergewissern Sie sich vor Prüfungsantritt unbedingt, dass Sie einen Schein erhalten haben!
  • Zugelassene Hilfsmittel in der Prüfung: siehe C@MPUS unter StudiumPrüfungsan-/abmeldungTheoretische Informatik IIPrüfungsplanungsservice.

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.

Einheit Datum Inhalt Folien
1 10.04. Aussagenlogik: Syntax, Semantik, Baumstruktur pdf
2 10.04. Wahrheitswerte, Äquivalenzen, Ersetzbarkeitstheorem pdf
3 12.04. Normalformen: DNF und KNF pdf
4 12.04. Grundbegriffe der Prädikatenlogik pdf
5 17.04. Churchsche These, Turing-Berechenbarkeit pdf
6 17.04. Konstruktionen mit Turingmaschinen pdf
7 19.04. LOOP- und WHILE-Berechenbarkeit pdf
8 19.04. GOTO-Programme, Normalform-Theorem von Kleene pdf
9 24.04. Turing- vs. GOTO-Berechenbarkeit, Primitiv-rekursive Funktionen pdf
10 24.04. Beschränkte Operatoren, Primitive Rekursion entspricht LOOP-Berechenbarkeit pdf
11 26.04. Partiell rekursive Funktionen, Satz von Kleene pdf
12 26.04. Die Ackermannfunktion pdf
13 03.05. Halteproblem, Entscheidbarkeit pdf
14 03.05. Rekursive Aufzählbarkeit pdf
15 08.05. Reduktionen, allgemeines Halteproblem pdf
16 08.05. Satz von Rice, Postsches Korrespondenzproblem pdf
17 15.05. Unentscheidbarkeit von PCP und MPCP pdf
18 15.05. Unentscheidbarkeitsresultate für DCFL pdf
19 17.05. Arithmetische Formeln, Gödelscher Satz pdf
20 17.05. Arithmetische Repräsentierbarkeit pdf
21 29.05. Beweis des Gödelschen Satzes pdf
22 29.05. Der Unvollständigkeitssatz pdf
23 05.06. Komplexitätstheorie pdf
24 05.06. NP-Vollständigkeit pdf
25 07.06. Satz von Cook pdf
26 07.06. Zum Beweis des Satzes pdf
27 12.06. Weitere NP-vollständige Probleme pdf
28 12.06. NP-Härte von CLIQUE und FÄRBBARKEIT pdf
29 21.06. Platzklassen pdf
30 21.06. Varianten algorithmischer Probleme pdf
31 26.06. Grapherreichbarkeit, Grundlegende Beziehungen pdf
32 26.06. Weitere Beziehungen zwischen Komplexitätsklassen pdf
33 05.07. Satz von Savitch pdf
34 05.07. Hierarchiesätze pdf
35 12.07. Lückensatz von Borodin pdf
36 12.07. Komplementabschluss nichtdeterministischer Platzklassen pdf
37 17.07. Die Translationstechnik pdf
38 17.07. logspace-Reduktionen pdf
39 19.07. NL-vollständige Probleme pdf
40 19.07. Vollständige Probleme in P und PSPACE pdf

Übungen

  • Übungen: Mitarbeiter der Abteilung Theoretische Informatik

  • Ansprechpartner: Lukas Fleischer

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 Mittwoch, den 11.04.2018, um 18:00 Uhr.

Falls Sie Übungen im wöchentlichen Rhythmus (mit detaillierteren Diskussionen der Lösungen) möchten, melden Sie sich bitte in Gruppe B2 an. Mehr Informationen zu den einzelnen Übungsgruppen finden Sie auch weiter unten.

Gruppe Slot Raum Tutor
A1 Di. 08:00-09:30 V38.02 Bienias
A3 Do. 11:30-13:00 0.463 Gaißert
A4 Do. 15:45-17:15 0.457 Bienias
A5 Do. 15:45-17:15 0.463 Kittelberger
A6 Do. 17:30-19:00 0.124 Böpple
A7 Do. 17:30-19:00 0.457 Lehmann
A8 Do. 17:30-19:00 V38.03 Sommer
A9 Fr. 08:00-09:30 0.457 Stach
A10 Fr. 09:45-11:15 0.124 Fleischer
B1 Di. 08:00-09:30 V38.02 Sommer
B2 Di. 14:00-15:30 0.463 Hasler
B3 Do. 11:30-13:00 0.463 Gaißert
B4 Do. 15:45-17:15 0.457 Sommer
B5 Do. 15:45-17:15 0.463 Kittelberger
B6 Do. 17:30-19:00 0.124 Böpple
B7 Do. 17:30-19:00 0.457 Lehmann
B8 Do. 17:30-19:00 V38.03 Sommer
B9 Fr. 08:00-09:30 0.457 Stach

Übungsblätter

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

  • Update Blatt 4 (04.06.2018 12:45): Die Aufgabenstellung in der ersten schriftlichen Aufgabe wurde leicht modifiziert. Für die Lösung muss jetzt nicht mehr der Satz von Rice verwendet werden.
  • Update Blatt 4 (05.06.2018 11:00): Hinweis zur ersten schriftlichen Aufgabe hinzugefügt.
  • Update Blatt 6 (04.07.2018 05:15): Die Abgabefrist für A-Gruppen wurde auf den 20.07.2018 verschoben.
  • Update Blatt 6 (18.07.2018 11:30): In Aufgabe 3 soll gezeigt werden, dass das genannte Problem in coNP liegt.
  • Update Blatt 6 (19.07.2018 10:30): In Aufgabe 2 wird zusätzlich gefordert, dass die Abbildung monoton steigend ist.

A-Gruppen

Blatt Download Bearbeitung Präsenzaufgaben und Quiz Abgabe
schriftlich
Besprechung
schriftlich
A1 A3 A4 A5 A6 A7 A8 A9 A10
1 pdf 17.04. 19.04. 19.04. 19.04. 19.04. 19.04. 19.04. 20.04. 20.04. 27.04. 04.05.
2 pdf 30.04.* 03.05. 03.05. 03.05. 03.05. 03.05. 03.05. 04.05. 04.05. 11.05. 18.05.
3 pdf 15.05. 17.05. 17.05. 17.05. 17.05. 17.05. 17.05. 18.05. 18.05. 01.06. 08.06.
4 pdf 05.06. 07.06. 07.06. 07.06. 07.06. 07.06. 07.06. 08.06. 08.06. 15.06. 22.06.
5 pdf 19.06. 21.06. 21.06. 21.06. 21.06. 21.06. 21.06. 22.06. 22.06. 29.06. 06.07.
6 pdf 03.07. 05.07. 05.07. 05.07. 05.07. 05.07. 05.07. 06.07. 06.07. 20.07. 20.07.
7 pdf

* Blatt 2 wird in Gruppe A1 am 30.04.2018 um 08:00 Uhr in Raum 0.108 besprochen.

B-Gruppen

Die zusätzliche Übungsgruppe B2 findet wöchentlich ab dem 17.04.2018 statt. Die Aufgaben werden dort in einem langsameren Tempo bearbeitet. Die Abgabetermine für Gruppe B2 sind dieselben wie für die restlichen B-Gruppen!

Blatt Download Bearbeitung Präsenzaufgaben und Quiz Abgabe
schriftlich
Besprechung
schriftlich
B1 B2 B3 B4 B5 B6 B7 B8 B9
1 pdf 24.04. 17.04./24.04. 26.04. 26.04. 26.04. 26.04.* 26.04. 26.04. 27.04. 04.05. 04.05.
2 pdf 08.05. 02.05.*/08.05. 11.05.* 11.05.* 11.05.* 11.05.* 11.05.* 11.05.* 11.05. 18.05. 18.05.
3 pdf 29.05. 15.05./29.05. 04.06.* 01.06.* 01.06.* 01.06.* 01.06.* 01.06.* 01.06. 08.06. 08.06.
4 pdf 12.06. 05.06./12.06. 14.06. 14.06. 14.06. 14.06. 14.06. 14.06. 15.06. 22.06. 22.06.
5 pdf 26.06. 19.06./26.06. 28.06. 28.06. 28.06. 28.06. 28.06. 28.06. 29.06. 06.07. 06.07.
6 pdf 10.07. 03.07./10.07. 12.07. 12.07. 12.07. 12.07. 12.07. 12.07. 13.07. 20.07. 20.07.
7 pdf

* Bitte beachten Sie die folgenden Ersatztermine:

  • Blatt 1 wird in Gruppe B6 am 26.04.2018 um 17:30 Uhr in Raum 0.363 besprochen.
  • Blatt 2 wird in Gruppe B2 am 02.05.2018 um 17:30 Uhr in Raum 0.108 besprochen.
  • Blatt 2 wird in Gruppe B3 am 11.05.2018 um 15:45 Uhr in Raum 0.108 besprochen.
  • Blatt 3 wird in Gruppe B3 am 04.06.2018 um 14:00 Uhr in Raum 0.463 besprochen.
  • Blatt 2 wird in Gruppe B4 am 11.05.2018 um 08:00 Uhr in Raum 0.124 besprochen.
  • Blatt 3 wird in Gruppe B4 am 01.06.2018 um 08:00 Uhr in Raum 0.124 besprochen.
  • Blatt 2 wird in Gruppe B5 am 11.05.2018 um 09:45 Uhr in Raum 0.447 besprochen.
  • Blatt 3 wird in Gruppe B5 am 01.06.2018 um 09:45 Uhr in Raum 0.447 besprochen.
  • Blatt 2 wird in Gruppe B6 am 11.05.2018 um 09:45 Uhr in Raum 0.108 besprochen.
  • Blatt 3 wird in Gruppe B6 am 01.06.2018 um 09:45 Uhr in Raum 0.108 besprochen.
  • Blatt 2 wird in Gruppe B7 am 11.05.2018 um 15:45 Uhr in Raum 0.457 besprochen.
  • Blatt 3 wird in Gruppe B7 am 01.06.2018 um 15:45 Uhr in Raum 0.457 besprochen.
  • Blatt 2 wird in Gruppe B8 am 11.05.2018 um 09:45 Uhr in Raum 0.124 besprochen.
  • Blatt 3 wird in Gruppe B8 am 01.06.2018 um 09:45 Uhr in Raum 0.124 besprochen.

Ergänzungen

Zusätzlich zur Vorlesung und den Übungen wird von Carlos Camino eine Ergänzung angeboten.

Zeit Raum Termine
Fr 14:00-15:30 V38.04 wöchentlich ab 13.04.2018

Details zur Veranstaltung entnehmen Sie bitte der Ergänzungswebseite.

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

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