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 | |
Lehrveranstaltungen
| Veranstaltung/ Lehrform | CP | SWS | Semester | Häufigkeit | |
|---|---|---|---|---|---|
| Vorlesung: Formale Systeme, Automaten und Prozesse | 6 CP | 3 SWS | 4. Sem. | SoSe, jährlich | |
| Übung: Formale Systeme, Automaten und Prozesse | 2 SWS | 4. Sem. | SoSe, jährlich | ||
Prüfungsleistung
Aktive Übungsteilnahme, Lösung von Übungsaufgaben: Die erfolgreiche Teilnahme an den regelmäßigen Übungen ist Voraussetzung für die Zulassung zur Prüfung. 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 Analyse verfahren für Automaten und Regelsysteme)
Inhalte
Inhalte der Veranstaltungen sind z.B.:
- Formale Systeme: Terme, Wörter, Sprachen anhand von Kernbeispielen
- Definition von Termmengen und Programmiersprachen durch Regelsysteme (Termersetzungssysteme, Grammatiken), Ableitungsbegriff
- Methode der strukturellen Induktion für die Definition von Funktionen und für Beweise, Illustration anhand der while-Programme
- Klassifikation von Grammatiken (Chomsky-Hierarchie) und elementare Sachverhalte zu kontextfreien Grammatiken: Normalformen, Wortproblem, Nichtleerheitstest
- Automaten: Endliche Automaten, Abschlusseigenschaften, reguläre Ausdrücke
- Nichtleerheits- und Äquivalenztest, Nachweis nichtregulärer Sprachen
- Kellerautomaten (deterministisch und nichtdeterministisch)
- Übersetzung von kontextfreien Grammatiken in Kellerautomaten
- Ausblick auf deterministisches Parsing (Compilerbau)
- Prozesse: Synchronisierte Produkte, Illustration anhand Darstellung von Protokollen
- Erweiterung durch Message-Passing: Coummunicating Sequential Processes
- Erweiterung durch unbeschränkte Zähler: Petrinetze
- Simulation, Bisimulation, Quotientenbildung: Minimierungsverfahren für Transitionssysteme
Sonstige Informationen
Pflichtmodul. Empfehlung: Elementare mathematische Begriffe aus Modulen des 1. Semesters sollten vorhanden sein.
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.
