Theoretical Computer Science

Vorlesung: Theoretische Informatik 2

Sommersemester 2024

News

25. Juni

Als Vorbereitung für die Prüfung am 16. Juli steht eine Probeklausur zur Verfügung. Sie wird voraussichtlich am 9. Juli behandelt.

24. Juni

Die dieswöchigen kleinen Übungen mit Eren Keskin verschieben sich um eine Woche. Sie finden nicht am 26. und 27. Juni (11:30 bzw. 16:45 Uhr), sondern am 3. und 4. Juli statt.

17. Juni

Die Aufgabenstellung zu Blatt 5, Aufgabe 2 wurde korrigiert. Ab morgen bis zum Ende der Vorlesungszeit wird Thomas Haas an Stelle von Prof. Meyer die Vorlesung halten.

7. Mai

Ein Hinweis zu Blatt 2, Aufgabe 4, a) wurde hinzugefügt.

15. April

Die VIPS-Gruppen sind nun freigeschaltet. Auch das erste Aufgabenblatt ist zum Download verfügbar.

8. April

Um sich für die kleinen Übungen anzumelden, tragen Sie sich in diese Stud.IP Veranstaltung ein. Die VIPS-Gruppen werden in Kürze freigeschaltet. Das erste Aufgabenblatt wird am 15. April herausgegeben. Die kleinen Übungen starten ab dem 2. Mai. Die kleinen Übungen am 1. Mai werden auf den 8. Mai verschoben.

25. März

Die Vorlesung startet am 08. April.

Organisation

• Dozent und Prüfer der Vorlesung ist Prof. Dr. Roland Meyer.
• Leiter der Übungen ist René Maseli.
• Eintrag im Vorlesungsverzeichnis: Vorlesung, kleine Übung, Prüfung.
• Stud.IP-Veranstaltungen: Vorlesung, kleine Übung.
• Vorlesung: Montag, 13:15 - 14:45 in PK 11.1.
• Vorlesung / Große Übung: Dienstag, 13:15 - 14:45 in UP 3.007.
• Kleine Übungen, startend ab dem 2. Mai. Abgaben erfolgen über Stud.IP.
  • Mittwoch, 11:30 - 13:00 in IZ 358, mit Eren Keskin, startend am 8. Mai.
  • Donnerstag, 15:00 - 16:30, in IZ 358, mit Jan Wasserscheidt, startend am 2. Mai.
  • Donnerstag, 16:45 - 18:15, in IZ 358, mit Eren Keskin, startend am 2. Mai.
  • Freitag, 13:15 - 14:45, in IZ 358, mit Fabian Kollhoff, startend am 3. Mai.
• Sprechstunde Mittwoch, 18:30 - 19:30 in IZ 358, mit René Maseli.

Modul

Um das Modul erfolgreich abzuschließen, sind zwei Leistungen zu erbringen:

• Prüfungsleistung: Zu erbringen durch Bestehen einer schriftliche Abschlussklausur.
• Studienleistung: Zu erbringen durch das erfolgreiche Bearbeiten von mindestens 50% der Übungsaufgaben.

Material

Begleitend zur Vorlesung werden hier Notizen und Videos aus vergangenen Semestern zur Verfügung gestellt. In diesem Semester halten wir uns an folgendes Skript (Stand: 2024-07-01).

Übungsblätter

Alle zwei Wochen werden während des Semesters hier die Übungsblätter zur Verfügung gestellt. Die Abgabe kann sowohl im Stud.IP, als auch über den Briefkasten vor dem Raum IZ 343 erfolgen.

Kontaktieren Sie bei Fragen zu den Übungsblättern Ihren Tutor oder René Maseli.

1. 15. April - 25. April: tutorium de
2. 30. April - 9. Mai: tutorium de en
3. 13. Mai - 23. Mai tutorium de
4. 27. Mai - 6. Juni tutorium de en
5. 10. Juni - 20. Juni tutorium de en
6. 24. Juni - 4. Juli tutorium de en

Weiteres Material

