Formale Systeme, Automaten, Prozesse (SS2020)

Bitte beachten Sie, dass sich die Uhrzeiten der Klausuren durch die hochschulweite Neuplanung der Prüfungsveranstaltungen geändert haben.

Vorlesungsvideos

Die Vorlesung ist inhaltlich fast gleich zu der Vorlesung von 2017. Die Video AG der Fachschaft MPI hat diese netterweise aufgezeichnet, sie können diese hier finden.
Sofern sie im RWTH-Netz verbunden sind (z.B. über VPN) können Sie hier die Aufzeichnungen der Globalübung und Vorlesung einsehen. Es wird keine regelmäßige Vorlesung in Zoom geben. Allerdings wird es unregelmäßig Fragestunden bzw. Ergänzungen auf Zoom gestreamt. Diese werden rechtzeitig in Moodle und auf der Website angekündigt.

Bitte arbeiten Sie folgende Vorlesungen in der jeweiligen Kalenderwoche durch:
KWVideos
15 (6.-10. April)1 & 2
16 (13.-17. April)3 & 4
17 (20.-24. April)5 & 6
18 (27. April-1. Mai)7 & 8
19 (04. Mai-08. Mai)9 & 10
20 (11. Mai-15. Mai)11 & 12
21 (18. Mai-22. Mai)13 & 14
22 (25. Mai-29. Mai)15
24 (1. Juni-5. Juni)Nichts
25 (8. Juni-12. Juni)16 & 17
26 (15. Juni-19. Juni)18
27 (22. Juni-26. Juni)19 & 20

Anmeldung

Sie müssen sich nur für das Tutorium in RWTH Online anmelden. Dann werden Sie mit etwas Verzögerung auch dem Moodle-Raum hinzugefügt. Dabei können Sie Ihre Präferenzen und AbgabepartnerInnen (falls bereits vorhanden) durch Nennung eines gemeinsamen Gruppennamens angeben. Studierende, die im Master FoSAP als Auflage hören müssen, müssen sich per Mail mit Präferenzen (und Gruppenname falls vorhanden) sowie Matrikelnummer melden. Wir fügen Sie dann manuell hinzu.

Erste Termine

  • Globalübung: Di, 14.4. 14:30 statt Tutorium
  • Tutorium: 20.4. bzw 21.4.
  • Minitest: Während der ersten Globalübung (sonst in Tutorien)
  • Blatt Veröffentlichung: 13.4. Abgabe: 20.4. jeweils 8 Uhr
    • Wegen Ostern gibt es keine Tutorien in der Osterwoche. Stattdessen wird in der Globalübung ein großer Ersatztutorium gehalten.

Zulassungsvoraussetzungen für die Klausur

  • 50% der Punkte in den Hausaufgaben.
  • 50% der Punkte in den Präsenzübungen die in den Tutorien stattfinden.

Sollten Sie die Vorlesung in einem Studiengang belegen, welcher nicht Informatik ist, können diese Zulassungsbedingungen für Sie möglicherweise entfallen. Überprüfen Sie dazu bitte Ihre fachspezifische Prüfungsordnung und informieren Sie sich im Zweifelsfall bei dem/der für Sie zuständigen Fachstudienberater*in.

Hausaufgaben

Jeden Montag um 8 Uhr werden Hausaufgaben im Moodle und auf der Website veröffentlicht. Diese sollen zu dritt bearbeitet und in Moodle als eine PDF hochgeladen werden. Dazu muss man als Abgabegruppe aus genau drei Mitgliedern in Moodle registriert sein. Alle Mitglieder der Abgabegruppe müssen im selben Tutorium sein. Abgabefrist ist jeweils eine Woche später montags um 8 Uhr.

Präsenzübung

Am Ende jedes Tutorium gibt es einen Minitest. Dieser besteht aus einer Verständnisaufgabe, die in ca. 15 Minuten Zeit gelöst werden soll. Sie erhalten zusätzlich 15 Minuten um ihre Lösung per E-Mail an ihre/n Tutor*In zu schicken. Sie können die Aufgabe gern handschriftlich lösen und abfotografiert versenden. Achten Sie bitte auf Lesbarkeit. Im Gegensatz zur Hausaufgabe sollen die Präsenzübungen alleine bearbeitet werden.

Findung von AbgabepartnerInnen

Wenn Sie zum Zeitpunkt der Anmeldung noch keine AbgabepartnerInnen habt, ist das nicht weiter schlimm. Das Blatt sollen Sie allerdings zu dritt abgeben. Dafür stellen wir im Moodle ein Forum bereit, wo Sie nach AbgabepartnerInnen suchen können. Bitte nennen Sie immer auch Ihre Tutoriennummer, da alle Abgapartner*Innen im selben Tutorium sein müssen.

Organisatorisches

Inhalt

  • 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.

Folien

Die Folien zur Vorlesung sind zeitnah nach Durchführung auf dieser Website zu finden. Original sind die Folien genau wie in der Vorlesung und Tintenfreund ist eine Variante, die zum Ausdrucken besser geeignet ist. Es gibt jedoch kleine Unterschiede zu den Folien auf den Videos von 2017, da zum Beispiel einige Fehler korrigiert wurden.

Übungsblätter

Klausuren