Institute of Theoretical Computer Science

Vorlesung: Theoretische Informatik 2

Sommersemester 2024

News

18. Juli: Die Ergebnisse der Prüfung sind hier einsehbar. Die Bestehensquote beträgt 62.4%.
Die Klausureinsicht findet am Mittwoch, den 24. Juli, ab 12:00 in IZ 358 statt. Für einen alternativen Termin schreiben Sie eine Mail an René Maseli.
9. Juli: Lösungen für die Probeklausur sind nun verfügbar.
Die Raumverteilung für die Klausur: Prüflinge mit Vornamen A-I werden in UP 3.007 geprüft. Beginnt Ihr Vorname mit J-Z, dann schreiben Sie die Prüfung im Audimax.
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).

Datum	Thema
8. April	Intro
9. April	CSL und TM
15. April	Satz von Kuroda, Determinismus
16. April	Übung 1: CSL und LBA
22. April	Berechenbarkeit
23. April	Entscheidbarkeit
29. April	Satz von Immermann & Szelepcsényi
30. April	Übung 2: Alphabetsreduktion, Mehrband-TM
6. Mai	Die universelle TM, Unentscheidbarkeit
7. Mai	Reduktion, PCP
13. Mai	Satz von Rice
14. Mai	Übung 3: Berechenbare Funktionen
27. Mai	Unentscheidbare Probleme über CFL
28. Mai	Übung 4: Reduktionen
3. Juni	Komplexität, Landau-Notation
4. Juni	Komplexitätsklassen
10. Juni	L, NL, Reduktionen, Vollständigkeit
11. Juni	Übung 5: Komplexitätsanalyse, NL-Vollständigkeit
17. Juni	PATH, 2SAT
18. Juli	P, CVP, NP
24. Juli	SAT, PSPACE, QBF
25. Juli	Übung 6: NP-Vollständigkeit, 3SAT, 3-Färbbarkeit
1. Juli	Hamiltonian Cycle, Zertifikate
2. Juli	Satz von Savitch
8. Juli	Hierarchiesätze, Landkarte der Komplexitätstheorie
9. Juli	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.

15. April - 25. April: tutorium de
30. April - 9. Mai: tutorium de en
13. Mai - 23. Mai tutorium de
27. Mai - 6. Juni tutorium de en
10. Juni - 20. Juni tutorium de en
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

Handschriftliche Notizen zu einzelnen Themen der Vorlesung:

Videos aus vergangenen Online-Vorlesungen (Sommer 2020, Sommer 2021):

Abschlussklausur

Die Abschlussklausur findet am Dienstag, dem 16. Juli 2024 von 8:00 bis 10:00 Uhr im Audimax (Vorname J-Z), sowie UP 3.007 (Vorname A-I) 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]

Institute of

Theoretical Computer Science

Carl-Friedrich-Gauß-Fakultät

Technische Universität Braunschweig