Prüfungsergebnisse (WS 20/21)
Prüfungsergebnisse (SoSe 20)
Die Prüfungsergebnisse zu den unten aufgeführten Prüfungen wurden versandt.
Hinweise und Notenschlüssel
Hinweise zur Korrektur:
- Theoretische Informatik II und Berechenbarkeit und Komplexität:
[Notenschlüssel & Hinweise]
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
-
Übungen: Mitarbeiter der Abteilung Theoretische Informatik
-
Ansprechpartner: Caroline Mattes, Armin Weiß
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