Simulationstheorie

Die Lehrveranstaltung ist beendet.

Seminar (2 SWS/4 ECTS)

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

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

  • LNCS-Style (die Datei llncs.cls) des Springer-Verlages
  • Rahmenvorlage seminararbeit.tex (Seitengröße und der Font bitte nicht verändern)
  • Beispieldatei example.tex (das Bild example.eps wird eingebunden)
  • Die Ausarbeitung soll auf die verwendete Literatur verweisen, diese Literatur ist mit BibTeX zu verwalten und in einer eigenen Datei zu speichern (hier die zum Beispiel gehörende Datei: example.bib)

Vorträge

Theorie
Zeit:Donnerstag, 12.06.08, 9:00-9:45, M 631
Vortragende(r):Jakob Mall
Thema:Äquivalenz und Simulation sequenzieller dynamischer Systeme
Referenzen:
  • 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
Zeit:Freitag, 06.06.08, 14:00-14:45, D 210
Vortragende(r):Stefan Wolf 
Thema:Fixpunktanalyse
Referenzen:
  • 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
Zeit:Freitag, 06.06.08, 15:00-15:45, D 210
Vortragende(r):Alexander Artiga Gonzalez
Thema:"Game of Life"
Referenzen:
  • 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.

Allgemeine Literatur (nur lokaler Zugriff)

Henning S. Mortveit, Christian M. Reidys: An Introduction to Sequential Dynamical Systems. Springer-Verlag, New York, NY, 2007.