Vortragender: Prof. Dr. Thomas Schneider
K4, Master-Ergänzung, „Spezielle Themen der Theoretischen Informatik“
Di. 16–18 GW1 A0160
Mi. 8–10 MZH 6340
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.
| Einführung | 4 pro Seite | |||
| Teil 1: endliche Wörter | 4 pro Seite | |||
| Teil 2: endliche Bäume | 4 pro Seite | |||
| Teil 3: unendliche Wörter | 4 pro Seite | (Änderung am 31. 1.: Korrektur des Algorithmus auf Folie 84) | ||
| Teil 4: unendliche Bäume | 4 pro Seite | (Änderung am 23. & 29. 1.: zusätzliche Erklärungen auf Folie 58, Korrektur URL auf Titelfolie) | ||
| Teil 5: Alternierung | 4 pro Seite | (Änderung am 30. 1.: Korrekturen auf Folien 9, 15) |
Es wird empfohlen, die Beispiele und Beweise an der Tafel mitzuschreiben. Zum Abgleich der Mitschriften steht auf Github ein (unvollständiges) PDF-Dokument zur Verfügung.
Die Quellen der Folien sind jetzt ebenfalls auf GitHub verfügbar.