Institute of

Theoretical Computer Science

Carl-Friedrich-Gauß-Fakultät

Technische Universität Braunschweig

Vorlesung: Theoretische Informatik 2

Sommersemester 2022

Konferenzraum, Stud.IP: Vorlesung, Stud.IP: kleine Übung, Organisation, Material, Übungsblätter, Weiteres Material, Abschlussklausur.

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.titleavg.med.
1TM7,18
2NP5,97
3Ents.3,63
4NL5,56
5Ber.1,90
6Quiz3,33
7Zirk.1,90
total29,429
1,0 1,3 1,7 2,0 2,3 2,7 3,0 3,3 3,7 4,0 5,0 60 56 53 49 46 42 39 35 32 28 0 0 10 20 30 Die Prüfungsergebnisse der Abschlussklausur vom 2. August sind nun verfügbar: 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 64%.
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

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

Handschriftliche Notizen zu einzelnen Themen der Vorlesung:

Abschlussklausur

Literatur