Theoretical Computer Science

Vorlesung: Theoretische Informatik II

Sommersemester 2017 in Braunschweig

Neuigkeiten

17. Februar

Es gibt nun eine Informationsseite zur Abschlussklausur am 15. März.

31. Juli

Die Ergebnisse der Abschlussklausur vom 18. Juli sind nun verfügbar:

• Statistische Auswertung und Notengrenzen
• Ergebnisse

24. Juli

Die Klausureinsicht zur Abschlussklausur wird am Dienstag, dem 08. August, ab 14:00 in Raum IZ 358 stattfinden.

12. Juli

Die Raumaufteilung für die Abschlussklausur ist nun verfügbar (siehe unten).

12. Juli

Wir werden vor der Abschlussklausur eine Fragestunde anbieten, und zwar am Montag, dem 17. Juli, ab 13:15 in Raum PK2.2 (Raum und Termin der Vorlesung).

9. Juli

Die Vorlesungsnotizen umfassen nun den Stoff zu deterministischer Polynomialzeit (P).
Wir bedanken uns bei allen Studierenden, die uns bereits Fehler im Script gemeldet haben und freuen uns über weitere Hinweise.

6. Juli

Das 6. Übungsblatt war das letzte Übungsblatt, das bepunktet wird und damit relevant für die Studienleistung ist.
Wir haben ein 7. Übungsblatt mit Zusatzaufgaben zur Vorbereitung auf die Klausur online gestellt. Es soll nicht abgegeben werden und wird nicht bewertet. Wir werden die Aufgaben in einer freiwilligen Großübung am Dienstag, dem 11. Juli, um 17 Uhr in Raum PK2.2 vorrechnen.

6. Juli

Eine aktualisierte Version der Vorlesungsnotizen, die den Stoff bis einschließlich Woche 11 (L, NL, coNL) beinhaltet, ist nun verfügbar.

22. Juni

Am Dienstag, dem 27.06, werden wir ab 17 Uhr in Raum PK2.2 eine weitere Großübung anbieten.

15. Juni

Um den Vorlesungsstoff in vollem Umfang präsentieren zu können, werden wir die beiden Vorlesungen, die Aufgrund von Feiertagen (17. April und 1. Mai) ausgefallen sind, nachholen. Daher werden wir an den nächsten beiden regulären Terminen der Großübung stattdessen eine Vorlesung anbieten. Die Großübung verschieben wir auf einen Zusatztermin am selben Abend, ab 17:00 in Raum PK2.2. Mit anderen Worten:

• 20.06, 13:15, PK2.2: Vorlesung statt Großübung
• 20.06, 17:00, PK2.2: Ersatztermin Großübung (Notizen)
• 04.07, 13:15, PK2.2: Vorlesung statt Großübung
• 04.07, 17:00, PK2.2: Ersatztermin Großübung

15. Juni

Mehr Informationen zur Abschlussklausur in der ersten Woche der vorlesungsfreien Zeit am Dienstag, dem 18. Juli, sind nun weiter unten auf dieser Seite zu finden.

12. Juni

Am Dienstag, dem 13. Juni, findet eine Vorlesung statt (und keine Großübung).

30. Mai

Aufgrund der Exkursionswoche entfallen die Vorlesungen in der Woche vom 5. - 9. Juni.

30. Mai

Die erste Version der geTeXten Vorlesungsnotizen ist nun verfügbar.

2. Mai

Der Termin für; die Abschlussklausur ist nun weiter unten auf dieser Seite zu finden.

6. April

Zur Anmeldung für die Übungsgruppen erfolgt über Zettel. Diese hängen nun im Institut für Theoretische Informatik neben Raum 344 aus. Bitte tragen Sie sich, wenn Sie an den Übungen teilnehmen wollen, bis Dienstag, den 11. April, 13:30, in eine Übungsgruppe ein. Eine Liste der angebotenen Termine finden Sie weiter unten auf dieser Seite.

5. April

Das erste Übungsblatt ist online, und muss bis Donnerstag, 13. April, in Dreier- oder Vierergruppen abgegeben werden. Die erste Übungsstunde, in der dieses Blatt besprochen wird, findet in der 3. Vorlesungwoche (19. - 21. April) statt.

3. April

Die erste Vorlesung findet am Montag, dem 03.04.2017 von 13:15 - 14:45 in Raum PK 2.2 statt.

3. April

Im zweiwöchigen Rhytmus finden jeweils abwechselnd zwei Vorlesungen beziehungsweise eine Vorlesung und eine Großübung pro Woche statt.

Vorlesung / Großübung

• Die Vorlesung wird von Prof. Roland Meyer und Sebastian Muskalla gehalten. Die Großübung wird von Peter Chini gehalten.
• Eintrag im Vorlesungsverzeichnis: Vorlesung, Übung.
• Vorlesungstermine:
  • Montag, 13:15 - 14:45 in PK 2.2
  • Dienstag, 13:15 - 14:45 in PK 2.2

Übungen

