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 27.02.2019 sind nun korrigiert und die Ergebnisse hängen aus! Die Einsicht findet am Dienstag, den 26.03.2019 um 10:00 Uhr in Raum 1.168 statt!
-
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 Studium → Prüfungsan-/abmeldung → Theoretische Informatik II → Prü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 | |
| 2 | 10.04. | Wahrheitswerte, Äquivalenzen, Ersetzbarkeitstheorem | |
| 3 | 12.04. | Normalformen: DNF und KNF | |
| 4 | 12.04. | Grundbegriffe der Prädikatenlogik | |
| 5 | 17.04. | Churchsche These, Turing-Berechenbarkeit | |
| 6 | 17.04. | Konstruktionen mit Turingmaschinen | |
| 7 | 19.04. | LOOP- und WHILE-Berechenbarkeit | |
| 8 | 19.04. | GOTO-Programme, Normalform-Theorem von Kleene | |
| 9 | 24.04. | Turing- vs. GOTO-Berechenbarkeit, Primitiv-rekursive Funktionen | |
| 10 | 24.04. | Beschränkte Operatoren, Primitive Rekursion entspricht LOOP-Berechenbarkeit | |
| 11 | 26.04. | Partiell rekursive Funktionen, Satz von Kleene | |
| 12 | 26.04. | Die Ackermannfunktion | |
| 13 | 03.05. | Halteproblem, Entscheidbarkeit | |
| 14 | 03.05. | Rekursive Aufzählbarkeit | |
| 15 | 08.05. | Reduktionen, allgemeines Halteproblem | |
| 16 | 08.05. | Satz von Rice, Postsches Korrespondenzproblem | |
| 17 | 15.05. | Unentscheidbarkeit von PCP und MPCP | |
| 18 | 15.05. | Unentscheidbarkeitsresultate für DCFL | |
| 19 | 17.05. | Arithmetische Formeln, Gödelscher Satz | |
| 20 | 17.05. | Arithmetische Repräsentierbarkeit | |
| 21 | 29.05. | Beweis des Gödelschen Satzes | |
| 22 | 29.05. | Der Unvollständigkeitssatz | |
| 23 | 05.06. | Komplexitätstheorie | |
| 24 | 05.06. | NP-Vollständigkeit | |
| 25 | 07.06. | Satz von Cook | |
| 26 | 07.06. | Zum Beweis des Satzes | |
| 27 | 12.06. | Weitere NP-vollständige Probleme | |
| 28 | 12.06. | NP-Härte von CLIQUE und FÄRBBARKEIT | |
| 29 | 21.06. | Platzklassen | |
| 30 | 21.06. | Varianten algorithmischer Probleme | |
| 31 | 26.06. | Grapherreichbarkeit, Grundlegende Beziehungen | |
| 32 | 26.06. | Weitere Beziehungen zwischen Komplexitätsklassen | |
| 33 | 05.07. | Satz von Savitch | |
| 34 | 05.07. | Hierarchiesätze | |
| 35 | 12.07. | Lückensatz von Borodin | |
| 36 | 12.07. | Komplementabschluss nichtdeterministischer Platzklassen | |
| 37 | 17.07. | Die Translationstechnik | |
| 38 | 17.07. | logspace-Reduktionen | |
| 39 | 19.07. | NL-vollständige Probleme | |
| 40 | 19.07. | Vollständige Probleme in P und PSPACE |
Ü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 | 17.04. | 19.04. | 19.04. | 19.04. | 19.04. | 19.04. | 19.04. | 20.04. | 20.04. | 27.04. | 04.05. | |
| 2 | 30.04.* | 03.05. | 03.05. | 03.05. | 03.05. | 03.05. | 03.05. | 04.05. | 04.05. | 11.05. | 18.05. | |
| 3 | 15.05. | 17.05. | 17.05. | 17.05. | 17.05. | 17.05. | 17.05. | 18.05. | 18.05. | 01.06. | 08.06. | |
| 4 | 05.06. | 07.06. | 07.06. | 07.06. | 07.06. | 07.06. | 07.06. | 08.06. | 08.06. | 15.06. | 22.06. | |
| 5 | 19.06. | 21.06. | 21.06. | 21.06. | 21.06. | 21.06. | 21.06. | 22.06. | 22.06. | 29.06. | 06.07. | |
| 6 | 03.07. | 05.07. | 05.07. | 05.07. | 05.07. | 05.07. | 05.07. | 06.07. | 06.07. | 20.07. | 20.07. | |
| 7 | — | — | — | — | — | — | — | — | — | — | — | |
* 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 | 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 | 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 | 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 | 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 | 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 | 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 | — | — | — | — | — | — | — | — | — | — | — | |
* 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