Theoretical Computer Science

Formale Grundlagen der Programmierung 2016

Neuigkeiten

• Die Ergebnisse der Nachklausur stehen fest.
  • Die Ergebnisse können im STATS eingesehen werden.
  • Ab 40 Punkten bzw. Note 4.0 zählt die Klausur als bestanden.
  • Die Klausureinsicht wird am Donnerstag, dem 13. Oktober 2016, um 14:00 in Raum 34-420 stattfinden.
• Die Anmeldungen für die Nachklausur ist im STATS freigeschaltet.
• Sie dürfen auch dann an der Nachklausur teilnehmen, wenn Sie die Zwischenklausur(en) nicht bestanden haben.
• Die Ergebnisse der Abschlussklausur stehen fest.
  • Die Ergebnisse können im STATS eingesehen werden.
  • Ab 40 Punkten bzw. Note 4.0 zählt die Klausur als bestanden.
  • Die Klausureinsicht wird am Dienstag, den 27. September, um 13:00 in Raum 34-420 stattfinden.
  • Das Prüfungsamt hat die Anmeldefrist für die Nachklausur ausnahmsweise auf 7 Tage gesenkt. Sie können sich also nach der Klausureinsicht in der Woche vom 26. - 30. gegebenfalls für die Nachklausur anmelden, falls Sie die erste Klausur auch nach der Klausureinsicht nicht bestanden haben.
• Die Anmeldungen für die erste Abschlussklausur und zweite Zwischenklausur sind im STATS freigeschaltet.
• Für die Übung von Joshua am Dienstag gibt einen Zusatztermin ohne Anwesenheitspflicht am Dienstag, den 26.07. um 10:30 in 34-420.
• Die Einsichtnahme für die Zwischenklausur wird am Mittwoch, dem 13. Juli 2016, ab 17:00 in 34-420 stattfinden.
• Die Ergebnisse der Zwischenklausur stehen fest.
  • Die Ergebnisse können im STATS eingesehen werden.
  • Ab 40 Punkten bzw. Note 4.0 zählt die Klausur als bestanden.
• Die Anmeldung für die Zwischenklausur ist im STATS freigeschaltet.
• Es gibt eine einmalige Raumänderung: Die Übung am Mittwoch, den 25.05.2016 um 10:00-11:30 findet statt in 46/270.
• Die Klausurtermine stehen fest.
• Am Donnerstag, den 26.05.2016 ist ein Feiertag. Für die Übung gibt es einen Ersatztermin am Dienstag, den 31.05. um 11:45 in 13-370.
• Es gibt wieder permanente Raumänderungen: Die Übung am Mittwoch 10:00-11:30 findet statt in 46-220. Die Übung am Mittwoch 11:45-13:15 findet nun statt in 52-203.
• Am Donnerstag, den 05.05.2016 ist ein Feiertag. Für die Übung gibt es einen Ersatztermin am Dienstag, den 10.05. um 11:45 in 13-370.
• Es gibt permanente Raumänderungen: Die Übung am Mittwoch 10:00-11:30 findet nun statt in 36-265. Die Übung am Dienstag 15:30-17:00 findet nun statt in 34-420.
• Es gibt eine Raumänderung: Die Übung am Mittwoch 10:00-11:30 findet nun statt in 46-220.
• Die Übungstermine stehen fest und die Anmeldung ist im STATS freigeschaltet.

Vorlesung

• Die Vorlesung wird von Prof. Roland Meyer gehalten.
• Der KIS-Eintrag der Veranstaltung ist hier.
• Vorlesungstermine:
  • Dienstags, 10:00 - 11:30 in 52-207
  • Freitags, 13:45 - 15:15 in 46-220

Übungen

• Die Übungen beginnen am Mittwoch, den 27.04.2016.
• Die Organisation der Übungen erfolgt über STATS. Bitte legen Sie sich dafür gegebenfalls im STATS einen Account an.
• Die Übungen werden von Florian Furbach organisiert.
• Es werden folgende Übungstermine angeboten::
  • Dienstags, 11:45 - 13:15 in 48-379 Tutor: Joshua Blickensdörfer
  • Dienstags, 15:30 - 17:00 in 34-420 Tutor: Florian Wetzels
  • Mittwochs, 10:00 - 11:30 in 46-220 Tutor: Florian Wetzels
  • Mittwochs, 11:45 - 13:15 in 52-203 Tutor: Joshua Blickensdörfer
  • Mittwochs, 15:30 - 17:00 in 48-453 Tutor: Matthias Lederer
  • Donnerstags, 15:30 - 17:00 in 11-241 Tutor: Matthias Lederer
