Automatentheorie und ihre Anwendungen
-
Vortragender
-
Dr. Thomas Schneider
-
Art der Veranstaltung
-
K4, Master-Ergänzung, Wahlbereich: Spezielle Themen der Logik
-
Zeit und Ort
-
Mo 12–14, SFG 0150 (ab 15. 4.)
Mi 8–10, GW1 A0150
Fr 12–14, MZH 1470 (bis einschl. 12. 4.)
Erste Sitzung: Mi 3. 4., 8:30 Uhr, GW1 A0150
Lageplan Uni Bremen
Kurzbeschreibung
Automatentheoretische Techniken haben nützliche Anwendungen in der Informatik:
mit ihnen kann man beispielsweise sicherheitsrelevante Eigenschaften eines Systems überprüfen (Verifikation),
robuste XML-Sprachen definieren oder Anfragen auf XML-Bäumen auswerten.
Dazu muss man den Standard-Begriff von endlichen Automaten auf Wörtern verallgemeinern,
indem man von endlichen Wörtern zu unendlichen Wörtern oder Bäumen übergeht.
Diese Erweiterung des Automatenbegriffs sowie die damit verbundenen theoretischen Resultate und praktischen Anwendungen
sind Gegenstand dieses Kurses.
Vorläufige Themenliste:
-
Motivation und
Kurzwiederholung von endlichen Automaten und formalen Sprachen
-
Automaten auf unendlichen Wörtern; Verifikation und Verifikationslogiken
-
Automaten auf endlichen Bäumen; baumförmige Datenstrukturen und XML
-
Automaten auf unendlichen Bäumen; Verifikation und Verifikationslogiken
Wissen aus der Veranstaltung "Theoretische Informatik 1" ist hilfreich,
wird aber nicht vorausgesetzt – wir werden die wichtigsten Aspekte am Anfang kurz wiederholen.
Material
Folien
Einführung
Teil 1
4 pro Seite (Version vom 12. 4., 16:30 Uhr)
Teil 2
4 pro Seite (Version vom 15. 5., 11:15 Uhr)
Teil 3
4 pro Seite (Version vom 26. 6., 11:10 Uhr)
Teil 4
4 pro Seite (Version vom 1. 7., 15:10 Uhr)
Übungsblätter
Übungsblatt 1 (Abgabe am 10. 4.)
Übungsblatt 2 (Abgabe am 24. 4.)
Übungsblatt 3 (Abgabe am 13. 5.)
Übungsblatt 4 (Abgabe am 29. 5.)
Übungsblatt 5 (Abgabe am 12. 6.)
Übungsblatt 6 (Abgabe am 26. 6., Korrektur in Aufgaben 2 + 3, jeweils Punkt (4))
AG Theorie der künstlichen Intelligenz
1. 7. 2013
Thomas Schneider
