Direkt zum Inhalt

Lexikon der Mathematik: randomisierter Algorithmus

ein Algorithmus, der mit zufälligen Bits arbeitet, die in den Anwendungen Pseudozufallszahlen sind.

Somit besteht ein randomisierter Algorithmus aus einer Klasse von Algorithmen und einer Wahrscheinlichkeitsverteilung auf dieser Klasse. Randomisierte Algorithmen können wesentlich effizienter sein als die besten bekannten deterministischen Algorithmen.

Wenn ein Algorithmus seine Aufgabe lösen kann, indem er eines von m guten Objekten aus einer Menge von 2m Objekten benutzt, sind deterministisch im worst case m +1 Versuche nötig, während bei zufälliger Wahl durchschnittlich zwei Versuche genügen.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos