Probabilistische Algorithmen SS11

Pseudozufallszahlen

Bei probabilistischen Algorithmen spielen Zufallszahlen eine besondere Rolle. Höhere Programmiersprachen verfügen über Sprachelemente für Zufallszahlen. In Racket beispielsweise random. Es wird eine natürliche Zahl n als Eingabe erwartet. Die Ausgabe ist eine natürliche Zahl r mit 0 \le r < n. Die Transformation in ein abgeschlossenes Intervall [a,b] natürlicher Zahlen lässt sich leicht bewerkstelligen. Wie folgendes Beispiel zeigt.

Numerische probabilistische Algorithmen

Algorithmen dieser Art produzieren eine Näherungslösung mit wählbarer Genauigkeit.

Ein Beispiel für diese Klasse von Algorithmen ist die Bestimmung einer Näherung für die Zahl \pi durch "Zufallsregen". Dabei werden n Regentropfen auf eine quadratische Fläche fallen gelassen, in der sich ein Kreis befindet. Anschließend werden die Regentropfen gezählt, die innerhalb des Kreises gefallen sind.

Es wird angenommen, dass jeder Punkt im Quadrat exakt dieselbe Wahrscheinlichkeit hat, von einem Tropfen getroffen zu werden. Ist der Radius des Kreises r, so ist seine Fläche \pi r^2, wobei die Fläche des Quadrats 4r^2 ist. Somit ist der durchschnittliche Anteil der Tropfen, die innerhalb des Kreises landen, \pi r^2 / 4r^2 = \pi / 4. Damit kann \pi mit \pi \approx 4 k / n geschätzt werden.

Codebeispiel eines Algorithmus, der mit "Zufallsregen" arbeitet. Je höher n gewählt wird umso genauer lässt sich \pi abschätzen.