Seminar: Analyse von Petrinetz-Modellen
Petrinetze werden zur Modellierung verteilter Systeme verwendet. Zustandsänderungen in einem Petrinetz-Modell werden verstanden als Erzeugen und Vernichten von Ressourcen (statt des sonst üblichen Lesens und Schreibens von Variablen). Dadurch ergeben sich interessante algorithmische Analysemöglichkeiten, die in diesem Seminar vorgestellt werden.
Aktuelles
- Kleinere Änderungen am Zeitplan.
- Am Mittwoch, den 19.11.09 findet das Seminar auf Grund der Konferenz der Informatikfachschaften im Raum RUD 25, 4.410 statt (Haus IV, 4. OG)
- Einführungsfolien und Themaverteilung online.
- Kleine Anpassung an den Anforderungen (Abstract, Ein-Seiten-Handout).
- Vorläufige Terminplanung sowie Themen online.
Zum Seminar
| Zuordnung | Hauptstudium, Theoretische Informatik |
|---|---|
| Beginn | 15.10.2009 (Erste Semesterwoche!) |
| Zeit | Do. 13-15 Uhr s.t. |
| Ort | RUD 25, 3.113 |
| Dozent | Jan Sürmeli |
| Studienpunkte | 3 |
Vorträge/Gliederung
Jeder Seminarteilnehmer hält zwei Vorträge, die jeweils 30 Minuten dauern sollen: Der erste Vortrag dient dazu, in das Thema einzuführen und die grundlegenden Konzepte vorzustellen. Der Vortragende sollte außer Grundkenntnissen und den bis dorthin behandelten Inhalten im Seminar keine Vorkenntnisse voraussetzen. Im zweiten Vortrag erfolgt dann eine Vertiefung auf Basis des ersten Vortrages. Schriftlich anzufertigen sind: (1) ein kurzes, motivierendes Abstract, das vor dem ersten Vortrag per Goya-Mail an die anderen Seminarteilnehmer verschickt wird, sowie (2) ein Handout, das höchstens eine Din A4 Seite lang ist, die wichtigsten Punkte beider Vorträge enthält und nach dem zweiten Vortrag ausgeteilt wird.
In einer Seminarstunde werden wir in den meisten Fällen zwei Vorträge hören und jeweils anschließend eine 15-minütige Diskussion führen, die sich nicht nur mit dem Inhalt sondern vor allem auch mit der Vortragsweise sowie den verwendeten Hilfsmitteln beschäftigt. Zielsetzung des Seminars ist also nicht nur das Behandeln der Seminarthemen sondern auch die gezielte Verbesserung der Vortragsfähigkeiten des Einzelnen.
Themen/Literatur
Es folgt eine Auflistung der bisher geplanten Themen. Die Vergabe der Themen erfolgt in der ersten Seminarstunde (15.10.2009). Die Literaturangaben sind Vorschläge, zu dem einen oder anderen Thema findet sich sicher auch noch mehr Literatur. Der Vortrag eines Themas, das nicht in dieser Liste enthalten ist, ist prinzipiell nicht ausgeschlossen, muss aber vorher abgeklärt werden.
| Thema | Vortragender | Literatur |
|---|---|---|
| Einführung und Themenvergabe | Jan Sürmeli | Desel, Reisig: "Place/Transition Petri Nets" |
| "Spezielle Netzklassen" | Matthias Godau | Starke: "Analyse von Petri-Netz-Modellen", Kap. 14, und Desel, Esparza: "Free Choice Petri Nets", Kap. 3 und 4.1 |
| "Deadlocks und Fallen" | Nikolai Kosjar | Starke: "Analyse von Petri-Netz-Modellen", Kap. 14, und Desel, Esparza: "Free Choice Petri Nets", Kap. 4.2 und 4.3 |
| "Überdeckbarkeitsgraph" | Robert Scheffler | Starke: "Analyse von Petri-Netz-Modellen", Kap. 5, und Schmidt: "Model-Checking with Coverability Graphs" |
| "Invarianten" | Jeanine Umlang | Starke: "Analyse von Petri-Netz-Modellen", Kap. 11 |
| "Regionentheorie" | Stefan Koch | Desel, Reisig: "The Synthesis Problem of Petri Nets." und Cortadella et al: "Deriving Petri Nets from Finite Transition Systems" |
| "Partial Order Reduction" | Jörg Bachmann | Antti Valmari: "The State Explosion Problem", Kap. 7.4 |
| "Unfoldings" | Benjamin Gehrels | McMillan: "Symbolic Model Checking", Kap. 6, und Esparza et al: "Model Checking Using Net Unfoldings" |
| "Beweisgraphen" | Zheng Wang | Reisig: "Elements of distributed Algorithms", Kap. VIII |
|
|
|
|
| "Zeitpetrinetze" | Mathias Mosolf | Starke: "A Memo on Time Constraints in Petri Nets" |
|
|
|
|
| "Workflow-Netze" | Alexander Boll | W.M.P. van der Aalst: "Verification of Workflow Nets" |
| "High-Level Invarianten" | Karl-Heinz Preuß | Reisig: "Petri Nets and Algebraic Specifications." und Smith: "Principles of High-Level Net Theory." |
| "Offene Workflownetze" | Jens Killat |
Vorläufige Terminplanung
| Termin | Tag | Thema 1 | Thema 2 |
|---|---|---|---|
| 0. | 15.10.2009 | "Einführung und Themenvergabe" | |
| 1. | 22.10.2009 | "Spezielle Netzklassen" I | "Deadlocks und Fallen" I |
| 2. | 29.10.2009 | "Überdeckbarkeitsgraph" I | "Invarianten" I |
| 3. | 05.11.2009 | "Spezielle Netzklassen" II | "Deadlocks und Fallen" II |
| 4. | 12.11.2009 | "Überdeckbarkeitsgraph" II | "Invarianten" II |
| 5. | 19.11.2009 | "Regionentheorie" I | "Partial Order Reduction" I |
| 6. | 26.11.2009 | -- | "Beweisgraphen" I |
| 7. | 03.12.2009 | "Regionentheorie" II | "Partial Order Reduction" II |
| 8. | 10.12.2009 | "Unfoldings" I | "Beweisgraphen" II |
| 9. | 17.12.2010 | "High-Level Petrinetze" I | -- |
| 10. | 07.01.2010 | "Zeitpetrinetze" I | "Unfoldings" II |
| 11. | 14.01.2010 | -- | "Workflow-Netze" |
| 12. | 21.01.2010 | "High-Level Invarianten" I | |
| 13. | 28.01.2010 | "Zeitpetrinetze" II | "Offene Workflow-Netze" I |
| 14. | 04.02.2010 | "High-Level Invarianten" II | |
| 15. | 11.02.2010 | Offene Workflow-Netze" II | Abschließende Diskussion |
Theorie der Programmierung | Kontakt | zuletzt geändert am 15.03.2010 11:29