Studien- und Diplomarbeiten

Offene Themen

Bereich Verifikation

Verteilte Algorithmen

Problemstellung	Anwendungen und Organisation rechnergestützter Systeme sind zunehmend verteilt. Damit werden verteilte Algorithmen immer wichtiger. In dieser Arbeit modellieren Sie einen verteilten Algorithmus aus der Literatur mit Petrinetzen, Temporaler Logik, Abstract State Machines, Z oder einer anderen Spezifikationstechnik, beweisen seine wichtigsten Eigenschaften und vergleichen die gewählte Technik mit Alternativen.
Ziele	- Modellierung eines verteilten Algorithmus mit einer Spezifikationstechnik - Beweis von Eigenschaften - Vergleich der gewählten Technik mit Alternativen
Voraussetzungen	Teilnahme an mindestens einer der Vorlesungen Methoden und Modelle des Systementwurfs bzw. Verteilte Algorithmen
Beginn	sofort
Ansprechpartner	Prof. Dr. Wolfgang Reisig

Komposition von Petrinetzen

Problemstellung	Große Systemmodelle werden systematisch durch Komposition kleinerer Modelle kkonstruiert. Für Petrinetz-Modelle braucht man deshalb geeignete Kompositions-Operationen. In der Literatur werden zahlreiche solche Operationen vorgestellt. Sie sind oft intuitiv einfach, aber formal doch vergleichsweise aufwendig.
Ziele	Vor dem Hintergrund ganz neuer Vorschläge werden in dieser Diplomarbeit bekannte Konstruktionen neu bewertet, neu formuliert und aufeinander bezogen. Neue Varianten werden systematisch hergeleitet und untersucht.
Voraussetzungen	Grundkenntnisse zu Petrinetzen, wie sie in den Vorlesungen "Methoden und Modelle des Systementwurfs" und "Verteilte Algorithmen" vermittelt werden. Dieses Thema erfordert Interesse an guten, einfach verständlichen und dennoch präzisen formalen Darstellungen.
Beginn	sofort
Ansprechpartner	Prof. Dr. Wolfgang Reisig
Umfang/Rahmen	eine Diplomarbeit

Offene Netze und Bedienungsanleitungen

Stochastische Petrinetze in Toollandschaft integrieren

Problemstellung	Am Lehrstuhl existieren verschiedene Tools, welche auf einem Erreichbarkeitsgraphen eines Petrinetzes arbeiten. Dafür haben sich mittlerweile Datenformate etabliert. Außen vor gelassen wurden dabei bisher stochastische Annotationen an den Petrinetztransitionen. Es gibt bereits Werkzeuge, die für ein stochastisch annotiertes Petrinetz den Erreichbarkeitsgraphen bestimmen können, sodass für jeden Knoten die Wahrscheinlichkeit gegeben ist, in diesen zu gelangen. Hier fehlt jedoch die Anbindung an unsere Tools.
Ziele	Unsere Toollandschaft soll möglichst einfach und effizient auf stochastische Informationen zugreifen können. Dazu sollen - die existierenden Tools für die Analyse Stochastischer Petrinetze evaluiert werden, und ein geeignetes gewählt werden, - die Ausgabe des gewählten Tools unseren Tools zur Verfügung gestellt werden, sowie - die vorhandenen Datenformate angepasst werden.
Voraussetzungen	Sehr empfohlen sind stochastische Grundkenntnisse und Erfahrung in C++, wünschenswert sind Kenntnisse über Petrinetze.
Ansprechpartner	Christian Gierds
Umfang/Rahmen	eine Studienarbeit

Stochastische Bedienungsanleitungen

Problemstellung	Wenn bisher stochastische Petrinetze betrachtet wurden, dann im Zusammenhang mit geschlossenen Systemen, d.h. es fand keine Kommunikation mit der Umgebung oder genauer mit einem Partnernetz statt. Am Lehrstuhl betrachten wir jedoch kommunizierende Systeme in Form von offenen Netzen, also Petrinetzen die Kommunikationsplätze besitzen können. Um zu beschreiben, wie ein möglicher Partner //P// eines gegebenen Netzes //N// ausschauen darf, wurde am Lehrstuhl das Konzept der Bedienungsanleitungen entwickelt. Im Zusammenhang mit stochastischen Netzen stellen sich hier zwei Fragen: 1. Wenn ein Partner //P// in einem bestimmten Zustand, mit welcher Wahrscheinlichkeit ist //N// in welchem Zustand? 2. Analog dazu, was lässt sich über die Zustände von //P// sagen, wenn //N// in einem bestimmten Zustand ist.
Ziele	Es soll der Formalismus der Stochastischen Petrinetze auf offene Netze erweitert werden. Auf Basis der dafür notwendigen Definitionen soll der Begriff der Bedienungsanleitung um stochastische Informationen erweitert werden, mit dem Ziel, die beiden zuvor genannten Fragen beantworten zu können. Die Ergebnisse sollen anschließend in die am Lehrstuhl existierende Toollandschaft integriert werden.
Voraussetzungen	Sehr empfohlen sind stochastische Grundkenntnisse und Erfahrung in C++, wünschenswert sind Kenntnisse über Petrinetze.
Ansprechpartner	Christian Gierds
Umfang/Rahmen	eine Diplomarbeit

Laufende Arbeiten

Diplomarbeiten

Optimierung der Sweeplinemethode (Robert Prüfer)

