Vorlesung Randomisierte Algorithmen

In vielen praktischen Anwendungen sind Algorithmen selbst dann nicht effizient genug, wenn die Rechenzeit zwar polynomiell, aber z.B. wie n hoch 3 wächst. Dann bilden randomisierte Algorithmen, die auf die Ergebnisse von unabhängigen Münzwürfen (in der Praxis Pseudozufallszahlen) zurückgreifen können, eine attraktive Alternative. Es gibt randomisierte Algorithmen, die das richtige Resultat in einer bestimmten mittleren Rechenzeit liefern. Bei anderen randomisierten Algorithmen ist zwar eine obere Schranke für die Rechenzeit gesichert, die Antwort des Algorithmus kann jedoch mit kleiner Wahrscheinlichkeit "weiß nicht" lauten. Selbst randomisierte Algorithmen, die mit kleiner Wahrscheinlichkeit falsche Ergebnisse liefern, sind von praktischer Bedeutung, wenn sie wesentlich schneller als die besten bekannten "normalen", also deterministischen Algorithmen sind. In dieser Spezialvorlesung sollen Entwurf und Analyse randomisierter Algorithmen behandelt werden, wobei die Grundlagen aus der Wahrscheinlichkeitsrechnung dann vorgestellt werden, wenn sie gebraucht werden. Kenntnisse in Wahrscheinlichkeitstheorie werden also nicht vorausgesetzt, sondern anhand von Anwendungen innerhalb der Informatik entwickelt. Da randomisierte Methoden in immer mehr Informatikgebiete eindringen, ergibt sich hier die Möglichkeit, nicht nur wichtige Algorithmen kennenzulernen, sondern sich gezielt mit den Ergebnissen der Wahrscheinlichkeitstheorie vertraut zu machen, die in der Informatik benutzt werden.