Formale Systeme, Automaten, Prozesse (SS2009)

Peter Rossmanith

Sprechstunde: Mittwoch 11-12 Uhr

Betreuung der Übungen und Organisation:

• Fabian Emmes emmes@cs.rwth-aachen.de
• Joachim Kneis kneis@cs.rwth-aachen.de
• Alexander Langer langer@cs.rwth-aachen.de

Wiederholungsklausur

Die Wiederholungsklausur fand am Mittwoch, den 7.10., von 16 Uhr bis 18 Uhr im Hörsaal Audimax (1420|210) statt.

Die Klausureinsicht findet am Donnerstag, den 22.10., von 9 Uhr bis 11 Uhr in Raum 6103 (E2, 1. Etage, Hörn) statt.

Vorläufige Ergebnisse (nur aus dem RWTH-Netz abrufbar; Notenspiegel wie unten)

Klausur

Die Klausur fand am Dienstag, den 18.8., von 14 Uhr bis 16 Uhr in den Hörsälen Audimax (1420|210) und Roter Hörsaal (Ro, 1420|002) statt.

Vorläufige Ergebnisse (nur aus dem RWTH-Netz abrufbar)

Klausur (PDF) Lösungsvorschlag (PDF)

Notenspiegel:

40,1.0
39,1.0
38,1.0
37,1.3
36,1.3
35,1.7
34,1.7
33,2.0
32,2.0
31,2.3
30,2.3
29,2.7
28,2.7
27,3.0
26,3.0
25,3.3
24,3.3
23,3.7
22,3.7
21,4.0
20,4.0

Weniger als 20 Punkte: Leider nicht bestanden.

Klausureinsicht

Die Klausureinsicht findet am Freitag, den 28.8., bei uns am Lehrgebiet (Raum 6103, E2, 1. Etage, Hörn) statt.

Uhrzeit	UID
9 Uhr - 10 Uhr	100000 - 249999
10 Uhr - 11 Uhr	250000 - 399999
11 Uhr - 12 Uhr	400000 - 549999
14 Uhr - 15 Uhr	550000 - 699999
15 Uhr - 16 Uhr	700000 - 849999
16 Uhr - 17 Uhr	850000 - 999999

Klausurzulassung

Studierende in den Studiengängen B.Sc. Informatik, B.Sc. Mathematik und Lehramt Informatik benötigen eine Zulassung zur Klausur. Die hierfüur nötigen Kriterien erfüllen Sie, wenn Sie mindestens 118 Punkte in den Hausaufgaben und 50 Punkte in den wöchentlichen Präsenzübungen erreicht haben. Aus datenschutzrechtlichen Gründen dürfen wir leider keine Liste der zugelassenen Matrikelnummern online stellen. Bitte überprüfen Sie daher auf der Webseite der Übungen, ob Sie die nötige Punktzahl erreicht haben. Bitte beachten Sie außerdem, daß die Zulassung zur Klausur unabhängig von der Anmeldung zur Klausur über das ZPA bzw. Campus-System ist.

Studierende der Fächer Informatik (Diplom) und Technische Kommunikation benötigen keine Zulassung.

Neu: Weitere Materialien

Folien

Weitere interessante Informationen:

• The Algorithmic Beauty of Plants
• Branch Prediction
• Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)
• List of hard PCP instances

Zeit und Ort

Vorlesung:
Dienstags, 08:15 - 09:00 Uhr, Grüner Hörsaal (im Audimaxgebäude)
Donnerstags, 10:00 - 11:30 Uhr, Roter Hörsaal (im Audimaxgebäude)

Vorlesungsbeginn: Donnerstag, 16.04.2009

Zusätzliche Angebote

Fragestunde:
Dienstags, 09:00 - 09:45 Uhr, Grüner Hörsaal (im Anschluß an die Vorlesung)

Globalübung:
Freitags, 11:45 - 13:15 Uhr, Fo 1 (im Kármán-Auditorium), ab dem 24. April

Organisatorisches

Die Veranstaltung ist teilweise anmeldepflichtig: Studierende im Bachelorstudiengang der Informatik müssen sich bis zum 31.05.2009, 23:00 Uhr online über das Campussystem zu der Vorlesung anmelden. Studierende anderer Fachrichtungen müssen unter Umständen ihr eigenes Anmeldeverfahren durchführen. Bitte konsultieren Sie Ihre Studienordnung.

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.

Vorwissen

Elementare mathematische Begriffe (aus dem 1. Semester)

Credit Points

6 ECTS

Literatur

TBA