Problemstellung	Bei der Suche nach erreichbaren Zuständen in Transitionssystemen kann mittels der Sweep-Line-Methode Speicherplatz gespart werden, indem einmal gefundene und nicht mehr benötigte Zustände gelöscht werden. Dafür wird eine Progress Measure benötigt, um zu entscheiden, welche Zustände gelöscht werden können. Für Petrinetze kann diese Progress Measure automatisch berechnet werden; allerdings lässt die bisherige Berechnung verschiedene Freiheitsgrade zu. Unter Anwendung verschiedener heuristischer Optimierungsverfahren soll untersucht werden, ob die Progress Measure verbessert werden kann.
Ziele	Finden geeigneter Heuristiken zur Steigerung der Leistungsfähigkeit der Sweep-Line-Methode
Ansprechpartner	Daniela Weinberg
Umfang/Rahmen	eine Diplomarbeit

Kosten- und Lastenanalyse von Prozessen im Katastrophenmanagement (Konstanze Swist)

Problemstellung	Es soll untersucht werden, inwiefern die Planung von Katastrophenmanagementprozesse mit bereits bestehenden Simulations- und Analystechniken unterstützt werden kann. Die Arbeit in Katastrophensituationen ist insbesondere durch beschränkte Resourcen und zum Teil zeitkritische Arbeitsschritte gekennzeichnet. Für zuverlässiges Handeln in einem Katastrophenfall erscheint es daher sinnvoll, vor dem tatsächlichen Einsatz, verschiedene Handlungsszenarien hinsichtlich der benötigten Resourcen, der entstehenden Kosten und der erforderlichen Zeit durchzurechnen. Im Bereich der Workflow-Modellierung und aus der Petrinetztheorie sind eine Reihe von Simulations- und Analysetechniken bekannt, die sich für diese Aufgabe prinzipiell eignen. In vorrangegangenen Arbeiten wurde am Lehrstuhl der Prozess der "Taskforce Erdbeben" des GFZ Potsdam in einer domänenspezifischen Workflowsprache modelliert; zu dieser Sprache gibt es eine Petrinetzsemantik. In der Arbeit soll anhand des bestehenden Modells untersucht werden, welche Techniken und Werkzeuge zur Prozessplanung im Katastrophenmanagement relevante Fragestellungen in welcher Qualität beantworten können.
Ziele	- Erarbeiten von für die Prozessplanung im Katastrophenmanagement typischer Fragestellung - Ermitteln geeigneter Werkzeuge zur Beantwortung der Fragen - Erweiterung des bestehende Prozessmodells um dafür benötigte Parameter - Implementation der Petrinetzsemantik in einem Werkzeug - Durchführung eines Experimentes zur beispielhaften Beantwortung einer typischen Fragestellung mit den ermittelten Werkzeugen - Auswertung des Experiments
Betreuer	Dirk Fahland
Umfang/Rahmen	eine Diplomarbeit

Studienarbeiten

Implementierung einer grafischen Benutzeroberfläche für Tools4BPEL (Janine Ott)

Problemstellung	Am Lehrstuhl werden seit Oktober 2005 im Projekt Tools4BPEL mehrere Werkzeuge zur Analyse von Geschäftsprozessen entwickelt. Diese Prototypen werden derzeit mit Kommandozeilenparametern kontrolliert, was ob der Fülle an Funktionen zunehmend unübersichtlich wird. Damit auch Nicht-Experten die Werkzeuge benutzen können, soll eine grafische Benutzeroberfläche (GUI) implementiert werden, die die Funktionen der einzelnen Werkzeuge übersichtlich darstellt und (bswp. mit Hilfe von Assistenten) oft verwendete Anwendungsszenarien unterstützt.
Ziele	Da die Werkzeuge in C++ geschrieben sind, soll auch die GUI in dieser Sprache implementiert werden. Um weiterhin Plattformunabhängigkeit (Windows, Linux, Mac OS) sicherzustellen, bietet sich die Qt-Bibliothek von Trolltech http://trolltech.com/products/qt an. Die GUI soll die bestehenden Werkzeuge ausreichend einfach steuern und den Nutzer weitgehend unterstützen. Weiterhin soll die GUI leicht für neue Funktionen erweiterbar sein. Zuletzt sollen grundlegende Funktionen implementiert werden, mit denen von den Werkzeugen erstellte Dateien (z.B. XML-Dokumente oder PNG-Grafiken) innerhalb der GUI angezeigt werden können.
Voraussetzungen	Kenntnisse in der Programmiersprache C++ sind vorteilhaft. Kenntnisse der Qt-Bibliothek sind hilfreich, jedoch wegen einer exzellenten Dokumentation nicht notwendig.
Beginn	sofort
Ansprechpartner	Christian Gierds
Umfang/Rahmen	eine Studienarbeit

Strukturelle Reduktion von Adaptern (Richard Müller)

Problemstellung/Ziel	Bei der Synthese von Verhaltensadaptern wird in einem ersten Schritt aus einer Spezifikation elementarer Aktivitäten (SEA) eine Engine generiert, welche für die zu adaptierenden Services die Einhaltung der semantischen Regeln gemäß der SEA sicherstellt. In einem zweiten Schritte wird für die Komposition aus Engine und Services ein Kontroller berechnet. Die Laufzeit des Kontroller-Synthese-Algorithmus hängt stark von der Größe der Engine und der Anzahl der darin umgesetzten elementaren Aktivitäten ab. Ziel der Arbeit ist es, die Engine strukturell so zu vereinfachen (z.B. durch Entfernen nichtnutzbarer Aktivitäten), das der Kontroller-Synthese-Algorithmus beschleunigt werden kann, dabei die Menge der möglichen Adapter jedoch erhalten bleibt.
Betreuer	Christian Gierds
Umfang/Rahmen	eine Studienarbeit