Kurs: Automatentheorie und ihre Anwendungen (Wintersemester 2020/21)
Vortragender: Dr. Leif Sabellek
K4, Master-Ergänzung, „Spezielle Themen der Theoretischen Informatik“
Ablauf
Die Veranstaltung findet online statt. Jede Woche gibt es die Vorlesung in Form von mehreren kurzen Videos, die ihr alleine (asynchron) durcharbeitet. Zusätzlich treffen wir uns einmal pro Woche per BigBlueButton im Stud.IP, um Fragen zu beantworten und Übungsaufgaben zu besprechen.
Das wöchentliche Treffen findet statt immer montags 16-18 Uhr per BigBlueButton in Stud.IP (in der Veranstaltung unter dem Reiter "Meetings"). Link zur Veranstaltung
Das erste Treffen ist am Montag den 2.11., 16-18 Uhr.
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.
Kurzübersicht der Themen:
-
Wiederholung von endlichen Automaten und formalen Sprachen
-
Automaten auf endlichen Bäumen
-
Automaten auf unendlichen Wörtern
(insbesondere Determinisierung)
-
Automaten auf unendlichen Bäumen
(insbesondere Komplementierung)
-
Anwendungen: Textsuche, XML-Schemasprachen, Verifikation und Temporallogik (LTL, CTL)
Wissen aus der Veranstaltung „Theoretische Informatik 1“ ist hilfreich;
die relevanten Aspekte werden jedoch am Anfang kurz wiederholt.
Vorlesungsmaterialien
Folien, Literaturhinweise, Übungsaufgaben und weiteres Material sind über Stud.IP zugänglich. Link zur Veranstaltung
Prüfungen
Die Prüfungsmodalitäten werden in der Vorlesung bekanntgegeben.
AG Theorie der künstlichen Intelligenz
9. Okt. 2020
Leif Sabellek