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

  • 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. Unentscheidbarkeit von PCP -
17 29.11. Unentscheidbare Grammatik-Probleme -
18 29.11. Weitere Unentscheidbarkeitsresultate -
19 04.12. Der Satz von Gödel, Arithmetik -
20 04.12. Arithmetische Repräsentierbarkeit -
21 11.12. WA ist nicht rekursiv aufzählbar -
22 11.12. Der Unvollständigkeitssatz -
23 13.12. -
24 13.12. -
25 18.12. -
26 18.12. -
. . . (weitere Einheiten folgen!)

Ü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 11.12. 13.12. 14.12. 15.12. 18.12. 20.12. 21.12. 22.12. 18.12. 08.01. 08.01.
5 08.01. 10.01. 11.01. 12.01. 15.01. 17.01. 18.01. 19.01. 15.01. 22.01. 22.01.
6 22.01. 24.01. 25.01. 26.01. 29.01. 31.01. 01.02. 02.02. 29.01. 05.02. 05.02.

* 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’17] Lukas’ paper “Green’s Relations in Finite Transformation Semigroups” and Armin’s paper “The conjugacy problem in free solvable groups and wreath product of abelian groups is in $\text{TC}^0$ \text{TC}^0 “ both have received a Best Paper Award at the 12th International Computer Science Symposium in Russia (CSR).