Einführung in probalistische Algorithmen

Wiki-Quelltext dieser Seite.

<language>Java</language>
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.

<code>
/*
switch((int)rand()*3){
case 0: return 1;
case 1: return 3;
case 2: return 7;
default: return -1;
}
*/
</code>

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. Außerdem gibt es Sherwood-Algorithmen, welche einen Spezialfall von Las-Vegas-Algorithmen darstellen, aber keine Sackgassen besitzen. Diese Sherwood-Algorithmen arbeiten im mittleren Fall bedeutend effizienter, als im schlechtesten. Durch ein Zufallselement wird dann dafür gesorgt, dass sich alle Fälle ähnlich dem mittleren Fall verhalten, wordurch im Mittel die Effizienz gesteigert wird. Dies nennt man den Robin-Hood-Effekt.

===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

# einen effizient in Polynomzeit arbeitenden probalistischen Algorithmus,
# keinen bekannten deterministischen, in Polynomialzeit arbeitenden Algorithmus und
# 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 '''P'''olynomialer Zeit oder '''n'''ichtdeterministisch in '''P'''olynomialer Zeit gelößt werden kann)

Für Probleme, bei denen selbst der beste bekannte, deterministisch arbeitende Algorithmus einen hohen polynomialen Aufwand hat, lassen sich oft efizientere probalistische Algorithmen finden. 


Als Beispiel betrachten wir uns hier die Berechnung der Kreiszahl Pi:

Als Formel für eine numerische Näherung könnte man zum Beispiel der Formel des Inders Srinivasa Ramanujan aus dem Jahr 1914 nutzen:

<math>\frac{1}{\pi}=\frac{\sqrt{8}}{9801}\cdot \sum_{n=0}^{\infty}\frac{(4n)!\cdot(1103+26390n)}{(n!)^4\cdot396^{4n}}</math>

Alternativ ist es möglich, einen Kreis durch ein Quadrat zu Zeichnen, in dieses zufällig gewählte Punkte zu werfen, und über deren Verteilungsverhältnis Pi zu ermitteln.

[[Bild:Pi_statistisch.png]]

Ein Algorithmus, in dem dies Implementiert ist, findet sich hier:

<code>public static double berechne_pi(int tropfenzahl) {
  double pi = 0;
  int innerhalb = 0;
  int gesamt = tropfenzahl;
 
  while (tropfenzahl > 0) { // generiere Tropfen und addiere je nach Zugehörigkeit
    double dotx = Math.random();
    double doty = Math.random();
 
    if (dotx*dotx + doty*doty <= 1) { // Punkt liegt innerhalb des Kreises
      innerhalb++;
    } else { // Punkt liegt außerhalb des Kreises
    }
    tropfenzahl--;
  }
  pi = 4*(double)innerhalb/gesamt;
  return pi;
}
</code>
<run>
berechne_pi(100);
</run>

===Probalistische Algorithmen in kritischen Anwendungen===
[[Monte-Carlo-Algorithmen]] liefern ein Ergebnis, welches nicht zwangsläufig korrekt sein muss. Es gibt Menschen, die daraus Schlussfolgern, dass probalistische Algorithmen für etwa sicherheitskritische Anwendungen nicht geeignet sind. Dies muss so aber nicht stimmen, da die Wahrscheinlichkeit eines Fehlers signifikant gesenkt werden kann, in dem man den Algorithmus mehrmals mit dem gleichen Eingabeparameter laufen lässt. Unter Umständen ist es auch möglich, für einen Monte-Carlo-Algorithmus einen Las-Vegas-Algorithmus anzugeben. In der Regel braucht es dazu aber einen Verifizierer für die Lösung, also einen Algorithmus, der zu einem Lösungsvorschlag testen kann, ob der Vorschlag korrekt ist. Man erhält dann einen Las-Vegas-Algorithmus, in dem man den gegebenen Monte-Carlo-Algoroithmus ausführt, anschließend die Lösung mit dem Verifizierer überprüft, und dieses Verfahren solange wiederholt, bis eine korrekte Lösung berechnet wurde. Bei dieser Methode ist zwar die Rechenzeit nicht nach oben beschränkt, man kann aber die Anzahl der Iterationen grob nach oben abschätzen.

Umgekehrt lässt sich aus jedem Las-Vegas-Algorithmus ein Monte-Carlo-Algorithmus machen, in dem man einen obere Schranke für die Rechenzeit festlegt und, falls diese Überschritten wurde, eine beliebige Ausgabe liefert (etwa "?"), welche dann als falsche Ausgabe interpretiert wird.

===Formalisierung von probalistischen Algorithmen===
Um eine formale Notation für probalistische Algorithmen zu erhalten, kann man eine deterministische Turingmaschine ''M'' mit einem zusätzlichen unendlichen Band nehmen. Dieses zusätzliche Band kann nur gelesen werden und enthält eine unendliche, zufällige Sequenz von "0" und "1". Die Maschine ''M'' schiebt dieses Band nur von links nach rechts. 

