Theoretical Computer Science

Vorlesung: Theoretische Informatik 2

Sommersemester 2023

News

27. Juli

Die Prüfungsergebnisse der Abschlussklausur vom 25. Juli sind nun verfügbar:

• Ergebnisse
• Statistik

Eine Klausureinsicht findet am 04.08. von 11:00 bis 14:00 in Raum IZ 358 statt. Bei weiteren Fragen wenden Sie sich an René Maseli.
Eine Übersicht ist hier bereitgestellt. Die Bestehensquote beträgt 88%.

3. Juli

Als Vorbereitung auf die Prüfung am 25.07. wird am 18.07. diese Probeklausur behandelt. Sie können sich ab sofort daran versuchen.

8. Mai

Die Übungen mittwochs und freitags finden wieder in den üblichen Räumen statt.

24. April

Die kleinen Übungen mittwochs und freitags werden für die nächste Zeit online stattfinden. Der Web-Konferenz-Raum ist dieser BBB-Raum.

20. April

Die kleinen Übungen am 11. Mai werden nicht in IZ 358 stattfinden. Der Ersatzraum wird in Kürze bekannt gegeben ist IZ 413A.

18. April

Die Anmeldung zu den kleinen Übungen ist auf der Stud.IP-Seite freigeschaltet.

17. April

Die erste große Übung findet morgen statt. Die Anmeldung zur kleinen Übung, sowie das erste Aufgabenblatt werden auch ab morgen verfügbar sein.

12. April

Die Vorlesung startet am 17. April. Die erste große Übung findet am 25. April 18. April statt.

13. März

Die Informationen auf dieser Seite sind noch vorläufig.

Organisation

• Die Dozenten der Vorlesung sind Prof. Dr. Roland Meyer und René Maseli.
• Prüfer der Vorlesung ist Prof. Dr. Roland Meyer.
• Einträge im Vorlesungsverzeichnis: Vorlesung, kleine Übung.
• Vorlesung (Stud.IP):
  • Montag, 13:15 - 14:45 in PK 11.3.
  • Dienstag, 13:15 - 14:45 in PK 11.3, alle 14 Tage.
• Große Übung:
  • Dienstag, 13:15 - 14:45 in PK 11.3, alle 14 Tage, wenn keine Vorlesung stattfindet.
• Kleine Übung (Stud.IP): zweiwöchig.
  • Mittwoch, 18:30 - 20:00 in IZ 358, mit Viktoria Lammers, startend am 26. April.
  • Donnerstag, 15:00 - 16:30, in IZ 358, mit Dennis Dinh, startend am 27. April.
  • Donnerstag, 16:45 - 18:15, in IZ 358, mit Dennis Dinh, startend am 27. April.
  • Freitag, 13:15 - 14:45, in IZ 358, mit Viktoria Lammers, startend am 28. April.
• Lerntreff Theorie: wöchentlich.
  • Mittwoch, 11:30 - 13:00 in IZ 358, mit Benjamin Hennies, startend ab 19. April.
• Im zweiwöchigen Rhythmus werden auf dieser Seite Übungsblätter mit Hausaufgaben online gestellt. Diese Hausaufgaben werden in Vierer-Gruppen bearbeitet und abgegeben. Unvollständige Gruppen bzw. Einzelpersonen werden zu Vierer-Gruppen zusammengefasst.
• Um das Modul erfolgreich abzuschließen, sind zwei Leistungen zu erbringen:
  • Prüfungsleistung: Zu erbringen durch Bestehen einer schriftliche Abschlussklausur am 25. Juli, von 11:30 bis 13:30 Uhr, im Audimax und Bunker UP 3.007.
  • 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: 2023-05-02). Weitere Materialien finden sich weiter unten auf dieser Seite.

17. April

Intro,

18. April

Übung 1: CSL und LBAs.

24. April

CSL und TM.

25. April

Satz von Kuroda und Determinismus in TMs.

2. Mai

Übung 2: Alphabetsreduktion, Mehrband-Turing-Maschinen

8. Mai

Berechenbarkeit I, Berechenbarkeit II.

9. Mai

Entscheidbarkeit, Unentscheidbarkeit.

15. Mai

Kodierung von TM, Die universelle TM, Unentscheidbarkeit von ACCEPT.

16. Mai

Übung 3: Berechenbare Funktionen.

22. Mai

Reduktionen. Post Correspondence Problem.

23. Mai

Satz von Rice.

5. Juni

Unentscheidbare Probleme kontextfreier Sprachen.

6. Juni

Übung 4: Reduktionen.

12. Juni

Grundlagen der Komplexitätstheorie, Landau-Notation, Komplexitätsklassen.

13. Juni

Satz von Immerman und Szelepcsényi.

19. Juni

Grundlagen der Komplexitätstheorie II Relationen, Komplementklassen, Landkarte der Komplexitätstheorie.

20. Juni

Übung 5: Komplexitätsanalyse, NL-Vollständigkeit.

26. Juni

Reduktionen und die Klassen L und NL, Reduktionen und Vollständigkeit.

27. Juni

Path, 2-SAT. Probleme in L,

3. Juli

P, NP,

4. Juli

Übung 6: NP-vollständige Probleme (3-SAT, 3-COLORABILITY).

10. Juli

SAT, HamiltonianCycle. Zertifikate,

11. Juli

Quantifizierte Boolsche Formeln. Satz von Savitch,

17. Juli

Hierarchiesätze. Klausurinfos.

18. Juli

Übung 7: Klausurvorbereitung

Ü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. 18. April - 26. April tutorium de en
2. 2. Mai - 10. Mai de en
3. 16. Mai - 24. Mai tutorium de en
4. 5. Juni - 14. Juni de en
5. 20. Juni - 28. Juni de en
6. 4. Juli - 12. Juli 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

Abschlussklausur

• Die Abschlussklausur findet am Dienstag, dem 25. Juli 2023 von 11:30 bis 13:30 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: Winter 2017/18, Sommer 2018, Sommer 2019, Winter 2019/20, Sommer 2020, Winter 2020/21, Sommer 2021, Winter 2021/22, Sommer 2022.

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]