Vorlesung Randomisierte Algorithmen (WS 2002/03)Wie kann Zufall helfen? - Die Antwort liefern randomisierte oder zufallsgesteuerte Algorithmen. In vielen Anwendungskontexten, in denen deterministische Lösungen oft zu kompliziert und damit unpraktisch sind, bieten randomisierte Algorithmen eine einfache und damit praktikable Lösung. In dieser Spezialvorlesung sollen Entwurf und Analyse randomisierter Algorithmen behandelt werden, wobei die Grundlagen aus der Wahrscheinlichkeitstheorie dann vorgestellt werden, wenn sie gebraucht werden. Tiefgreifende Kenntnisse in Wahrscheinlichkeitstheorie werden also nicht vorausgesetzt, sondern anhand von Beispielen aus der Informatik entwickelt. Wir behandeln randomisierte Algorithmen insbesondere aus den Bereichen Sortieren, Lastverteilung, Graphenalgorithmen, Routingverfahren und Datenmanagement in Netzwerken.
Skript zur Vorlesung (in englischer Sprache)Tutorial "Balls and Bins"Übungen
Homepage of Berthold Vöcking |