Algorithmen, Struktur, Zufall - Hauptseite Algorithmen, Struktur, Zufall

Leitfragen des Forschungsprogramms

Das Forschungsprogramm kann unter vier Leitfragen subsummiert werden:

Leitfrage 1: Charakterisierung zufälliger Objekte

In der klassischen Graphentheorie und Kombinatorik stehen deterministische Konstruktionen im Vordergrund, etwa die Frage, welche Bedingungen ein Graph, eine partielle Ordnung oder ein anderes kombinatorisches Objekt erfüllen muss, um auf jeden Fall eine bestimmte Eigenschaft zu haben.

Im Gegensatz dazu betrachtet man bei der Charakterisierung zufälliger Objekte Klassen diskreter Objekte mit gegebenen Wahrscheinlichkeitsverteilungen. Im Mittelpunkt steht hier die Bestimmung der Wahrscheinlichkeit, mit der diese zufälligen diskreten Strukturen bestimmte Eigenschaften haben. Das Ziel ist es, durchschnittliche Werte von Parametern zu bestimmen sowie typische Eigenschaften zu finden, deren Wahrscheinlichkeit bei wachsender Größe der Objekte gegen Eins strebt. Eine solche Charakterisierung gestaltet sich oft verhältnismäßig einfach, wenn sich die Objekte durch lokale, voneinander unabhängige Zufallsexperimente modellieren lassen. Das Paradebeispiel für ein solches Modell ist die klassische Theorie zufälliger Graphen Gn,p, deren Kanten mit Wahrscheinlichkeit p unabhängig voneinander existieren. Die Frage wird aber ungleich schwieriger, wenn man Graphen untersucht, die zufällig aus einer festgelegten Graphenklasse ausgewählt werden.

Leitfrage 2: Charakterisierung von Objekten durch Zufall

Während in den bisher erwähnten Fragestellungen die Wahrscheinlichkeitsverteilungen als Ausgangspunkt vorgegeben waren und es darum ging, typische Eigenschaften ihrer Repräsentanten zu ermitteln, kommt nun im Rahmen der Leitfrage 2 - Charakterisierung von Objekten durch Zufall - der Zufall wieder verstärkt als Werkzeug denn als primäres Untersuchungsobjekt zur Geltung. Dementsprechend sollen nun beispielsweise die Wahrscheinlichkeitsverteilungen so ausgerichtet werden, dass sie bestimmten Anforderungen genügen.

Ein Ziel sind dabei Existenzbeweise mit Hilfe der sogenannten probabilistischen Methode: statt ein gewünschtes Objekt mit bestimmten Eigenschaft haarklein zu konstruieren, führt man eine Reihe von Zufallsexperimenten durch und zeigt, dass die Wahrscheinlichkeit, am Ende die erforderliche Struktur in den Händen zu halten, positiv ist - und ergo ein solches Objekt existieren muss. Nicht von ungefähr ergeben sich hierbei manchmal Parallelen zu den Methoden der Leitfrage 4 - es handelt sich schließlich um randomisierte Verfahren.

Weitere generelle Ziele, die unter Leitfrage 2 fallen, sind die Modellierung und die Analyse komplexer realer Netzwerke (wie beispielsweise das World-Wide-Web, soziale Bekanntschaftsnetzwerke etc.). Der Hintergedanke ist, dass an vielen dieser realen Netzwerke eine Anzahl von prinzipiell ähnlichen Eigenschaften (insegesamt wenige Kanten, trotzdem ein geringer Durchmesser und ein lokal hoher Vernetzungsgrad) empirisch beobachtet wurde, die man gerne mathematisch präzisieren und modellieren möchte. Die zugrunde liegende Vision besteht darin, durch eine Modellierung mit anschließender Analyse die realen Netzwerke besser zu "verstehen". Verbunden damit ist die Hoffnung, dass sich dann weitere Eigenschaften abzeichnen, die sich auch in den realen Strukturen wiederfinden und die es beispielsweise ermöglichen, speziell abgestimmte Such­ oder Sortierverfahren für diese Netzwerke zu entwerfen.

Leitfrage 3: Analyse von Algorithmen bei zufälliger Eingabe

Algorithmen werden klassischerweise aus einer Worst­Case­Sichtweise bewertet - ihre Leistung wird an der (für sie) schwierigsten Eingabe gemessen. Diese Bewertung beruht auf der Konstruktion artifizieller Eingaben für komplexitätstheoretische Reduktionen, während sich aber ein im Worst­Case schlechter Algorithmus häufig in der Praxis gut bewährt. Das Beispiel par excellence hierfür ist der Simplexalgorithmus.

Die Leitfrage 3 - Analyse von Algorithmen bei zufälliger Eingabe - betrachtet die Leistung eines Algorithmus nun aus folgendem Blickwinkel: Wie verhält sich dieser bei einer Eingabe, die gemäß einer Wahrscheinlichkeitsverteilung auf dem Raum der Eingaben zufällig ausgewählt wurde? Hierbei stehen im Wesentlichen zwei verschiedene Kriterien zur Diskussion, nämlich die erwartete Laufzeit und die erwartete Qualität der Lösung, gemessen am "Abstand" zur optimalen Lösung. Diese probabilistische Sichtweise, auch als Average­Case­Analyse eines Algorithmus bekannt, unternimmt den Versuch, das in der Praxis beobachtete Verhalten theoretisch abzusichern.

Leitfrage 4: Analyse von Algorithmen, die Zufall nutzen

Während unter Leitfrage 3 der Gegenstand der Untersuchung das Verhalten deterministischer Algorithmen auf zufälligen Eingaben ist, betrachten wir unter dieser Leitfrage Algorithmen, die in ihrem Ablauf Entscheidungen auf Grund von Zufalls-Experimenten fällen. Dabei werden in der Regel deterministische Eingaben betrachtet, d.h. es werden im klassischen Sinne Worst-Case-Analysen durchgeführt. Der Einbau von Zufalls-Elementen in Algorithmen kann hierbei mit zwei verschiedenen Zielsetzungen erfolgen.

Fasst man die klassische Worst-Case-Analyse von Algorithmen (sei es mit dem Ziel der Laufzeitabschätzung oder der Garantie einer gewissen Güte der produzierten Lösung) als ein Spiel auf, bei dem ein "böswilliger" Gegner versucht, einen Algorithmus zu "diskreditieren", indem er für genau diesen Algorithmus möglichst schwierige Instanzen konstruiert, so kann der Einbau von Zufallsentscheidungen in den Algorithmus die Möglichkeiten dieses Gegners enorm beschneiden (sofern man als Maßstab für die Worst-Case-Analyse die erwartete Laufzeit bzw. Güte über alle Zufallsentscheidungen des Algorithmus wählt). Zudem weisen randomisierte Algorithmen häufig nicht nur eine ausgesprochen gute Qualität hinsichtlich der Güte der von ihnen produzierten Lösungen oder ihrer Laufzeit auf, sondern sie sind oft auch überraschend elegant.

zuletzt geändert am 02.02.2006 (alkox-www)