Probabilistische Algorithmen SS11

Pseudozufallszahlen

Bei probabilistischen Algorithmen spielen Zufallszahlen eine besondere Rolle. Höhere Programmiersprachen verfügen über Sprachelemente für Zufallszahlen. In Java gibt es beispielsweise die Klasse Random. Es wird eine natürliche Zahl n als Argument 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.

Die Erzeugnung von Zahlen nach obigen Beispiel erfolgt jedoch nicht rein zufällig. Sie werden deterministisch berechnet d.h. es gibt Prozduren, die in der Lage sind, lange Folgen von Werten zu generieren, die scheinbar die Eigenschaften zufälliger Folgen haben.

Ein Verfahren zum erzeugen von Zufallszahlen ist die Kongruenzmethode, die 1948 von D. H. Lehmer entwickelt wurde. Ausgehend von einem Startwert, dem sogenannten Seed wird folgende rekursive Vorschrift angewand.

z_{n} = (a * z_{n-1} + b) mod c

dabei sind

• a ein Multiplikator, der eine möglichst große Primzahl sein sollte
• b eine Konstante (im Fall von c = 0 spricht man von multiplikativer Kongruenz)
• c ist das Argument der Modulo Funktion und sollte möglichst einen hohen Wert besitzen, da es die Länge der Zahlenfolge angibt

Dabei ist zu beachten, dass der selbe Seed immer die selbe Zahlenfolge liefert. Um unterschiedliche Folgen zu erhalten ist es notwendig unterschieliche Seeds zu wählen. Oftmals wird der Seed in Abhängigkeit der Tageszeit gewält.

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.

Monte-Carlo-Algorithmen

Algorithmen dieser Art geben mit hoher Wahrscheinlichkeit das korrekte Ergebnis aus. Können sich jedoch gelegentlich irren. Im Falle eines Fehlers liefert der Algorithmus ülicherweise keine Wahrnung. Dies nimmt man jedoch in Kauf um Probleme zu lösen, die sonst nur schwer oder in keiner angemessenen Zeit gelöst werden könnten.

Ein Monte-Carlo-Algorithmus wird p-korrekt genannt, wenn er eine richtige Lösung mit einer Wahrscheinlichkeit nicht kleiner als p liefer. Dabei ist p eine reele Zahl mit 1/2 < p < 1. Desweiteren wird von einem konsistenten Algorithmus gesprochen, wenn er nie zwei verschiedene richtige Lösungen für dasselbe Problem liefert.