• Es gibt alle zwei Wochen ein Übungsblatt zur Abgabe. Ihre Lösungen reichen Sie bitte in Gruppen von 3 bis 4 Personen ein. Dazu dient eine Box im Institut für Theoretische Informatik, neben Büro 343. Die Lösungen werden in den Übungsstunden besprochen. Jede Aufgabe wird mit einer Punktzahl zwischen 0 und 2 bewertet.
• Die Übungen werden von Sebastian Muskalla organisiert.
• Alle Übungen finden im Gebäude des Instituts für Theoretische Informatik in Raum 305 statt. Die angebotenen Übungstermine sind wie folgt:
  • Gruppe 1: Mittwoch, 15:00 - 16:30, Tutor: Michael Perk
  • Gruppe 2: Donnerstag, 8:00 - 9:30, Tutor: Benedikt Fuhrmann
  • Gruppe 3: Donnerstag, 13:15 - 14:45, Tutorin: Leonie Basso
  • Gruppe 4: Donnerstag, 15:00 - 16:30, Tutor: Jonathan Kolberg
  • Gruppe 5: Freitag, 9:45 - 11:15, Tutor: Malte Klingenberg
  Die Übungstermine finden ebenfalls nur alle zwei Wochen statt, jeweils in der Woche, nachdem ein Übungsblatt abgegebe wurde.

Übungsblätter

• Übungsblatt 1
• Übungsblatt 2
• Übungsblatt 3
• Übungsblatt 4
• Übungsblatt 5
• Übungsblatt 6
• Übungsblatt 7 (Zusatzaufgaben zur Klausurvorbereitung)

Prüfungsmodalitäten

• Prüfungsleistung: Schriftliche Abschlussklausur.
• Studienleistung: Sie müssen durch Ihre Abgabe der Übungsblätter mindestens 50 Prozent der Punkte erreichen.

Modul

• Prüfungsleistung: Schriftliche Abschlussklausur.
• Studienleistung: Sie müssen durch Ihre Abgabe der Übungsblätter mindestens 50 Prozent der Punkte erreichen.

Abschlussklausur

• Die Abschlussklausur wird am Dienstag, dem 18. Juli 2017, ab 8:30 stattfinden.
• Die Abschlussklausur findet verteilt in den Raumen ZI 24.1, PK 2.1 und PK 11.1 statt. In welchem Raum Sie die Klausur schreiben, hängt vom Anfangsbuchstaben Ihres Nachnamens ab:
  • Anfangsbuchstabe A - F in Raum PK 11.1,
  • Anfangsbuchstabe G - M in Raum ZI 24.1 (Grotrian),
  • Anfangsbuchstabe N - Z in Raum PK 2.1.
• Die Bearbeitungszeit der Klausur beträgt 180 Minuten.
• Die Klausur umfasst den kompletten Stoff der Vorlesung. Die Klausuraufgaben orientieren sich an den Übungsaufgaben auf den Aufgabenblättern.
• Als Hilfsmittel ist ein beidseitig von Hand beschriebenes DIN A4 Blatt erlaubt.
• Die Klausureinsicht wird am Dienstag, dem 08. August, ab 14:00 in Raum IZ 358 stattfinden

Material

Vorlesungsnotizen (zuletzt aktualisiert am 16. Juli)

1. Fixpunkte (Woche 1)
2. Datenflussanalyse (Woche 1/2)
3. Folien zu Datenflussanalyse (Woche 2)
4. Unentscheidbarkeit, die universelle Turing-Maschine, das Halteproblem, Reduktionen (Woche 7)
5. Post's theorem and Rice's theorem (Woche 8/9)
6. Unentscheidbare Probleme der kontextfreien Sprachen (Woche 9)
7. Zeit- und Platzkomplexitätsklassen (Woche 9/10)
8. Summary of the relationship among the robust complexity classes (Woche 10)
9. L und NL (Woche 10/11)
10. Satz von Immerman und Szelepcsényi (Woche 11)
11. P and NP (Woche 12)
12. PSPACE (Woche 13)
13. Satz von Savitch (Woche 13)

• Space vs. time, non-determinism vs. determinism.
• Space and time hierarchy results.
• Translation theorems.
• Models of computation for L and NL.

• Notizen zur Vorlesung Theoretische Informatik I
• Notizen zur Vorlesung Komplexitätstheorie
• Notizen zur Vorlesung Programmanalyse / Bäume, Ordnungen & Anwendungen
• Notizen zu den Vorlesungen Theorischer Informatik I & II von Prof. Adamek

Literatur

• F. Nielson, H. R. Nielson, C. Hankin: Principles of Program Analysis. Springer, 2005.
• U. P. Khedker, A. Sanyal, B. Karkare: Data Flow Analysis - Theory and Practice. CRC Press, 2009.
• H. Seidl, R. Wilhelm, S. Hack: Übersetzerbau - Analyse und Transformation. Springer, 2010.
• R. Berghammer: Ordnungen, Verbände und Relationen mit Anwendungen. Springer, 2012.
• G. Grätzer: General Lattice Theory. Birkhäuser, 2003.
• G. Birkhoff: Lattice Theory. Providence, 1967.
• 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.