Theoretical Computer Science

Vorlesung: Theoretische Informatik 2

Sommersemester 2022

News

5. September

Die Klausureinsicht findet online, oder bei Absprache in Person statt. Um sich einen Termin zu sichern, schreiben Sie eine Mail an René Maseli.

5. August

nr.	title	avg.	med.
1	TM	7,1	8
2	NP	5,9	7
3	Ents.	3,6	3
4	NL	5,5	6
5	Ber.	1,9	0
6	Quiz	3,3	3
7	Zirk.	1,9	0
	total	29,4	29

Die Prüfungsergebnisse der Abschlussklausur vom 2. August sind nun verfügbar:

• Ergebnisse

Eine Klausureinsicht wird im September stattfinden. Genaueres folgt in Kürze. Bei weiteren Fragen wenden Sie sich an René Maseli.
Eine Übersicht ist hier bereitgestellt. Die Bestehensquote beträgt 63%.

27. Juli

Die Prüfung am 2. August beginnt tatsächlich um 10:30 Uhr anstatt 12:30 Uhr. Wir möchten uns für diese Fehlinformation entschuldigen.

12. Juli

Sie können sich mit der Probeklausur auf die Klausur am 2. August vorbereiten. Die Aufgaben werden am 26. Juli besprochen.

21. Juni

Die großen Übungen verschieben sich nun dauerhaft um eine Woche (Beachten Sie den Vorlesungskalender). Auf die Hausaufgaben und die Tutorien hat dies aber keinen Einfluss; Diese finden nun in den selben Wochen wie die Große Übung statt.

18. Mai

Die kleinen Übungen vom 25. bis zum 27. Mai verschieben sich um eine Woche, also auf den 1. bis 3. Juni.

25. April

Die Anmeldung zu den kleinen Übungen und den Hausaufgaben ist ab heute freigeschaltet.

18. April

Die erste Vorlesung findet am 25.04. statt.

4. April

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.
• Vorlesungstermine:
  • Montag, 13:15 - 14:45 in PK 11.2.
  • Dienstag, 13:15 - 14:45 in PK 11.2, alle 14 Tage.
• Große Übung:
  • Dienstag, 13:15 - 14:45 in PK 11.2, alle 14 Tage, wenn keine Vorlesung stattfindet.
• Kleine Übung: alle 14 Tage, wenn eine Vorlesung Große Übung stattfindet, ab dem 11. Mai. In den kleinen Übungen werden die Hausaufgaben besprochen.
  • Mittwoch, 11:30 - 13:00 in IZ 358
    Tutor: Dennis Dinh (d.dinh@tu-braunschweig.de) [Upload]
  • Mittwoch, 13:15 - 14:45 in IZ 358
    Tutor: Dogukan Hizir (d.hizir@tu-braunschweig.de) [Upload]
  • Donnerstag, 15:00 - 16:30 in IZ 305
    Tutor: Jan Steiner (j.steiner@tu-braunschweig.de) [Upload]
  • Freitag, 9:45 - 11:15 in IZ 305
    Tutor: Jan Grünke (jan.gruenke@tu-braunschweig.de) [Upload]
• Im zweiwöchigen Rhythmus werden auf dieser Seite Übungsblätter mit Hausaufgaben online gestellt. Diese Hausaufgaben werden in Vierer-Gruppen bearbeitet und abgegeben. Um sich für die kleinen Übungen anzumelden, tragen Sie sich in diese Veranstaltung ein und schließen sich unter dem Teilnehmer/Participants-Reiter über die Gruppen/Groups-Ansicht einer Vierer-Gruppe Ihrer Wahl an. 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 zu Beginn des vorlesungsfreien Zeitraums.
  • Studienleistung: Zu erbringen durch das erfolgreiche Bearbeiten von mindestens 50% der Übungsaufgaben.

Material

Die Vorlesungen und Großen Übungen werden als Videos angeboten. In diesem Semester halten wir uns an folgendes Skript (Stand: 2022-07-07). Weitere Materialien finden sich weiter unten auf dieser Seite.

25. April

Intro, CSL und TM.

26. April

Satz von Kuroda und Determinismus in TMs.

2. Mai

Berechenbarkeit I.
siehe auch: A. M. Turing: On Computable Numbers, with an application to the Entscheidungsproblem [DOI] [PDF]

3. Mai

Übung 1: CSL und LBAs

9. Mai

Berechenbarkeit II.

10. Mai

Entscheidbarkeit.

16. Mai

Unentscheidbarkeit, Kodierung von TM, Die universelle TM.

17. Mai

Übung 2: Berechenbare Funktionen

23. Mai

Unentscheidbarkeit von ACCEPT, Reduktionen.

24. Mai

Satz von Rice. Post Correspondence Problem.

30. Mai

Unentscheidbare Probleme kontextfreier Sprachen.

31. Mai

Übung 3: Reduktion

13. Juni

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

14. Juni

Satz von Immerman und Szelepcsényi.

20. Juni

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

21. Juni

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

27. Juni

Path, 2-SAT.

28. Juni

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

4. Juli

Probleme in L. P, NP, SAT. HamiltonianCycle,

5. Juli

Zertifikate. Quantifizierte Boolsche Formeln.

11. Juli

Satz von Savitch.

12. Juli

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

18. Juli

Hierarchiesätze.

19. Juli

Klausurinfos.

25. Juli

Outro

26. Juli

Übung 6: Klausurvorbereitung

Übungsblätter

Die Übungsblätter werden während des Semesters hier zur Verfügung gestellt, jeweils an den Dienstagen, an denen eine Vorlesung stattfindet. Die Abgabe kann sowohl über den Briefkasten vor dem Raum IZ 343, als auch digital über die Dateien/Files auf Stud.IP erfolgen.

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

1. 26. April - 6. Mai pdf
2. 10. Mai - 20. Mai pdf
3. 24. Mai - 3. Juni pdf
4. 14. Juni - 24. Juni pdf
5. 28. Juni - 8. Juli pdf
6. 12. Juli - 22. Juli pdf

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 2. August 2022, ab 10:30 Uhr in den Räumen ZI 24.1 und ZI 24.2 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.
• Wenn Ihr Nachname mit einem der Buchstaben A - K beginnt, schreiben Sie die Klausur in Hörsaal ZI 24.1. Ansonsten, also wenn Ihr Nachname mit einem der Buchstaben L - Z beginnt, schreiben Sie die Klausur in ZI 24.2.
• 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.

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.