Randomisierter Algorithmus

Ein randomisierter Algorithmus (auch stochastischer oder probabilistischer Algorithmus) ist ein Algorithmus, der versucht, durch die Wahl von zufälligen Zwischenergebnissen zu einem (im Mittel) guten bzw. näherungsweise korrekten Ergebnis zu gelangen. Er bildet somit das Gegenstück zum deterministischen Algorithmus. Es wird dabei nicht verlangt, dass ein randomisierter Algorithmus immer effizient eine richtige Lösung findet. Randomisierte Algorithmen sind in vielen Fällen einfacher zu verstehen, einfacher zu implementieren und effizienter als deterministische Algorithmen für dasselbe Problem. Ein Beispiel, das dies zeigt, ist der AKS-Primzahltest, der zwar deterministisch ist, aber viel ineffizienter und viel schwieriger zu implementieren als beispielsweise der Primzahltest von Solovay und Strassen.