Dr. Markus Nebel

"Zufall in der Algorithmik"

Immer häufiger sind neu vorgestellte Algorithmen randomisiert, d.h. sie greifen zur Beeinflussung ihrer Berechnung auf eine Quelle von unabhängigen und meist gleichverteilten Zufallsbits zurück. Hierbei entstehen zwei Qualitäten von Algorithmen. Erstens gibt es Verfahren, bei denen trotz zufälliger Entscheidungen stets eine korrekte Lösung berechnet wird; der randomisierte Quicksort sei als Beispiel genannt. Zweitens entstehen heuristische Verfahren, die mit einer geringen Wahrscheinlichkeit auch falsche Lösungen ausgeben. Dies ist beispielsweise bei einer randomisierten Lösung des MinCut-Problems zu beobachten.

Wir wollen hier auf zwei verwandte Aspekte des Zufalls in der Algorithmik eingehen:

Im ersten Teil des Vortrags befassen wir uns mit einer neuen Idee, wie ein Algorithmus Nutzen aus dem Zufall ziehen kann und dennoch stets eine korrekte Lösung liefert. Dazu untersuchen wir das String-Matching-Problem (SMP), also die Suche nach allen Vorkommen eines Wortes in einem Text. Dieses Problem findet seit neustem wieder verstärkt Beachtung, da es in den sog. Computational Sciences und besonders in der Bioinformatik häufig Anwendung findet. Ein bekanntes Verfahren zur Lösung des SMPs ist der Algorithmus nach Horspool, der besonders bei großen Alphabeten eine gute Laufzeit aufweist. Zur Beschleunigung dieses Verfahrens nutzen wir die Verteilung der Symbole im Text aus, d.h. wir verwenden statistische Eigenschaften der zufälligen Eingabe, um den Algorithmus zu verbessern. Dabei ist es nicht notwendig, diese Statistik für jede Eingabe neu zu bestimmen, es genügt eine vorab bekannte Verteilung (z.B. die Verteilung der verschiedenen Buchstaben im Deutschen oder die Verteilung der Aminosäuren in Proteinsequenzen) der die Eingabe entstammt. Zum Vergleich beider Varianten bestimmen wir ihre erwarteten Laufzeiten (Average-Case) unter der Annahme eines zufälligen, multinomial verteilten Textes mit probabilistischen Methoden. Das Ergebnis zeigt, daß das Originalverfahren bei uniform verteilten Symbolen leichte Vorteile besitzt und daß der modifizierte Algorithmus umso überlegener wird, desto länger das Wort und desto asymmetrischer die Symbolverteilung der Eingabe ist.

Im zweiten Teil des Vortrages beschäftigen wir uns mit der Average-Case Analyse von Güteparametern, die gerade im Kontext randomisierter Algorithmen von großem Interesse ist, da dort Parameter oft selbst für eine feste Eingabe bereits einen zufälligen Wert besitzen. Will man jedoch sinnvoll über alle Eingaben mitteln, um das erwartete Verhalten eines Verfahrens bei einer typischen Eingabe zu bestimmen, so muß die Verteilung der Eingaben bekannt sein. Dies ist für viele Anwendungen jedoch nicht gewährleistet. Wir skizzieren einen neuen Ansatz für die Average-Case Analyse und zeigen, wie aus Simulationen oder aus Beobachtungen der Anwendung mathematisch handhabbare Modelle gewonnen werden können, aus denen wir dann die gesuchten Erwartungswerte, aber auch höhere Momente ableiten. Zur Illustration des Ansatzes betrachten wir die Datenstruktur Trie, deren erwartete Größe wir bestimmen. Abschließend geben wir Hinweise darauf, wie dieselbe Methode auch verwendet werden kann, um realitätsnahe Modelle für die Struktur von Biomolekülen zu gewinnen, und welche Resultate aus solchen Modellen abgeleitet werden können.