Institute of

Theoretical Computer Science

Carl-Friedrich-Gauß-Fakultät

Technische Universität Braunschweig

Vorlesung: Theoretische Informatik 2

Sommersemester 2018

Neuigkeiten

12. März
Die Informationen zur Nachklausur am 14.03.2019 finden Sie auf folgender Seite: Klausur: Theoretische Informatik 2
19. Juli
Die Einsicht wird am 24.07 ab 10:00 in IZ 358 stattfinden.
19. Juli
Die Ergebnisse der Abschlussklausur vom 17. Juli sind nun verfügbar: Die Ergebnisse der Studierende, die nach BPO 2017 studieren, sind nicht in der Liste eingetragen. Die Ergebnisse können bei Elisabeth Neumann in IZ 344 eingesehen werden.
16. Juli
Da ausreichend Plätze im AM vorhanden sind, wird die Abschlussklausur am Dienstag, dem 17. Juli 2018 ab 08:30 ausschließlich im AM stattfinden. Es erfolgt keine Aufteilung in zwei Räume.
3. Juli
Wir weisen darauf hin, dass PSPACE in diesem Jahr klausurrelevant ist.
3. 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 2 Zusatzaufgaben zu PSPACE online gestellt. Es soll nicht abgegeben werden und wird nicht bewertet. Wir werden die Aufgaben in den Großübungen zur Klausurvorbereitung (09. und 10. Juli) in Raum PK2.2 vorrechnen.
3. Juli
Details zu der Abschlussklausur sind nun (unten) verfügbar. Die Raumeinteilung folgt noch.
3. Juli
In der nächsten Woche findet keine Vorlesung statt. Anstelle werden wir an beiden Terminen (09. und 10. Juli) die Abschlussklausur vom letzten Jahr und Blatt 7 durchrechnen. Falls die Zeit nicht ausreicht um alle Aufgaben durchzurechnen, führen wir die Großübung am 10. Juli ab 16:45 in PK 2.2 fort.
18. Juni
Wir weisen darauf hin, dass in der Prüfungsprotokollsammlung der Fachgruppe und im Sekretariat (IZ. 345) die Altklausuren verfügbar sind.
18. Juni
Die getexten Vorlesungsnotizen zu den letzten beiden Vorlesungen (11. und 12. Juni) sind nun verfügbar. Kapitel 1 wurde um einen Paragraphen zu verschiedenen Varianten von Turing Maschinen ergänzt.
14. Mai
Nachtrag zu der 5-PATH Aufgabe aus der letzten Großübung.
14. Mai
Die getexten Vorlesungsnotizen zu den letzten drei Vorlesungen (7. , 8. und 14. Mai) sind nun verfügbar. Definition 3.16 wurde dabei ergänzt und zwei Bemerkungen hinzugefügt.
8. Mai
Nächste Woche wird Übungsblatt 4 herausgegeben und es finden eine Vorlesung sowie ein Tutorium statt. Aufgrund der Exkursionswoche entfallen die Vorlesungen in der Woche vom 21.-25. Mai. In der darauffolgenden Woche (28. Mai - 1. Juni) muss Blatt 4 abgegeben werden und es finden 2 Vorlesungen statt. Danach finden die Veranstaltungen wieder im gewohnten zweiwöchigen Rhythmus statt.
7. Mai
Am 8. Mai findet die Vorlesung statt. Die nächste Großübung findet am 15. Mai statt.
27. April
Aufgrund des Feiertages am 1. Mai, wird das Aufgabenblatt bereits am Montag, dem 30. April veröffentlicht. Die Lösung muss bis zum 9. Mai 12:00 eingereicht werden.
27. April
Die getexten Vorlesungsnotizen zu den letzten beiden Vorlesungen (23. und 24. April) sind nun verfügbar.
24. April
In dieser Woche (25.-27. April) finden keine kleinen Übungen statt. Aufgrund des Feiertages, entfällt die Großübung am 1. Mai. Die nächste Großübung findet am 15. Mai statt.
19. April
Die getexten Notizen zu der letzten Vorlesung sind nun verfügbar.
10. April
Die getexten Vorlesungsnotizen zu den Kapiteln über kontextsensitive Sprachen und dem Satz von Satz von Immermann und Szelepcséyi sind nun verfügbar.
10. April
Raumänderung: Die kleine Übung von Lucas Rösner (Mittwoch, 15:00 - 16:30) wird in den Raum IZ 161 verschoben.
10. April
Das erste Übungsblatt (Präsenz-Übungsblatt) ist online.
3. April
Nächste Woche finden zwei Vorlesungen, am 9. und 10. April, statt. Die ersten Übungsstunden finden am 11., 12. und 13. April statt. In diesen Übungen wird ein Präsenz-Übungsblatt bearbeitet. Das erste Übungsblatt (zur Abgabe) wird am 19. April herausgegeben.
3. 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 10. April, 15:00, in eine Übungsgruppe ein. Eine Liste der angebotenen Termine finden Sie weiter unten auf dieser Seite.
28. März
Die erste Vorlesung findet am Dienstag, dem 03.04.2017 von 13:15 - 14:45 in Raum PK 2.2 statt.
28. März
Im zweiwöchigen Rhythmus finden jeweils abwechselnd zwei Vorlesungen beziehungsweise eine Vorlesung und eine Großübung pro Woche statt.

Vorlesung

Großübung

Übungen

Übungsblätter

Die Übungsblätter werden während des Semesters hier zur Verfügung gestellt. Kontakten Sie bei Fragen zu den Übungsblättern Ihren Tutor oder Elisabeth Neumann.

Prüfungsmodalitäten

Modul

Abschlussklausur

Material

Wir bieten geTeXte Vorlesungsnotizen an.

Vorlesungsnotizen (Sommersemester 2017) und Vorlesungsnotizen (Sommersemester 2018)

Zudem gibt es handschriftliche Notizen zu einzelnen Themen der Vorlesung.
  1. Context-sensitive languages.
  2. Immermann and Szelepcséyi's theorem.
  3. Berechenbarkeit.
  4. Unentscheidbarkeit, die universelle Turing-Maschine, das Halteproblem, Reduktionen
  5. Post's theorem and Rice's theorem
  6. Unentscheidbare Probleme der kontextfreien Sprachen
  7. Zeit- und Platzkomplexitätsklassen
  8. Summary of the relationship among the robust complexity classes
  9. L und NL
  10. Satz von Immerman und Szelepcsényi
  11. P and NP
  12. PSPACE
  13. Satz von Savitch
Die folgenden Notizen aus den Vergangenen Jahren werden wir im Laufe des Semesters in die obige Liste einpflegen. Als weitere Materialien verweisen wir auf die folgenden Vorlesungsnotizen.

Literatur