Vorlesung Automatentheorie
Aktuelles
- Vorerst haben wir vereinbart: Die Vorlesung fängt dienstags Punkt 15:00 Uhr und freitags Punkt 11:00 Uhr an. Nach einem entspannten Mittagessen treffen wir uns dann freitags 13:30 Uhr zur Übung.
- Die Eröffnungsvorlesung fand am Freitag, dem 19. April 2024, statt.
Einführung
Wir befassen uns in der Vorlesung mit der Theorie endlicher Automaten auf endlichen und unendlichen Wörtern, sowie auf Bäumen. Hierbei untersuchen wir verschiedene Typen von Automaten, deren Abschlusseigenschaften und Umwandlungsmöglichkeiten zwischen verschiedenen Modellen, verschiedene Entscheidungsprobleme (bspw. Leerheits- oder das Äquivalenzproblem) und deren Beziehungen zu verschiedenen Logiken wie LTL, CTL und MSO.
Logbuch
Im Logbuch werden regelmäßig Informationen bekannt gegeben.
Termine
- Vorlesung
- Dienstag 15:00-17:00, Schrödinger-Zentrum (RUD26), Raum 1'305 und
Freitag 11:00-13:00, Schrödinger-Zentrum (RUD26), Raum 1'305 - Übung
- Freitag 13:00-15:00, Schrödinger-Zentrum(RUD26),Raum1'305
Tutor:
Dorian Gutschenreiter
Übungsblätter
Ab der zweiten Vorlesungswoche wird wöchentlich, jeweils freitags ein Übungsblatt hier und im Moodle-Kurs online bereitgestellt.
Verbindliche "Spielregeln" zum Erwerb von Übungspunkten
Sie können bei jedem Übungsblatt entscheiden, gemäß welcher der folgenden beiden Varianten A bzw. B Ihre Lösung bewertet werden soll:
-
Variante A:
Sie geben eine schriftliche, ausführlich ausgearbeitete und mathematisch präzise Lösung spätestens direkt vor Beginn der Übungsstunde am Freitag im Moodle-Kurs ab. -
Variante B:
Sie geben keine Lösung ab. Stattdessen tragen Sie direkt vor Beginn der Übung in eine bereitgestellte Liste ein, wie viele Übungspunkte Sie für Ihre Lösung der einzelnen Aufgaben(teile) für gerechtfertigt halten. Während der Übungsstunde werden aus dieser Liste einzelne Teilnehmer zum Vorrechnen von Aufgaben(teilen) ausgesucht. Falls sich beim Vorrechnen herausstellen sollte, dass Sie keine sinnvolle Lösung vorweisen können, obwohl Sie in der Liste Punkte für diese(n) Aufgabe(nteil) eingetragen haben, werden Ihnen für das gesamte gerade behandelte Übungsblatt keine Übungspunkte angerechnet. Eine sinnvolle Lösung muss hierbei nicht notwendigerweise vollständig korrekt sein
Prüfung
Zur Vorbereitung auf eine Prüfung (Modulabschlussprüfung) ist es unbedingt notwendig, das gesamte in den Vorlesungs- und Übungsstunden behandelte Material durchzuarbeiten.
Die Modulabschlussprüfung wird durch eine mündliche Prüfung erfolgen.
Voraussetzung für die Zulassung zur Prüfung ist:
- Erreichen von mindestens 50 Prozent aller Übungspunkte. Um dies zu gewährleisten empfehlen wir dringend, regelmäßig und aktiv an den Übungsstunden teilzunehmen. Beachten Sie hierzu auch die "Spielregeln" -- und
- Erreichen von mindestens 40 Prozent der Punkte eines gesonderten Präsenzübungsblattes, welches in der Mitte des Semesters bearbeitet wird.
Literatur
| [1] | John E. Hopcroft und Jeffrey D. Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheotrie. Addison-Wesley, 1993. |
|---|---|
| [2] | Javier Esparza und Michael Blondin: Automata Theory: An Algorithmic Approach. MIT Press, 2023. |
| [3] | Dominique Perrin und Jean-Éric Pin: Infinite Words: Automata, Semigroups, Logic and Games. Academic Press, 2004. |
| [4] | Martin Hofmann und Martin Lange: Automatentheorie und Logik. Springer, 2011. |
| [5] | Hubert Comon et al.: Tree Automata Techniques and Applications. Online verfügbar: http://tata.gforge.inria.fr/ |
| [6] | Edmund M. Clarke, Orna Grumberg und Doron A. Peled: Model Checking. MIT Press, 2001. |
| [7] | Jean-Éric Pin: Mathematical Foundations of Automata Theory. Online verfügbar: https://www.irif.fr/~jep/PDF/MPRI/MPRI.pdf |
| [8] | Howard Straubing: Model Checking: Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser Boston, MA, 1994. |