Einführung in probalistische Algorithmen

von Gruppe 1

Was sind probalistische Algorithmen?

Probalistische, oder auch stochastische oder randomatisierte Algorithmen, zeichnen sich dadurch aus, dass der intere Ablauf eines Programms dem Zufall unterliegt. Im Gegensatz dazu gibt es die deterministischen Programme, bei welchen der Ablauf von vornhinein fest steht.

Man kann sich probalistische Algorithmen als deterministischen Algorithmus vorstellen, bei dem jede Entscheidungsmöglichkeit im Programm einer gewissen Wahrscheinlichkeit unterliegt. Für eine fixe Inputgröße x kann der probalistische Algorithmus evt. unterschiedliche Ergebnisse liefern und/oder unterschiedliche Zeiten zur Berechnung brauchen. Algorithmen, deren Ergebnis immer korrekt ist, falls sie eines liefern, heißen Las-Vegas-Algorithmen. Im Gegensatz dazu gibt es Monte-Carlo-Algorithmen, welche zwar immer ein Ergebnis liefern, welches aber nicht zwangsläufig korrekt sein muss.

Wozu probalistische Algorithmen

Randomatisierte Algorithmen können effizienter arbeiten und einfachter zu verstehen und implementieren sein als die besten deterministischen Algorithmen für das gleiche Problem. Zur Bestimmung einer Primzahl gibt es etwa

1. einen effizient in Polynomzeit arbeitenden probalistischen Algorithmus,
2. keinen bekannten deterministischen, in Polynomialzeit arbeitenden Algorithmus und
3. es ist nicht bekannt, ob es sich um ein P oder NP- Problem (oder EXPTIME) handelt (Also ob das Problem mit einem deterministischen Algorithmus in Polynomialer Zeit oder nichtdeterministisch in Polynomialer Zeit gelößt werden kann.