Randomisierter_Algorithmus
Randomisierter_Algorithmus

== Derandomisierung ==
Unter Derandomisierung versteht man die Verringerung der Anzahl der Zufallsbits, die ein randomisierter Algorithmus benutzt. Dies ist aus dem folgenden Grund nützlich:
Man kann jeden randomisierten Algorithmus deterministisch machen, indem man ihn für alle Belegungen der Zufallsbits simuliert. Allerdings bedeutet dies, dass bei der Verwendung von  Zufallsbits die Rechenzeit um einen Faktor  steigt, was in den meisten Fällen zu exponentieller Rechenzeit führt. Falls aber der Algorithmus bei Eingabelänge  nur  Zufallsbits benötigt, führt dies nur zu einer polynomiellen Vergrößerung der Rechenzeit.
Ein Ansatz zur Derandomisierung besteht darin, genauer zu analysieren, wie der Algorithmus die Zufallsbits benutzt. Bei manchen randomisierten Algorithmen genügt es, dass die verwendeten Zufallsbits paarweise unabhängig sind. Man kann nun beispielsweise  paarweise unabhängige Zufallsvariablen aus  vollständig unabhängigen Zufallsvariablen erzeugen. In einem zweiten Schritt kann man den Algorithmus mit dem zuvor beschriebenen Ansatz deterministisch machen.