Jeder randomisierter Algorithmus ''A'' zusammen mit einem festen Eingangswert ''x'' stellt also ein Zufallsexperiment dar.

Für jeden probalistischen Algorithmus können wir die Komplexität prüfen, in dem wir die Anzahl der Zufallsbits mit betrachten. Wenn die Funktion 

<math>Random_{A}(n)</math>

das Höchstmaß an Zufallszahlen in allen Durchläufen von ''A'' für ''x'' ist, dann gilt

<math>Random_{A}(n) = max\left\{Random_A(x) | n \in \mathbb{N}\right\}</math>



Dieses Maß ist aus folgenden Gründen sehr wichtig:

+ Es kostet viel Arbeit, um eine Prozedur zu schreiben, die das gleiche Verhalten hat, wie ein probalistischer Algorithmus. Und diese Arbeit wächst mit Länge der Prozedur an. 

+ Wenn <math>Random_{A}(n)</math> von ''A'' an eine logarithmische Funktion gebunden ist, dann konvergiert die Anzahl der Durchläufe für einen festen Eingangswert ''x'' gegen <math>2^{Random_{A}(n)}</math>.

Das heißt, dass ''A'' deterministisch Simuliert werden kann, in dem man jeden Durchlauf nacheinander simuliert. Wenn ''A'' das Problem in Polynomzeit löst, benötigt auch die deterministische Simulation von ''A'' nur Polynomzeit. Dies wird als [[Derandomisierung]] bezeichnet.

Für jeden Durchlauf ''C'' von ''A'' mit ''x'' kann eine Wahrscheinlichkeit zur Lösung von ''x'' angegeben werden. Diese ergibt sich aus der Multiplikation aller Wahrscheinlichkeiten der Zufallsentscheidungen, welche in ''C'' getroffen wurden. Diese bezeichnen wir im Folgenden als <math>Prob_{A,x}(C)</math>. 
Ein probalistischer Algorithmus ''A'' kann für den gleichen Eingabewert ''x'' unterschiedliche Resultate liefern. Die Wahrscheinlichkeit, dass ''A'' für ''x'' das korrekte Ergebnis ''y'' liefert, also <math>Prob(A(x) = y)</math> ist die Summe aller <math>Prob_{A,x}(C)</math>, bei denen ''C'' 'y'' ausgibt. Das Ziel beim konstruieren eines probalistischen Algorithmus ist es also, ein möglichst hohes <math>Prob(A(x) = y)</math> zu erhalten.

Verschiedene Durchläufe von ''A'' mit ''x'' können aber auch unterschiedliche Rechenzeiten (oder Kosten) haben. Wenn <math>Time(C)^{10}</math> die Komplexität des Durchlaufs ''C'' von ''A'' mit ''x'' ist, dann ist die erwartete Zeitkomplexität von ''A'' mit ''x''

<math>ExpTime_A(x)=E\left[Time\right] = \sum Prob_{A,x}(C)\cdot Time(C)</math>

Wobei die Summe von allen Durchläufen ''C'' von ''A'' mit ''x'' gebildet wird.
Man könnte die Exp-Time-Funktion auch als Funktion über den Eingabewert definieren, in dem man

<math>ExpTime_A(n) = max\left\{ExpTime_A(x) \right\} </math> berechnet.

Oft ist es jedoch nicht ganz einfach, <math>ExpTime_A(n) </math> für einen bestimmten Algorithmus ''A'' anzugeben. Um mit dieser 
Schwierigkeit aufzuräumen, wird nur der worst case betrachtet. 

Wenn also <math>Time_A(x) = max\left\{Time(C) \right\}</math> wobei ''C'' ein Durchlauf von ''A'' mit ''x'' ist, dann ist die worst-case-Zeitkomplexität von ''A''

<math>Time_A(n) = max\left\{Time_A(X) \right\} </math>.

Leider ist diese Definition in manchen Fällen etwas irrführend, weil es sein kann, dass in dem probalistischen Algorithmus endlos läuft. Bei einem deterministischen Algorithmus sind endlose Rechenzeiten verboten, da der Computer in einer Endlosschleife feststecken würde, und das Problem nie lösen wird. Bei probalistischen Algorithmen ist es durchaus möglich, dass ein Algorithmus endlos rechnet, da dies auch ohne Endlosschleife möglich ist. Bei jeden neuen Durchlauf werden neue Zufallsparameter gewählt, und der Algorithmus könnte terminieren. Eine Möglichkeit, um die Rechenzeit einzuschränken, ist, wie schon beschrieben, eine Schranke in den Algorithmus einzubauen, welche immer ein falsches Ergebnis liefert, wenn der Algorithmus bis zu einer bestimmten Zeit nicht terminiert ist.