Ebook: Randomisierte Algorithmen

Nehmen wir an, daß es jedes Jahrtausend mindestens einen Meteoriteneinschlag gibt, der mehr als 100 Quadratmeter der Erdoberfläche verwüstet. Dann läßt sich folgern, daß ein Rechner während einer Mikrosekunde seines Daseins mit einer Wahrscheinlichkeit von mindestens zerstört wird. Von diesem Standpunkt aus erscheint ein Algorithmus, der mit Fehlerwahrscheinlichkeit kleiner in Sekundenschnelle - 593 als die größte Primzahl kleiner identifiziert, als sehr praktisch (insbesondere in Bezug auf dahinterstehende, kryptologische Anwendungen). Ein randomisierter Algorithmus ist ein Algorithmus, dessen Verhalten in jedem Schritt von einem Zufallsexperiment ("Münzwurf") abhängen kann. Da sich randomi-sierte Algorithmen nicht mehr deterministisch verhalten, können die Laufzeit und/oder die Korrektheit nur noch mit gewissen Wahrscheinlichkeiten garantiert werden. Es gibt zwei grundsätzliche Vorteile randomisierter Algorithmen gegenüber "normalen" (deterministischen) Algorithmen: Effizienz und Einfachheit (letzteres führt oft auch zu besserer Implementier-barkeit). In der Vorlesung werden grundlegende randomisierte Algorithmen für verschiedenste Anwendungen vorgestellt. Zudem werden randomisierte Komplexitätsklassen betrachtet und einige Methoden und Werkzeuge für die Analyse randomisierter Algorithmen bereitgestellt.