• Ältere Versionen der Vorlesungsnotizen: Sommersemester 2017 , Sommersemester 2018 , Sommersemester 2019 .
• Skript zur Vorlesung Theoretische Informatik 1
• Skript zur Vorlesung Komplexitätstheorie

• Kontextsensitive Sprachen
• Satz von Immerman und Szelepcsényi
• Satz von Immerman und Szelepcsényi (2)
• Berechenbarkeit
• Unentscheidbarkeit, die universelle Turing-Maschine, das Halteproblem, Reduktionen
• PCP und der Satz von Rice
• Unentscheidbare Probleme kontextfreier Sprachen
• Zeit- und Platzkomplexitätsklassen
• Beziehungen zwischen den robusten Komplexitätsklassen
• L und NL
• P and NP
• PSPACE
• Satz von Savitch
• Platz vs. Zeit, Nichtdeterminismus vs. Determinismus
• Hierarchieresultate für die Zeit- und Platzkomplexitätsklassen
• Translation-Theoreme
• Berechnungsmodelle für L and NL

• Intro
• Übung 1: CSL und LBAs
• CSL und TM
• Satz von Kuroda und Determinismus in TMs
• Berechenbarkeit I
• Berechenbarkeit II
• Entscheidbarkeit
• Unentscheidbarkeit
• Kodierung von TM
• Die universelle TM
• Unentscheidbarkeit von ACCEPT
• Übung 3: Berechenbare Funktionen
• Reduktionen
• Post Correspondence Problem
• Satz von Rice
• Unentscheidbare Probleme kontextfreier Sprachen
• Übung 4: Reduktionen
• Grundlagen der Komplexitätstheorie
• Landau-Notation
• Komplexitätsklassen
• Satz von Immerman und Szelepcsényi
• Relationen
• Komplementklassen
• Landkarte der Komplexitätstheorie
• Übung 5: Komplexitätsanalyse
• NL-Vollständigkeit
• Reduktionen und Vollständigkeit
• Path
• 2-SAT
• Probleme in L
• P
• NP
• Übung 6: NP-vollständige Probleme (3-SAT, 3-COLORABILITY)
• SAT
• HamiltonianCycle
• Zertifikate
• Quantifizierte Boolsche Formeln
• Satz von Savitch
• Hierarchiesätze
• Klausurinfos

Abschlussklausur

• Die Abschlussklausur findet am Dienstag, dem 16. Juli 2024 von 8:00 bis 10:00 Uhr im Audimax, sowie UP 3.007 darunter, statt.
• Sie besteht aus 7 Aufgaben zu je 10 Punkten, die Bearbeitungszeit beträgt üblicherweise 120 Minuten. Die Klausur umfasst den kompletten Stoff der Vorlesung und orientiert sich an den Übungsaufgaben auf den Aufgabenblättern. Mit mindestens 40%, also 28 Punkten, gilt die Prüfung als bestanden.
• Als Hilfsmittel sind ausschließlich Sprachwörterbücher sowie ein beidseitig handschriftlich beschriebenes DIN A4-Blatt erlaubt.
• Zur Vorbereitung auf die Abschlussklausur empfiehlt sich das Durcharbeiten der Klausuren aus den vergangenen Jahren: Sommer 2020, Sommer 2021, Sommer 2022, Sommer 2023.

Literatur

• U. Schöning: Theoretische Informatik - kurzgefasst. Springer, 2008.
• J. E. Hopcroft, R. Motwani, J. D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley Longman, 2002.
• M. Nebel: Formale Grundlagen der Programmierung. Vieweg+Teubner, 2012.
• M. Sipser: Introduction to the Theory of Computation. Cengage Learning, 2012.
• I. Wegener: Complexity Theory. Springer, 2005.
• D. Kozen: Automata and Computability. Springer, 1977.
• O. Goldreich: Computational Complexity. Cambridge University Press, 2008.
• A. M. Turing: On Computable Numbers, with an application to the Entscheidungsproblem. [DOI] [PDF]