Dr. P. Sadeghi
Inhalt
Vorlesung
- Alphabet, Wort, Sprache, Grammatik
- Regulärer Ausdruck, reguläre Sprache
- Nichtdeterministischer endlicher Automat
- Kontextfreie Sprachen und Stack-Automaten
- Recursive-Descent-Parser und -Übersetzer
- Turing-Maschine, Berechenbarkeit
- Komplexitätstheorie
Übungen / Labor
In der ersten Semesterhälfte werden wöchentlich Übungsaufgaben gestellt, die korrigiert werden und in gemeinsamen Übungsstunden besprochen werden.
In der zweiten Semesterhälfte wird in Laborübungen ein Recursive-Descent-Übersetzer für arithmetische Ausdrücke gebaut.
Die Programmiersprache ist Java oder Python.
Organisation
5. Semester, Vorlesung / Übung 4-std.
Sprache: deutsch
Präsenzstudium: 60 h, Eigenstudium: 90 h
Gesamtaufwand: 150 h
Leistungspunkte (credit points): 5
Medienformen: Tafel, Projektor
Vorbedingungen: Orientierungsprüfung
Prüfung: PL (Mündliche Prüfung)
Lernvoraussetzungen
Sie sind mit den grundlegenden mathematischen Konzepten Menge, Relation, Abbildung, Folge, Graph vertraut und können damit umgehen. Sie können objektorientiert programmieren.
Lernziele
Sie kennen die wichtigsten theoretischen Konzepte aus dem Bereich der Formalen Sprachen und Automaten sowie der Komplexitätstheorie; Sie können auf Basis einer Grammatik einen Parser und Übersetzer bauen.
Literatur
A. Asteroth, C. Baier: Theoretische Informatik. Pearson Studium (2002)
R.H. Güting, M. Erwig: Übersetzerbau. Springer (1999)
J. Hromkovic: Theoretische Informatik. 2. Auflage, Teubner (2004)
U. Schöning: Theoretische Informatik kurz gefasst. BI-Wissenschaftsverlag (1992)
M. Sipser: Introduction to the Theory of Computation. PWS Publishing Company (1996)
