Models of Computation WS26/27

Models of Computation WS26/27

News

16. Oktober - Der Veranstaltungsbeginn wurde ergänzt.

20. August - Die Informationen auf dieser Webseite sind noch vorläufig.

Organisation

Die Vorlesung wird gehalten von Prof. Dr. Roland Meyer. Der Übungsbetrieb wird von Natalia Gacek geleitet.

  • Zielgruppe der Vorlesung sind Studierende der Informatik im Bachelor.
  • Vorlesungstermin: Montag, 16:45 - 18:15 in IZ 358
  • Übungstermin: Dienstag, 13:15 - 14:45 in IZ 358
  • Die Veranstaltung beginnt am 26.10.2026.

Modul

Es handelt sich um eine Veranstaltung mit 4 (2 VL + 2 Ü) Semesterwochenstunden.
Um das Modul erfolgreich mit 5 ECTS abzuschließen, sind zwei Leistungen zu erbringen:

  • Studienleistung: Sie erreichen mindestens 50% der Punkte in den Übungsaufgaben.
  • Prüfungsleistung: Sie bestehen eine (voraussichtlich) mündliche Prüfung in der vorlesungsfreien Zeit.

Übungsblätter

Die Übungsblätter werden (in der Regel) wöchtenlich veröffentlicht.
Sie dürfen diese allein oder zu zweit bearbeiten.
Die Abgabe erfolgt per Mail, im Abgabekasten vor IZ 342/343 oder persönlich vor Beginn der Übung zur angegebenen Deadline.

Materialien

Die Vorlesung basiert vorwiegend auf handschriftlichen Notizen. Es gibt ein Skript, das für den ersten Teil der Vorlesung relevant ist.

Inhalte

Es werden operationelle Modelle zur Beschreibung des Verhaltens von Programmen betrachtet.
Für diese Modelle werden Berechnungsprobleme formuliert und Algorithmen zu deren Lösung vorgestellt.
Die Modelle umfassen

  • omega-Automaten,
  • Pushdown-Automaten,
  • Vektoradditionssysteme,
  • Games,
  • Timed-Automata und
  • Markov-Ketten.

Die Vorlesung gibt einen Einblick in die theoretischeren Forschungsarbeiten des Instituts und die entsprechenden Kurse des Masterstudiums.

Literatur

Die Liste der Literatur, auf der die Vorlesung aufbaut, wird im Laufe des Semesters vervollständigt.

  • L. Priese and H. Wimmel. Petri-Netze. Springer-Verlag, 2003.
  • W. Reisig. Petri nets: An Introduction. Monographs in Theoretical Computer Science. An EATCS Series. Springer-Verlag, 1985.
  • P. H. Starke. Analyse von Petri-Netz-Modellen. Leitfäden und Monographien der Informatik. Teubner, 1990.
  • J. Esparza and M. Nielsen. Decibility issues for Petri nets-a survey. Journal of Information Processing and Cybernetics EIK, 30(3):143-160, 1994.
  • J. Esparza. Decidability and complexity of Petri net problems - an introduction. In Lectures on Petri Nets I: Basic Models. Advances in Petri Nets, volume 1491 of LNCS, pages 374-428, Springer-Verlag, 1998.
  • J. Esparza. Automata theory - an algorithmic approach. Vorlesungsaufzeichnungen zu einer Veranstaltung für Automatentheorie. Online verfügbar. 2012.
  • W. Thomas. Languages, Automata, and Logic. In Handbook of Formal Languages, volume 3, pages 389-455, Springer-Verlag, 1996.
  • M. Hofmann and M. Lange. Automatentheorie und Logik. Springer-Verlag, 2011.
  • C. Baier, J. Katoen: Principles of Model Checking. The MIT Press, 2008 (Kapitel 9 & 10)
  • A. Bouajjani, J. Esparza, O. Maler. Reachability analysis of pushdown automata: application to model checking. In Proc. of the 8th International Conference on Concurrency Theory, CONCUR, volume 1243 of LNCS, pages 135-150, Springer-Verlag, 1997.
Letzte Aktualisierung: 27.10.2026