Randomisierte Algorithmen: Beispiele und Anwendungen

Ein randomisierter (auch: zufalliger oder stochastischer) Algorithmus verwendet zufallige Ereignisse bei seiner Durchfuhrung. In vielen Situationen haben zufallige Algorithmen Vorteile gegenuber deterministischen Algorithmen. In diesem Kapitel wird keine allgemeine Theorie entwickelt, sondern einige randomisierte Algorithmen und haufig verwendete Methoden werden anhand relative einfacher Beispiele illustriert. Solche Beispiele konnen in der Praxis als Teilprobleme eines groseren Algorithmus auftreten.