University of Konstanz
Algorithmics
Prof. Dr. Ulrik Brandes

Seminar Simulationstheorie

+++ Aktuelles +++

Die Lehrveranstaltung ist beendet.

Die durch den Einsatz neuer Technologien entstandene Datenexplosion und Datenverfügbarkeit in Wissenschaft und Technik (vor allem in den Lebenswissenschaften und der Telekommunikation) und die daraus resultierende wachsende Bedeutung systemischer Aspekte in der Einzelforschung macht eine fundierte Theorie komplexer Systeme erforderlich.

Aus informatischer Sicht behandelt die Theorie komplexer Systeme zwei Schwerpunktbereiche: die Modellierung komplexer Systeme und die Simulation komplexer Systeme. Während die Modellierung auf die Bereitstellung geeigneter formaler Methoden zur effizienten Systembeschreibung abzielt, steht bei der Simulation die (experimentelle) Realisierung und Analyse dynamischer Abläufe von konkreten, formal beschriebenen Systemen auf Computern im Mittelpunkt. Die Simulationstheorie beschäftigt sich mit der effizienten Gestaltung von (Computer)Simulationen. Zwei typische Fragestellungen dabei sind:

  • Wie sehen optimale Simulationspläne aus und wie lassen sie sich berechnen?
  • Wann gibt es "Simulationsabkürzungen", d.h., welche analytischen Problemstellungen lassen sich mittels geeigneter Algorithmen schneller lösen als durch Ausführung der Simulation?
Das Seminar zielt darauf ab, ausgehend vom Konzept der sequenziellen dynamischen Systeme und verwandter Modelle in die für die oben genannten simulationstheoretischen Fragestellungen notwendigen mathematischen und algorithmischen Methoden einzuführen. Fallstudien aus Anwendungsbereichen unterstreichen die Relevanz der Ansätze, Fragestellungen und Methoden.

Termine

Seminar (Sven Kosub) Vorbesprechung am Dienstag, 15.04.08, um 14:15 Uhr – im Raum C 421
Blockseminar am Freitag, 06.06.08, um 14:00 Uhr – im Raum D 210

Organisation

Die Themenvergabe erfolgte in der Vorbesprechung am 15.04.08. (Die Folien zur Vorbesprechung sind hier.)

Die Endfassung der Seminarbeit ist spätestens am 17.07.2008 als Postscript- oder PDF-Datei abzugeben. Der Umfang der Seminararbeit beträgt 8 (+/- 1) Seiten (ohne Literaturverzeichnis) im LNCS-Style (Springer-Verlag) unter LaTeX:

Bei Fragen zu LaTeX sei einerseits auf den folgenden Link hingewiesen, ferner kann auch der Betreuer um Hilfestellungen bzw. Literaturangaben gebeten werden:

Vorträge

Theorie
Jakob Mall

Donnerstag, 12.06.08, 9:00-9:45, M 631

Äquivalenz und Simulation sequenzieller dynamischer Systeme
  • H. S. Mortveit, C. M. Reidys: An Introduction to Sequential Dynamical Systems, Kapitel 4.3. Springer-Verlag, New York, NY, 2007.
  • R. Laubenbacher, B. Pareigis: Update Schedules for Sequential Dynamical Systems. Discrete Applied Mathematics, 154(6):980-994, 2006.
  • S. Kosub: Computational Analysis of Complex Systems: Discrete Foundations, Algorithms, and the Internet, Kapitel 3.5. Habilitationsschrift, Fakultät für Informatik, Technische Universität München, 2007.
Algorithmik
Stefan Wolf

14:00-14:45

Fixpunktanalyse
  • C. M. Barrett, H. B. Hunt III, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz, R. E. Stearns, P. Tosic: Gardens of Eden and Fixed Points in Sequential Dynamical Systems. In: Proceedings of the 1st International Conference on Discrete Models: Combinatorics, Computation and Geometry (DM-CCG'01), Band AA der Discrete Mathematics and Theoretical Computer Science Proceedings, S. 241-259, 2001.
  • S. Kosub: Dichotomy Results for Fixed-Point Existence Problems in Boolean Dynamical Systems, Mathematics in Computer Science, 1(3):487-505, 2008.
  • S. Kosub, C. M. Homan: Dichotomy Results for Fixed Point Counting in Boolean Dynamical Systems. In: Proceedings of the 3rd Italian Conference on Theoretical Computer Science, S. 163-174. World Scientific Publishing, Singapore, 2007.
Fallstudien
Alexander Artiga Gonzalez

15:00-15:45

"Game of Life"
  • M. Garzon: Models of Massive Parallelism - Analysis of Cellular Automata and Neural Networks, Kapitel 4. Springer-Verlag, Berlin, 1995.
  • E. R. Berlekamp, J. H. Conway, R. K. Guy: What is Life? In: Winning Ways for Your Mathematical Plays, Band 2, Kapitel 25. Academic Press, London, 1982.
  • D. Eppstein: Searching for Spaceships. In: More Games of No Chance, MSRI Publication 42, S. 433-453, 2002.

Ressourcen (nur lokaler Zugriff)