• Es gibt wöchentlich ein Übungsblatt mit abwechselnd Aufgaben zur Abgabe und Präsenz-Aufgaben. Zu ersteren geben Sie Lösungen ab und letztere bearbeiten Sie gemeinsam in der Übung.
• Die Übungsblätter werden dienstagabends hier veröffentlicht.
• Die Lösungen zu den Abgabe-Blättern sind bis 1 Woche später dienstags 12.00 Uhr abzugeben. Die entsprechenden Kästen finden sich im Treppenhaus von Gebäude 34, 4. Stock, nahe Raum 401 und der AG Softwaretechnik.
• Bitte geben Sie zu zweit oder zu dritt ab.
• Bitte beachten Sie, dass die Übungen verpflichtend sind.

Übungsblätter

• Präsenzblatt 1
• Abgabeblatt 2
• Präsenzblatt 3
• Abgabeblatt 4
• Präsenzblatt 5
• Abgabeblatt 6
• Präsenzblatt 7
• Abgabeblatt 8
• Präsenzblatt 9
• Präsenzblatt 10
• Abgabeblatt 11
• Abgabeblatt 12
• Präsenzblatt 13

Prüfungsmodalitäten

• Die Zwischenklausur ist zu bestehen
• Es sind 60% der Übungsaufgaben mit einem Plus ("sinnvoll bearbeitet") zu lösen.
• Es ist eine Aufgabe an der Tafel vorzustellen.

2. Abschlussklausur / Nachklausur

• Die Einsichtnahme wird am Donnerstag, dem 13. Oktober 2016, ab 14:00 in 34-420 stattfinden.
• Die Nachklausur wird am Montag, dem 10. Oktober 2016, ab 08:00 in der Mensa stattfinden.
• Um die Abschlussklausur mitschreiben zu dürfen, ist eine Klausurzulassung nötig, wobei Sie die Zwischenklausur(en) nicht bestanden haben müssen.
• Melden Sie sich im STATS für die Klausur an, um teilzunehmen.

Abschlussklausur & 2. Zwischenklausur

• Die Abschlussklausur wird am Donnerstag, dem 08. September 2016, ab 08:30 in Raum 46-215 stattfinden.
• Melden Sie sich bis zum Freitag, dem 02. September im STATS für die Klausur an, um teilzunehmen.
• Als Hilfsmittel zugelassen ist ein beidseitig von Hand beschriebenes DIN A4 Blatt.

1. Zwischenklausur

• Die Einsichtnahme wird am Mittwoch, dem 13. Juli 2016, ab 17:00 in 34-420 stattfinden.
• Die Zwischenklausur wird am Dienstag, dem 28. Juni um 17:15 in Raum 46-220 stattfinden.
• Melden Sie sich bis zum Dienstag, dem 21. Juni im STATS für die Zwischenklausur an, um teilzunehmen.
• Als Hilfsmittel zugelassen ist ein beidseitig von Hand beschriebenes DIN A4 Blatt.
• Falls Sie die erste Zwischenklausur nicht mitschreiben oder nicht bestehen, kann auch der erste Termin der Abschlussklausur im September als Zwischenklausur geschrieben werden, dann allerdings über den kompletten Stoff der Vorlesung!

Material

1. Folien zu regulären Sprachen und weiterführenden Resultaten.
2. Regular languages and finite automata.
3. Equivalence.
4. Homomorphisms.
5. Complexity of problems for regular languages.
6. Minimization.
7. Pumping lemma for regular languages and ultimate periodicity.
8. Overview of the results for regular languages.
9. The lecture notes and slides of Prof. Dr. Eike Best, University of Oldenburg, can be found on this page. The lecture is called Theoretische Informatik II in Oldenburg.
10. Normal forms for context-free grammars.
11. Pumping lemmas for context-free languages.
12. Pushdown automata and context-free languages.
13. Closure properties of context-free languages.
14. Deterministic context-free languages and complementation.
15. Decision algorithms for context-free languages.
16. Context-sensitive languages.
17. Immermann and Szelepcséyi's theorem.
18. Fixed points.
19. Data flow analysis.
20. Data flow analysis (slides).
21. Operational semantics. Nicht relevant für die Zwischenklausur.
22. Denotational semantics.
23. Axiomatic semantics and program verification.
24. Verification conditions.
25. Computability.
26. Universal Turing machine, halting problem, reduction.
27. Post's theorem and Rice's theorem.
28. Undecidable problems about context-free languages.

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.
• Friedman, Wand: Essentials of Programming Languages.
• Winskel: The Formal Semantics of Programming Languages: An Introduction.
• Reynolds: Theories of Programming Languages.