Aufbaumodul Formale Systeme, Automaten und Prozesse
Credits | Workload | Kontaktzeit | Selbststudium | Dauer | Semester-Zeitraum | |||||
---|---|---|---|---|---|---|---|---|---|---|
6 CP | 180 h | 5 SWS (75 h) | 105 h | 1 | 2 | 3 | 4 | 5 | 6 |
Teilnahmevoraussetzungen
Die erfolgreiche Teilnahme an den regelmäßigen Übungen in Form von semesterbegleitenden Hausaufgaben ist Voraussetzung für die Zulassung zur Prüfung.
Lehrveranstaltungen
Veranstaltung/ Lehrform | CP | SWS | Semester | Häufigkeit | |
---|---|---|---|---|---|
Vorlesung Formale Systeme, Automaten, Prozesse | 6 CP | 3 SWS | 4. Sem. | SoSe, jährlich | |
Übung Formale Systeme, Automaten, Prozesse | 2 SWS | 4. Sem. | SoSe, jährlich |
Prüfungsleistung
- Lösung von Übungsaufgaben
- Klausur oder mündliche Prüfung
Note
Die Modulnote ist die Note der Klausur bzw. der mündlichen Prüfung.
Lernergebnisse / Kompetenzen
Das Ziel dieses Moduls besteht darin, die Studierenden mit Darstellungs- und Modellierungstechniken der Informatik vertraut zu machen. Ziel ist der Erwerb der folgenden Kenntnisse und Fähigkeiten:
- Syntaxdefinitionen durch Regelsysteme und ihre Anwendung
- Automaten als Grundstruktur zustandsbasierter Systeme
- einfache Modelle der Nebenläufigkeit (synchronisierte Produkte, Petrinetze)
- Kenntnis der fundamentalen Algorithmen dazu (Transformation und Analyseverfahren für Automaten und Regelsysteme)
Inhalte
- Formale Systeme:
Terme, Wörter, Sprachen anhand von Kernbeispielen: u.a. Zahlterme, arithmetische und boolesche Terme, while-Programme. Definition von Termmengen und Programmiersprachen durch Regelsysteme (Termersetzungssysteme, Grammatiken), Ableitungsbegriff, Methode der strukturellen Induktion. Klassifikation von Grammatiken (Chomsky-Hierarchie) und elementare Sachverhalte zu kontextfreien Grammatiken: Normalformen, Wortproblem (Ableitbarkeitstest), Nichtleerheitstest.
- Automaten:
Endliche Automaten (deterministisch, nichtdeterministisch), Abschlusseigenschaften (u.a. Produktautomaten), reguläre Ausdrücke, Nichtleerheits- und Äquivalenztest, Nachweis nichtregulärer Sprachen. Kellerautomaten (deterministisch und nichtdeterministisch), Übersetzung von kontextfreien Grammatiken in Kellerautomaten als Beispiel der Implementierung von Rekursion durch Kellerspeicher.
- Prozesse:
Elementare Modellierungsformen verteilter und nebenläufiger Systeme: Synchronisierte Produkte, Petrinetze und kommunizierende sequentielle Prozesse (CSP). Vorstellung und Einübung anhand von Beispielen, Vergleich mit dem Grundmodell des endlichen Automaten.
Modulzuordnung
Bachelor of Science: Fach Grundlagen der Informatik
Disclaimer
Bitte beachten Sie, dass im Zweifel (z.B. sich widersprechende Angaben auf der Website und dem Modulhandbuch) für Ihr Studium immer die Angaben in der aktuellen Bachelorprüfungsordnung mit den entsprechenden Anhängen verbindlich sind. Wenden Sie sich bitte an die Fachstudienberatung, wenn Ihnen Unstimmigkeiten auffallen.