AuK/Probabilistische Algorithmen SS11

Wiki-Quelltext dieser Seite.

<language>Java</language>
==Einleitung==

Probabilistische Algorithmen werden auch randomisierte oder stochastische Algorithmen genannt. Das Ergebnis dieser Art von Algorithmen ist vom Zufall abhängig. Sie bringen oft eine Effiziensverbesserung mit sich, da Entscheidungsfragen zufällig beantwortet werden, bei denen die Zeit zur Berechnung des korrekten Resultates untragbar lang wäre. Probabilistische Algorithmen können sich, mehrfach auf ein und dasselbe Problem angewandt, unterschiedlich verhalten. Die Ausführungszeiten und die Ergebnisse können teilweise deutlich voneinander abweichen.

Um probabilistische Algorithmen zu erstellen werden Zufallszahlen benötigt. Diese werden mit Hilfe von Generatoren erstellt.

==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 <math>n</math> als Argument 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 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 <math>\pi</math> durch "Zufallsregen".[[Bild:Pi_Berechnung_mit_Zufallsregen.jpg|250px|thumb|right|Bestimmung der Zahl <math>\pi</math> duch "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>

Ein weiteres bekanntes Beispiel für diese Klasse von Algorithmen, die "Zufallsregen" verwenden ist die [http://de.wikipedia.org/wiki/Numerische_Integration numerische Integration].

==Las Vegas Algorithmus==

Grundlage:



Ein solcher  Algorithmus (randomisierter Algorithmus ) folgt dem einfachen Prinzip immer ein  richtiges Ergebnis auszugeben. So erklärt sich der Name des Las Vegas Algorithmus aus der Tatsache das Casinos immer gewinnen (bezogen auf ein korrektes Ergebnis). Es kann  jedoch der Fall eintreten das die Zufallssteuerungen in Sackgassen(nicht zulässige Ergebnissen ) landen. In diesen Fall gibt es kein Ergebnis. Dies kann aber durch wiederholen des Algorithmus mit einer neuen Zufallszahl auf ein richtiges Ergebnis kommen. Das Bedeutet es ist extrem Unwahrscheinlich
das nach einer bestimmten Anzahl von Versuchen kein Ergebnis Eintritt.



Analyse des Aufwands:



Im Fall der Las Vegas Algorithmen  muss man von der Möglichkeit ausgehen das eine Anzahl n von versuchen benötigt wird um ein richtiges Ergebnis auszugeben. Um nun den Zeitaufwand t(x) zu berechnen ,  brach man die Variablen <math>success(x)</math> im Fall des erfolgreichen Findens eines Ausgabewertes und <math>failure(x)</math> im Fall keines Erfolgreichen Ergebnisses. Des weiteren muss noch die Zeit eingerechnet werden ,die gebraucht wird  um aus einer „Sackgasse“ wieder raus zukommen ,bezeichnet mit der Variable <math>p(x)</math> . Man geht bei <math>p(x)</math> von <math>0 < p(x) < 1</math> aus.

Gleichung:

<math>t(x)=p(x) \cdot success(x)+(1-p(x)) \cdot (failure(x)+t(x))</math>



<math>t(x) = success(x) + (1- p(x)) / p(x) * failure(x)</math>


<math>t(x)=success(x)+ \left( \frac{1}{p(x)} - 1 \right) \cdot failure(x)</math>

==Monte-Carlo-Algorithmen==

Algorithmen dieser Art geben mit hoher Wahrscheinlichkeit das korrekte Ergebnis aus. Können sich jedoch gelegentlich irren. Irren bedeutet hier das Ergebnis ist falsch und nicht "knapp daneben". Im Falle eines Fehlers liefert der Algorithmus ülicherweise keine Warnung. 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 <math>p</math> liefer. Dabei ist <math>p</math> eine reele Zahl mit  <math>1/2 < p < 1</math>. Desweiteren wird von einem ''konsistenten'' Algorithmus gesprochen, wenn er nie zwei verschiedene richtige Lösungen für dasselbe Problem liefert.

Es gibt auch Monte-Carlo-Algorithmen, welche nicht nur den zu lösenden Fall als Argument akzeptieren, sondern auch eine obere Schranke für die zulässige Wahrscheinlichkeit eines Fehlers. Die benötigte Rechenzeit lässt sich dann als Funktion der Größe des zu bearbeitenden Falls und des Kehrwerts der zulässigen Fehlerwahrscheinlichkeit ausdrücken.

Um die Erfolgswahrscheinlichkeit eines Monte-Carlo-Algorithmuses heraufzusetzen muss er nur mehrmals ausgeführt werden und anschließend das häufigste Ergebnis ausgewählt werden.




===Äquivalenz zweier Multimengen===

Ein Beispiel für einen Monte-Carlo-Algorithmus ist der Test zweier Multimengen auf Äquivalenz. In Multimengen können mehrere gleiche Elemente enthalten sein. Im Beispiel werden Multimengen betrachtet, deren Elemente natürliche Zahlen aus <math>[1, k]</math> (mit <math>k \in N</math>) sind.

zum Beispiel:

* <math>M_1 = \lbrace 2,3,4,2,2,3 \rbrace </math>
* <math>M_2 = \lbrace 3,4,2,3,2,2 \rbrace </math>
* <math>M_3 = \lbrace 3,4,2,3,3,2 \rbrace </math>


Der klassische Weg eine Entscheidung über die Äquivalenz der Multimengen zu treffen, wäre sie zu sortieren und anschließend elementweise zu vergleichen. Dies kostet jedoch im Mittel <math>O~(n~log~n)</math>. Mit einem probabilistischen Algorithmus ist man in der Lage das Problem in <math>\theta~(n)</math> zu lösen.


Dazu wird der Multimenge 
<math>M_1~=~(x_1,x_2,~...~,x_n)</math> ein Polynom <math>p_m_1</math> mit <math>p_m_1(x)~=~(x~-~x_1)(x~-~x_2)~...~(x~-~x_n)</math> und

der Multimenge <math>M_2~=~(y_1,y_2,~...~,y_n)</math> ein Polynom <math>p_m_2</math> mit <math>p_m_2(x)~=~(x~-~y_1)(x~-~y_2)~...~(x~-~y_n)</math>
zugeordnet.

Die (evtl. mehrfachen) Nullstellen von <math>p_m_1~(x)</math> heißen <math>x_1,x_2,~...~,x_n</math> und die von <math>p_m_2~(x)</math> sind <math>y_1,y_2,~...~,y_n</math>. 
Diese Darstellung ist für jede ganzrationale Funktion eindeutig. Demzufolge gilt <math>M_1~\equiv~M_2 </math> genau dann wenn <math>p_m_1~(x)~=~p_m_2(x)</math>.

Mit folgendem Code kann der Polynomwert einer Multimenge bestimmt werden.
<code id="4dd52c5139926">
int[] m1  = {2,3,4,2,2,3};
int[] m2  = {3,4,2,3,2,2};
int[] m3  = {3,4,2,3,3,2};

static int polynomWert(int[] menge, int x){
int i = menge.length;
int wert = 1;

if(i == 0)
return 1;
else
for(i = menge.length; i > 0; i--){
wert = wert * (x - menge[i-1]);
}
return wert;
}

</code>
<run id="4dd52c513999d">System.out.println("Das Polynom hat den Wert " + polynomWert(m1,9));</run>


Berechnet und vergleicht man nun die Polynomwerte zweier Multimengen mit einer beliebiegen Testzahl <math>x'</math> und erhält verschiedene Werte für <math>p_m_1~(x')</math> und <math>p_m_1~(x')</math> so weiß man definitiv das <math>M_1~\not\equiv~M_2 </math>.

Um das Gegenteil zu beweisen wählt man zum Berechnen das Polynomwertes ein zufälliges <math>x</math>. Weiterhin wiederholt man den Test bei Erfolg mehrere Male. Somit ist es möglich, dass richtige Ergebnis mit hoher Wahrscheinlichkeit zu erhalten.


<code id="4dd7c4f022df0">
java.util.Random random = new java.util.Random();

boolean aequiv (int r, int[] a, int[] b, int wdh){
int x = random.nextInt(r);

if(polynomWert(a,x) == polynomWert(b,x)){
if(wdh >= 0){
this.aequiv (r, a, b, wdh - 1);
}
return true;
}
else {return false;}
}
</code>
<run id="4dd7c4f022ec1">System.out.println(aequiv (100, m1, m2, 10))</run>

==Quellen==

* Christian Wagenknecht: ''Algorithmen und Komplexität'', Fachbuchverlag Leipzig, 2003,
* Brassard, Gilles; Bratley, Paul: ''Algorithmik: Theorie und Praxis'', Attenkirchen: Wolfram, 1993