AuK/Probabilistische Algorithmen SS11

Wiki-Quelltext dieser Seite.

<language>Java</language>
==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 <math>n</math> als Eingabe erwartet. Die Ausgabe ist eine natürliche Zahl <math>r</math> mit <math>0 \le r < n</math>. Die Transformation in ein abgeschlossenes Intervall <math>[a,b]</math> natürlicher Zahlen lässt sich leicht bewerkstelligen. Wie folgendes Beispiel zeigt.
<code id="4dcbf4b7d024f">
public static int intervall(int a, int b){

Random randomGenerator = new Random();

return (a + randomGenerator.nextInt((b - a) + 1));
          
}
</code>
<run id="4dcbf672ced17">intervall(1, 7);</run>

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.

<math>z_{n} = (a * z_{n-1} + b)</math> <math>mod</math> <math>c</math>

dabei sind 

*<math>a</math> ein Multiplikator, der eine möglichst große Primzahl sein sollte
*<math>b</math> eine Konstante (im Fall von <math>c = 0</math> spricht man von multiplikativer Kongruenz)
*<math>c</math> 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 unterschielicher 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 <math>\pi</math> durch "Zufallsregen".
Dabei werden <math>n</math> 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 <math>r</math>, so ist seine Fläche <math>\pi r^2</math>, wobei die Fläche des Quadrats <math>4r^2</math> ist. Somit ist der durchschnittliche Anteil der Tropfen, die innerhalb des Kreises landen, <math>\pi r^2 / 4r^2 = \pi / 4</math>. Damit kann <math>\pi</math> mit <math>\pi \approx 4 k / n</math> geschätzt werden.


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

<code id="4dc540a538cae">public static float rain(int n){
	
	Random randomGenerator = new Random();
	float a = 0;
	int k = 0;
		
		for(int i = 0; i < n; i++){
			int x = randomGenerator.nextInt(2);
			int y = randomGenerator.nextInt(2);		
			
				if(x*x + y*y <= 1){
					k = k+ 1;					
				}
		}
		return a = 4*k/n;
}</code>


<run id="4dc540a538d1c">rain(100);</run>