Ins Netz gegangen

„Petrinetze“ beschreiben komplexe Systeme, etwa Geschäftsprozesse in Unternehmen. Zur zügigen Prüfung dieser Petrinetze entwickelte Robin Bergenthum in seiner Dissertation einen Algorithmus.


Fakultätspreis für die Informatik-Dissertation von Dr. Robin Bergenthum über „Petrinetze“ an der FernUni verliehen

Junger Mann lächelt. Im Hintergrund das Informatikzentrum der FernUniversität in Hagen. Dr. Robin Bergenthum entwickelte in seiner Dissertation einen Algorithmus zur zügigen Prüfung von Petrinetzen.
Dr. Robin Bergenthum entwickelte in seiner Dissertation einen Algorithmus zur zügigen Prüfung von Petrinetzen.

Bohnen mahlen, Filter einlegen, Wasser einfüllen und Maschine einschalten. So oder ähnlich gehört Kaffeekochen für die meisten Menschen zur täglichen Routine. Aber warum nicht erst den Filter einlegen und dann die Bohnen mahlen? „Das Problem bei der Modellierung komplexer Systeme in der Informatik sind die vielen Möglichkeiten, wie diese ablaufen können. Würde man das einfache Beispiel ‚Kaffeekochen‘ darstellen, gäbe es schon mehr als 60 Möglichkeiten“, sagt Dr. Robin Bergenthum, Wissenschaftlicher Mitarbeiter am Lehrgebiet Softwaretechnik und Theorie der Programmierung (Prof. Dr. Jörg Desel) der FernUniversität in Hagen. Aufgabe der Informatik ist es aber auch, diese komplexen Prozesse darzustellen und deren Durchführbarkeit zu überprüfen.

Für seine Dissertation über die „Verifikation von halbgeordneten Abläufen in Petrinetzen“ zur Überprüfung komplexer Prozesse erhielt Dr. Robin Bergenthum im Zuge eines Kolloquiums den Preis der Fakultät für Mathematik und Informatik. Er entwickelte einen Algorithmus, der zügig Auskunft über die Ausführbarkeit von Abläufen in nebenläufigen Systemen gibt. Wissenschaftlerinnen und Wissenschaftler sowie Unternehmen, die Modelle auf der Basis von Petrinetzen verwenden, können künftig mit Bergenthums Algorithmus wesentlich schneller und einfacher arbeiten. Dotiert ist der Preis mit 5.000 Euro. Das Kolloquium war eine Veranstaltung im Rahmen des Hagener Forschungsdialogs.

Petrinetz mit „Transitionen“ für mögliche Aktionen wie „Kaffeebohnen mahlen“. Die „Plätze“ (Kreise) und „Marken“ (schwarze Punkte) beschreiben Zustände des Petrinetzes: Hier können die ersten drei Aktionen („Kaffeebohnen mahlen“, „Kaffeemaschine entriegeln“ und „Wasser mit Glaskanne holen“) durchgeführt werden.
Petrinetz mit „Transitionen“ für mögliche Aktionen wie „Kaffeebohnen mahlen“. Die „Plätze“ (Kreise) und „Marken“ (schwarze Punkte) beschreiben Zustände des Petrinetzes: Hier können die ersten drei Aktionen („Kaffeebohnen mahlen“, „Kaffeemaschine entriegeln“ und „Wasser mit Glaskanne holen“) durchgeführt werden.

Beschreibung komplexer Szenarien

Der Informatiker Carl Adam Petri entwickelte das nach ihm benannte „Petrinetz“ in den 1960er Jahren. Es ist eine Modellierungssprache zur Beschreibung von Szenarien, in denen Ereignisse abhängig oder auch unabhängig voneinander ablaufen können. Zum Beispiel die verschiedenen Varianten beim Kaffeekochen.

Grafisch dargestellt ähneln Petrinetze Spielbrettern: Denn es gibt Kästen, sogenannte „Transitionen“. Sie enthalten Anweisungen wie „Kaffeebohnen mahlen“ oder „Filter füllen“. Es gibt Kreise, sogenannte „Plätze“ und es gibt Spielsteine, die „Marken“ in Petrinetzen. Transitionen und Plätze sind durch Pfeile verbunden. Diese verdeutlichen die Abhängigkeiten zwischen den Aktionen – und damit mögliche Wege der Spielsteine. Zum Beispiel auf das Feld „Bohnen mahlen“ vorrücken und dann weiterziehen zu „Filter füllen“.

Fakultätspreis Mathematik und Informatik (M+I)

Der Fakultätspreis M+I wurde erstmals 2012 vergeben. Gestiftet wird der mit 5.000 Euro dotierte Preis von Prof. Dr.-Ing. Firoz Kaderali, Emeritus der FernUni-Fakultät Mathematik und Informatik. Zur Verfügung gestellt wird das Preisgeld für die weitere Forschung der Preisträgerin beziehungsweise des Preisträgers.

Effizienter Algorithmus

Die formale „Verifikation“, also die Überprüfung, einer großen Menge an Abläufen sei zwar schwer, aber notwendig. „Zum Beispiel um zu wissen, ob das Modell überhaupt funktioniert. Also ob zum Beispiel immer trinkbarer Kaffee aus der Maschine läuft .“ Eine weitere Herausforderung: „Herausfinden, welcher Weg der schnellste ist“, beschreibt Bergenthum.

Diese Probleme löste der Informatiker in seiner Dissertation: „Mit meinem Algorithmus ist die Überprüfung der Abläufe effizienter.“ Er hilft also beim Modellieren des Systems. Und er verkürzt die Testphase eines Petrinetzes.

Weiterforschen dank Fakultätspreis

Durch den Fakultätspreis kann sich Robin Bergenthum weiter ganz auf seine wissenschaftliche Laufbahn konzentrieren: „Auch in Zukunft werde ich an einer effektiveren Verwendung von Petrinetzen forschen. Unter anderem möchte ich Systeme nicht nur verifizieren. In Zukunft soll das passende Modell aus einer Menge von Abläufen automatisch erstellt werden.“

Der Kaffee wird so zwar nicht besser schmecken, aber das Modellieren dieser Systeme würde deutlich einfacher werden.

Matthias Fejes | 21.01.2015