Vorlesung: Theoretische Informatik I
Wintersemester 2016/17 in Braunschweig
Neuigkeiten
- Die Informationen zur Nachklausur vom 30.08.2017 finden Sie auf folgender Seite: Klausur: Theoretische Informatik I 30.08.2017
- Die Klausureinsicht findet am Donnerstag, den 23.02 um 10:00 Uhr in Raum IZ 305 statt.
- Am Montag, den 13.02. um 13:15 findet in PK 2.2 eine weitere Großübung statt. Wir werden zusammen eine Altklausur durchrechnen.
- Die erste Version des getexten Skripts ist nun online.
- Termin und Ort der Klausur wurden aktualisiert: Mehr unter Prüfungsmodalitäten.
- Die Übung von Gruppe 1 am Donnerstag den 26.01 um 9:45 wird in den Raum 359 verlegt.
- Umstellung des Übungsbetriebs: nach der Winterpause werden die kleinen Übungen immer in der Vorlesungswoche stattfinden. Das bedeutet, die erste Übung im neuen Jahr wird in der Woche vom 9. Januar veranstaltet. In dieser Übung wird das Weihnachtsübungsblatt besprochen, welches bis 9. Januar 12:00 Uhr abzugeben ist. Nach dem Weihnachtsübungsblatt wird das aktuelle Übungsblatt dann immer zweiwöchentlich mittwochs herausgegeben. Dieses ist dann bis mittwochs in der Folgewoche abzugeben.
- Ab sofort gibt es getexte Notizen zu Kapitel 6: Reduktionssysteme, Kontextfreie Grammatiken und die Chomsky Hierarchie. Vielen Dank an Mike Becker.
- Update von Übungsblatt zwei: in Aufgabe 2.3 wurde ein Hinweis hinzugefügt.
- Das erste Übungsblatt ist online.
- Bitte tragen Sie sich zur Auswahl eines Übungstermins in eine der aushängenden Listen im Institut für Theoretische Informatik, neben Büro 342, ein.
- Es finden im zweiwöchigen Rhytmus jeweils zwei Vorlesungen pro Woche statt. Die ersten beiden Vorlesungen finden am 24. und 25. Oktober statt.
- In den Wochen in denen keine Vorlesung stattfindet, wird es eine Großübung/Tutorium geben. Diese wird erstmals am 31.10.2016 veranstaltet. Wir werden Fragen zur Vorlesung klären oder Beispiele durchrechnen. Die (kleinen) Übungsstunden finden ebenfalls in dieser Woche statt und beginnen am 1.11.2016. Hier werden die Lösungen zu den Übungsaufgaben diskutiert.
Vorlesung
- Die Vorlesung wird von Prof. Roland Meyer gehalten.
- Eintrag im Vorlesungsverzeichnis: Vorlesung, Übungen.
-
Vorlesungstermine:
- Montag, 13:15 - 14:45 in PK 2.2
- Dienstag, 15:00 - 16:30 in PK 2.2
Großübung
- Die Großübung findet immer montags in der vorlesungsfreien Woche um 13:15 - 14:45 in PK 2.2 statt.
Übungen
- Die Übungen beginnen am 01.11.2016.
- Die Übungen werden von Jürgen Koslowski, Peter Chini und Sebastian Muskalla, organisiert.
-
Alle Übungen finden im Gebäude des Instituts für Theoretische Informatik statt. Die Übungstermine sind wie folgt:
- Gruppe 0: Dienstags, 16:45 - 18:15 in 305
- Gruppe 1: Donnerstags, 9:45 - 11:15 in 161
- Gruppe 2: Donnerstags, 9:45 - 11:15 in 358
- Gruppe 3: Donnerstags, 9:45 - 11:15 in 305
- Gruppe 4: Donnerstags, 16:45 - 18:15 in 305
- Gruppe 5: Freitags, 11:30 - 13:00 in 305
- Es gibt zweiwöchentlich 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.
Übungsblätter
- Übungsblatt 1
- Übungsblatt 2
- Übungsblatt 3
- Übungsblatt 4
- Übungsblatt 5 - Weihnachtsübung
- Übungsblatt 6
- Übungsblatt 7
Prüfungsmodalitäten
Es wird eine Abschlussklausur geben. Diese findet am Donnerstag, dem 16. Februar 2017, ab 8:00 Uhr im AudiMax statt. Die Klausur wird aus zehn Aufgaben bestehen, die Bearbeitungszeit beträgt 120 Minuten. Zur Klausur darf ein beidseitig beschriebenes (handschriftlich!) DIN A4-Blatt mitgebracht werden.Zudem ist eine gesonderte Studienleistung zu erbringen: Sie müssen durch Ihre Abgabe der Übungsblätter mindestens 50 Prozent der Punkte erreichen.
Material
Es gibt handschriftliche Notizen zu einzelnen Themen der Vorlesung. Zusätzlich gibt es ein in diesem Semester getextes Skript. Wir weisen darauf hin, dass es sich bei dem Skript um eine erste Version handelt. Wir geben keine Garantie auf Vollständigkeit und Korrektheit.- Folien zu regulären Sprachen und weiterführenden Resultaten.
- Regular languages and finite automata.
- Equivalence.
- Homomorphisms.
- Complexity of problems for regular languages.
- Minimization.
- Pumping lemma for regular languages and ultimate periodicity.
- Overview of the results for regular languages.
- Reduktionssysteme, Kontextfreie Grammatiken und die Chomsky Hierarchie.
- Nikolausvorlesung zu sprachtheoretischer Verifikation, 2-Player-Perfect-Information-Games und Transitionsmonoiden endlicher Automaten.
- Normal forms for context-free grammars.
- Pumping lemmas for context-free languages.
- Pushdown automata and context-free languages.
- Closure properties of context-free languages.
- Deterministic context-free languages and complementation.
- Decision algorithms for context-free languages.
- Context-sensitive languages.
- Immermann and Szelepcséyi's theorem.
Literatur
- Schöning: Theoretische Informatik - kurzgefasst.
- Hopcroft, Motwani, Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie.
- Nebel: Formale Grundlagen der Programmierung.
- Sipser: Introduction to the Theory of Computation.