Vorlesung: Theoretische Informatik 2
Sommersemester 2020
Neuigkeiten
- 07. August
-
Die Klausurergebnisse sind da. Aufgrund eines kleinen Fehlers in einer Aufgabenstellung, wurden die Notengrenzen angepasst.
Im folgenden findet ihr die anonymisierten Ergebnisse und die Statistik der Klausur.
- Neue PO: Ergebnisse, Statistik
- Alte PO: Ergebnisse, Statistik
- 27. Juli
- Die Raumaufteilung steht fest. Alle Studenten werden die Klausur in der Sporthalle Beethovenstraße 16 schreiben.
- 24. Juli
-
Das letzte Video zu den Hausaufgaben ist online.
Neue Informationen zu der Raumaufteilung sind da. Bitte überprüft diese noch einmal am Montag vor der Klausur. Es ist sehr wahrscheinlich, dass es eine weitere Änderung geben wird. - 23. Juli
- Die Fragestunde ist beendet. Ihr könnt den TUBS RocketChat jedoch bis zur Klausur weiterhin verwenden, um inhaltliche Fragen mit uns und euren Kommilitonen zu besprechen.
- 21. Juli
- Die Raumplanung für die Klausur wurde geändert.
- 16. Juli
-
- Der Teil des Scripts zur Komplexitätstheorie wurde aktualisiert.
- Zur Vorbereitung auf die Abschlussklausur empfiehlt sich das Durcharbeiten der Klausuren aus den vergangenen Jahren: Sommer 2017 , Winter 2017/18 , Sommer 2018 .
- 14. Juli
-
Das letzte Hausaufgabenblatt und die letzte große Übung sind nun online.
Da die Klausur bereits 4 Tage nach der Hausaufgabenabgabe ist, werden wir uns bemühen das Tutorium direkt am Tag der Abgabe hochzuladen.
Das Tutorium zu Blatt 5 ist nun online. - 08. Juli
- Die Informationen zu der Klausur wurden korrigiert.
- 07. Juli
-
Informationen zu der Klausur wurden hinzugefügt.
Das 4. Übungsvideo ist nun online. - 30. Juni
- Das neue Hausaufgabenblatt ist online. Das Übungsvideo ist nun auch online.
- 16. Juni
- Das neue Hausaufgabenblatt und die neue große Übung sind online.
- 15. Juni
- Die Kapitel 7 und 8 im Skript wurden überarbeitet.
- 12. Juni
- Das Tutorium zum dritten Hausaufgabenblatt ist online.
- 9. Juni
- Passend zur aktuellen Vorlesung wurde Kapitel 6 des Skripts überarbeitet.
- 30. Mai
- Die Vorlesung pausiert in der "Exkursionswoche" vom 1. - 7. Juni. Am 8.6 geht es weiter - stay safe!
- 26. Mai
- Das Tutorium zum zweiten Hausaufgabenblatt und das neue Hausaufgabenblatt sind online. Die große Übung ist online.
- 19. Mai
-
Die Videos zur dieswöchigen Vorlesung sind nun online und die entsprechenden Teile des Skripts wurden überarbeitet.
Das Tutorium zum ersten Hausaufgabenblatt ist nun online. - 12. Mai
- Das neue Hausaufgabenblatt ist online. Die neue große Übung ebenso. Das erste Tutorium zum ersten Übungsblatt wird in den folgenden Tagen bereitgestellt.
- 29. April
- Das Hausaufgabenblatt wurde um Zusatzinformation ergänzt, die Aufgabe 3 und 4 leichter machen.
- 28. April
-
Die erste große Übung ist nun online. Am Video gibt es einige Makel, die in den nächsten Wochen nicht wieder auftreten werden!
Die ersten Hausaufgaben sind online. Gebt diese bitte bis nächsten Freitag per E-Mail direkt an eure Tutoren ab. Jeder angemeldete Student sollte eine E-Mail mit seiner Gruppe und seinem eingeteilten Tutor bekommen haben (Falls nicht, schreibt Thomas Haas an).
Einige Fehler im Skript wurden korrigiert. - 19. April
- Zusätzliche Informationen, darunter auch das Anmeldeverfahren für die Tutorien, wurde hinzugefügt. Bitte meldet euch wie beschrieben bis zum Freitag, den 24.04 für die Übungen an.
- 07. April
- Die Vorlesungen, großen Übungen und kleinen Übungen werden aufgrund der momentanen Situation nur online angeboten. Dazu werden hier auf dieser Seite die jeweiligen Veranstaltungen in Videoform hochgeladen. Die Hausaufgabenabgabe und Korrektur wird ebenso online stattfinden. Das heißt, die Hausaufgaben müssen entweder eingescannt werden oder direkt z.B. über LateX als .pdf erstellt werden.
Vorlesung
- Die Dozenten der Vorlesung sind Prof. Dr. Roland Meyer, Sebastian Muskalla und Peter Chini.
- Prüfer der Vorlesung ist Prof. Dr. Roland Meyer.
- Eintrag im Vorlesungsverzeichnis: Vorlesung.
-
Vorlesungstermine: Die Vorlesungen werden im Videoformat hochgeladen zu den folgenden Zeiten,
zu denen normalerweise die Vorlesungen stattfinden würden:
- Montag, 13:15 - 14:45.
- Dienstag, 13:15 - 14:45 alle 14 Tage.
Übungsbetrieb
-
Große Übung, gehalten von Thomas Haas, wird alternierend mit der Vorlesung am Dienstag hochgeladen:
- Dienstag, 13:15 - 14:45 alle 14 Tage, an den Tagen an denen keine Vorlesung stattfindet.
-
Im zweiwöchigen Rhythmus werden auf dieser Seite Übungsblätter mit Hausaufgaben online gestellt.
Diese Hausaufgaben werden in 4er Gruppen bearbeitet und abgegeben.
In den kleinen Übungen werden die Hausaufgaben besprochen. Die kleinen Übungen werden von diversen Tutoren gehalten. Statt mehreren Tutorien werden die Tutoren abwechselnd ein Tutorium aufnehmen und auf dieser Seite für alle Studenten zugänglich machen. Die Tutoren sind:- René Maseli (r.maseli@tu-braunschweig.de)
- Jakob Tepe (j.tepe@tu-braunschweig.de)
- Chek-Manh Loi (c.loi@tu-braunschweig.de)
Vorlesungsvideos
Die Vorlesungen werden als Videos angeboten.- Woche 1: Wiederholung CSL und TM, CSL und LBA, Determinismus in TM.
- Woche 2: Satz von Immerman und Szelepcsényi.
- Woche 3: Berechenbarkeit.
- Woche 4: Entscheidbarkeit.
- Woche 5: Unentscheidbarkeit - Intro, Kodierung von TM, Die universelle TM, Unentscheidbarkeit von ACCEPT, Reduktionen.
- Woche 6: PCP.
- Woche 7: Rice.
- Woche 7: Unentscheidbare Probleme kontextfreier Sprachen.
- Woche 8 & 9: Grundlagen der Komplexitätstheorie - Intro, Landau-Notation, Komplexitätsklassen, Relationen, Komplementklassen, Landkarte der Komplexitätstheorie.
- Woche 9 & 10: Reduktionen und die Klassen L und NL - Reduktionen und Vollständigkeit, Path, 2-SAT, Probleme in L.
- Woche 11: P.
- Woche 11: NP - Intro, SAT, HamiltonianCycle, Zertifikate.
- Woche 12: QBF.
- Woche 13: Savitch.
- Woche 13: Hierarchiesätze (& Outro).
Weitere Materialien finden sich weiter unten auf dieser Seite.
Große Übungen
Die großen Übungen werden im Videoformat hier bereitgestellt.- Übung 1: CSL und LBAs
- Übung 2: Berechenbare Funktionen
- Übung 3: Reduktion
- Übung 4: Komplexitätsanalyse
- Übung 5: NL-vollständige Probleme
-
Übung 6: NP-vollständige Probleme (3-SAT, 3-COLORABILITY)
(*3-SAT wurde anscheinend schon in der Vorlesung behandelt*)
Übungsblätter
Die Übungsblätter werden während des Semesters hier zur Verfügung gestellt.Die Hausaufgabenabgabe und Korrektur erfolgt ausschließlich online. Scannt dazu eure handschriftlichen Hausaufgaben ein oder erstellt diese direkt in digitaler Form als .pdf (z.B. mit LateX), und sendet diese an den euch zugeteilten Tutor per E-Mail.
- Hochgeladen: 28.04.2020; Abgabe: 08.05.2020:
Blatt 1
- Hochgeladen: 12.05.2020; Abgabe: 22.05.2020:
Blatt 2
- Hochgeladen: 26.05.2020; Abgabe: 05.06.2020:
Blatt 3
- Hochgeladen: 16.06.2020; Abgabe: 26.06.2020:
Blatt 4
- Hochgeladen: 30.06.2020; Abgabe: 10.07.2020:
Blatt 5
- Hochgeladen: 14.07.2020; Abgabe: 24.07.2020:
Blatt 6
Modul
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.
Abschlussklausur
- Weitere Informationen zur Abschlussklausur werden wir Ihnen rechtzeitig zur Verfügung stellen.
-
Die Abschlussklausur findet in der ersten Woche der vorlesungsfreien Zeit am Dienstag, dem 28. Juli 2020, ab 16:30 Uhr statt.
Bitte erscheint rechtzeitig vor Beginn der Klausur. Zum Zweck des geordneten Ablaufs, wird der Einlass bereits ab 15:45 stattfinden. - Es gibt Änderungen der Raumpläne. Die Klausur findet in der Sporthalle (Beethovenstraße 16) statt.
- Die Bearbeitungszeit beträgt 120 Minuten für 7 Aufgaben (ab Prüfungsordnung 6 (2017)) bzw. 180 Minuten für 10 Aufgaben (PO 5 und älter).
- Als Hilfsmittel sind ausschließlich Sprachwörterbücher sowie ein beidseitig handschriftlich beschriebenes DIN A4-Blatt erlaubt.
Weitere Materialien
Vorlesungsnotizen:- Aktuelles Skript zu Theoretische Informatik 2 (wird während des Semesters aktualisiert)
- Ä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
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.