Institute of

Theoretical Computer Science

Carl-Friedrich-Gauß-Fakultät

Technische Universität Braunschweig

Vorlesung: Theoretische Informatik 2

Sommersemester 2024

News

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

Modul

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

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).

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 Probleme von CFL
28. Mai Übung 4: Reduktionen
3. Juni Komplexität, Landau-Notation
4. Juni Komplexitätsklassen
10. Juni Landkarte der Komplexitätstheorie
11. Juni Übung 5: Komplexitätsanalyse, NL-Vollständigkeit
17. Juni L, NL, Reduktionen, Vollständigkeit
18. Juli PATH, 2-SAT
24. Juli P, NP
25. Juli Übung 6: NP-Vollständigkeit
1. Juli SAT, Hamiltonian Cycle
2. Juli Zertifikate, QBF
8. Juli Satz von Savitch, Hierarchiesätze
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.

  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

Weiteres Material

Handschriftliche Notizen zu einzelnen Themen der Vorlesung: Videos aus vergangenen Online-Vorlesungen (Sommer 2020, Sommer 2021):

Abschlussklausur

Literatur