Automatentheorie und ihre Anwendungen (Wintersemester 2017/18)

Vortragender: Prof. Dr. Thomas Schneider

K4, Master-Ergänzung, „Spezielle Themen der Theoretischen Informatik“

Neue Räume und Zeiten:
Di. 12–14 FVG Ost 0150  (Quadrat B3 im Campus-Lageplan, Eingang Ecke Leobener/Celsiusstr.)
Do. 8–10 MZH 8090


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:

Wissen aus der Veranstaltung „Theoretische Informatik 1“ ist hilfreich; die relevanten Aspekte werden jedoch am Anfang kurz wiederholt.


Material

Folien

Einführung   4 pro Seite  
Teil 1: endliche Wörter   4 pro Seite  
Teil 2   4 pro Seite  
Teil 3   4 pro Seite  
Teil 4   4 pro Seite   (bis einschließlich 18. 1.)

Weiteres Material

kommentiertes Beispiel zur Safra-Konstruktion, T3.16

Fragebögen aus der Vorlesung

Fragebogen 1    (23. 10.)
Fragebogen 2    (25. 10.)
Fragebogen 3    (14. 11.)

Übungsblätter

Abgabetermin (Stud.IP) Besprechung, Übungstermin
1 Übungsblatt 1 So. 29. 10. Di. 7. 11.
2 Übungsblatt 2 Fr.(!) 17. 11. Di. 21. 11.
3 Übungsblatt 3 Fr. 1. 12. Di. 5. 12.
4 Übungsblatt 4 Fr. 15. 12. Di. 19. 12.
5 Übungsblatt 5 Fr. 12. 1. Di. 16. 1.
6 Übungsblatt 6 Fr. 26. 1. Di. 30. 1.

Literatur ist am Ende jedes Foliensatzes angegeben. Für weiteres Material siehe Stud.IP.)

Prüfungen

Die Prüfungsmodalitäten werden in der Vorlesung bekanntgegeben.
AG Theorie der künstlichen Intelligenz 17. Jan. 2018  Thomas Schneider
Valid HTML 4.0 Transitional