23. Juli 2012

NODES – Offering Dynamics to Emerging Structures

Ganz praktisch: Wenn der Bäcker zum Kunden kommt

Eigentlich wäre es schon fast nicht mehr nötig, dass der Bäcker in einem festen Ladenlokal untergebracht ist, das sich immer an der gleichen Stelle befindet. Hätte jeder ein Smartphone mit Internetzugang, so könnte man sonntagmorgens einfach das Smartphone nach der nächstgelegenen Brötchenquelle befragen und sich dorthin auf den Weg machen. Der Bäcker seinerseits könnte sich mit seinem Brötchenwagen stets so postieren, dass der durchschnittliche Anfahrtsweg seiner Kunden minimal wäre – je nachdem, wer an diesem Morgen überhaupt Brötchen haben möchte. Doch nach welchen Kriterien sollte der Bäcker seine Position auswählen?

Diese Fragestellung illustriert eins der Probleme, mit denen sich die Teilnehmer der Projektgruppe „NODES – Offering Dynamics to Emerging Structures“ in der Fachgruppe Algorithmen und Komplexität von Prof. Friedhelm Meyer auf der Heide in den vergangenen zwei Semestern beschäftigt haben. Alle Probleme hatten dabei drei Dinge gemeinsam: Erstens mussten die Beteiligten einer Problemwelt oder eines Netzwerks stets autonome Entscheidungen treffen. Im obigen Beispiel heißt dies, dass nicht etwa der Chef der Bäckereikette vorgibt, wo sich seine Mitarbeiterinnen und Mitarbeiter postieren, sondern dass diese über ihre Position selbst entscheiden und dabei nur Kenntnis über das Kaufverhalten in ihrer näheren Umgebung besitzen. Zum Zweiten sahen sich die Beteiligten stets sogenannten externen Dynamiken ausgesetzt. Im Beispiel wäre dies die Veränderung des Kaufverhaltens, auf die der Bäcker ja keinen Einfluss hat. Drittens konnten die Beteiligten auf diese äußeren Einflüsse mit kontrollierten Dynamiken reagieren. So kann der Brötchenverkäufer seinen Brötchenwagen fortbewegen, um auf ein geändertes Kaufverhalten zu reagieren.

Für das obige Beispiel untersuchten die Projektgruppenteilnehmer einen stark vereinfachten Fall, der sich als kompliziert genug herausstellen sollte: Ein Brötchenverkäufer kann sich zwischen zwei Dörfern bewegen. Über den Sonntagmorgen verteilt wollen mal nur die Bewohner des einen Dorfes, mal nur die des anderen Dorfes seine Backwaren erwerben. Das Ergebnis: Wenn sich der Brötchenverkäufer immer, so schnell es geht, in die Richtung des gerade hungrigen Dorfes bewegt, erreicht er damit, dass die Gesamtweglänge seiner Kunden bis auf einen Faktor von unter 2,5 optimal ist.

Die Projektgruppe ist eine einjährige Wahlpflichtveranstaltung im Masterstudiengang Informatik an der Universität Paderborn. Die Teilnehmer arbeiten in Gruppen von sechs bis 18 Personen rund 20 Stunden pro Woche an verschiedenen Themen, die aktuellen Forschungsbezug aufweisen. In der Projektgruppe NODES wurden die Studierenden dabei von Meyer auf der Heide und seinen Mitarbeitern betreut. Der studentische Projektgruppenleiter Stefan Heindorf resümiert: „Die Projektgruppe war für uns alle eine wertvolle Erfahrung. Wir haben vielseitige Einblicke in den Forschungsalltag der theoretischen Informatik gewonnen und dabei interessante Ergebnisse erzielen können.“

 

Fachlicher Ansprechpartner:

Dipl.-Math. M.Sc. Andreas Cord-Landwehr
Telefon: 0 52 51 | 60-64 28
E-Mail: cola@upb.de