AuK/Probabilistische Algorithmen WS13-14
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Java</language>
=Einleitung=
=Zufall=
==Was ist Zufall?==
Auf der Suche nach der Definition des Begriffes Zufall liegt es nahe,
die Wortbedeutung im Duden nachzuschlagen. Hier ist der Zufall als "etwas, was man nicht vorhergesehen hat, was unerwartet geschah" definiert.
Hieraus ergibt sich die Fragestellung, ob das eingetretene Ereignis niemals vorausgesagt werden kann, oder nur in einem speziellen Fall nicht vorhergesehen werden konnte.
Ein Beispiel:
Wir betrachten den Wurf einer Münze, genauer gesagt den Zeitpunkt t, an welchem die Münze wieder beginnt, abwärts zu fallen.
Das Ergebnis des Wurfes erscheint zufällig. Doch für einen begabten Mathematiker mit entsprechender Rechentechnik wäre
es zum Zeitpunkt t durchaus möglich, anhand der Rotation, Umweltbedingungen und weiterer Parameter eine Vorhersage bezüglich des Ergebnis zu treffen.
Er steht allerdings vor dem Problem, dass er das Ergebnis vor dem Auftreffen der Münze berechnen muss (Zeitfrage).
Demnach ist eine Differenzierung nötig, da augenscheinlich sowohl die Perspektive des Betrachters eine Rolle spielt, als auch der Stand der Wissenschaft.
Es existieren Ereignisse, von denen bewiesen werden konnte, dass sie keine kausale Ursache haben. Ein Beispiel hierfür ist der Zerfallszeitpunkt eines (radioaktiven) Atoms.
Außerdem ist es möglich, dass man zwar alle Einflussfaktoren kennt, die ein Ergebnis bestimmen, diese aber weder ändern noch messen kann. Offensichtlich trifft dies bei Zufallsexperimenten zu. Betrachtet man den Wurf eines Würfels kann man sich leicht vorstellen, wovon das Ergebnis abhängt: Der angewendeten Kraft, dem Auftreffwinkel auf dem Untergrund,
das Material des Untergrundes und des Würfels usw. Bevor man dies alles berücksichtigt hat, steht das Ergebnis schon fest. Dies entspricht auch dem Beispiel 1.
Desweiteren kann es sein, dass die Ursache nicht erkennbar ist, aber existiert. Hierbei spricht man auch vom Pseudozufall. Dies findet in Programmiersprachen bei der Benutzung bestimmter Methoden Anwendung. Sie geben eine für den Betrachter ( = Programmierer) zufällige Zahl aus, unterliegen aber einer deterministisch definierten Berechnung.
==Zufallszahlen erzeugen==
Für die Erzeugung von Zufallszahlen gilt es also, die obigen Erkenntnisse zu berücksichtigen. Da man hierbei auf Beschränkungen trifft, haben erzeugte Zufallszahlen eine gewisse Güte.
Es liegt nahe, bewiesene zufällige Ereignisse zu Verwenden, um Zufallszahlen von höchster Güte zu erzeugen. Diese sind allerdings immer physisch und nicht ohne Weiteres anwendbar, theoretisch gesehen ist allerdings die Verwendung beispielsweise des Atomzerfalls bestens geeignet. Ebenfalls physisch, leichter verwendbar und nur mit leicht geringerer Güte sind beispielsweise die Benutzung einer Lottomaschine oder das Werfen von Würfeln. Es ist offensichtlich, das diese Verfahren bei einer großen Zahl an gewünschten Zufallszahlen an (zeitliche) Grenzen stoßen. Um dieses Problem zu lösen, gibt man sich mit Zufallszahlen geringerer Güte zufrieden und arbeitet mit Algorithmen, welche Pseudozufallszahlen erzeugen. Diese bezeichnen wir als Zufallszahlengeneratoren. Dieser Abschnitt erläutert die gebräuchlichste Methode zur Erzeugung von Zufallszahlen sowie deren Verwendung. Desweiteren werden Algorithmen für die Erzeugung spezieller Zufallszahlen vorgestellt und Hinweise zur Implementation gegeben.
===Lineare Kongruenzmethode===
Dies ist die am häufigsten genutzte Methode, um (pseudo)zufällige Zahlen zu erzeugen, gleichfalls ist es eine sehr alte. Derrick H.Lehmer entwickelte diese 1948,
da die bis dahin genutzte Mittquadratmethode (von Neumann) noch nicht optimal war. Lehmers lineare Kongruenzmethode dagegen ist nicht nur sehr einfach zu implementieren
und sehr schnell in der Berechnung, sondern erzeugt auch qualitativ hochwertige Zufallszahlen, wenn sie richtig angewandt wird. Als Grundlage dient die folgende Gleichung.
\[ x_{n+1} = ( a \cdot x_{n} + c) \mod m \]
$c$ bezeichnet man als Inkrement, $a$ als Multiplikator, $x_{0}$ als Seed und $m$ als Modul. Für diese Werte gelten (einführend) die folgenden Bedingungen.
\begin{equation}
m > 0
\end{equation}
\begin{equation}
0 \leq a < m
\end{equation}
\begin{equation}
0 \leq c < m
\end{equation}
Übungsaufgabe: Gegeben sind $a = 4$, $c = 6$, $m = 21$ und $x_{0}=3$. Berechnen Sie die ersten 6 Folgeglieder.
<popup name = "Lösung">
\begin{equation}
x_{0} = 3
\end{equation}
\begin{equation}
x_{1} = ( 4\cdot3+6 ) \mod 21 = 18 \mod 21 = 18
\end{equation}
\begin{equation}
x_{2} = ( 4\cdot18+6 ) \mod 21 = 78 \mod 21 = 15
\end{equation}
\begin{equation}
x_{3} = ( 4\cdot15+6 ) \mod 21 = 66 \mod 21 = 3
\end{equation}
\begin{equation}
x_{4} = ( 4\cdot3+6 ) \mod 21 = 18 \mod 21 = 18
\end{equation}
\begin{equation}
x_{5} = ( 4\cdot18+6 ) \mod 21 = 78 \mod 21 = 15
\end{equation}
\begin{equation}
x_{6} = ( 4\cdot15+6 ) \mod 21 = 66 \mod 21 = 3
\end{equation}
</popup>
Es wird deutlich, dass die Folge periodisch verläuft, was nicht gewollt ist. Dieses Ergebnis ergibt sich aus der Wahl der Parameter, weshalb weitere Eigenschaften festgelegt werden müssen. An das Modul $m$ stellen wir die Anforderung, möglichst groß zu sein. Praktisch bedeutet dies, dass die größte zur Verfügung stehende Integer-Zahl verwendet wird ($(2^{32})-1$).
Beweisen lässt sich diese Bedingung durch die Eigenschaft der Modulorechnung beziehungsweise der ganzzahligen Division mit Rest. Es gilt für $\ a\ =\ b\ mod\ c$, dass es keine Restklasse größer oder gleich $c$ gibt: $\ 0 \leq\ a\ \leq\ c-1$. Trotz großer $m$ kann es zu einer kleinen Periodenlänge kommen, der Zufallszahlengenerator ist also ungünstig. Auch dies ist den Parametern geschuldet. Ein Beispiel sei gegeben mit $a=4$, $c=6$, $x_{0}=3$, $m=100$. Die Folgeglieder sind $x_{1}=18$, $x_{2}=78$, $x_{3}=18$ usw. Weitere Bedingungen sind notwendig,
um eine optimale Folge, d.h. eine mit möglichst großer Periodenlänge, zu erhalten.
\begin{equation}
ggT\ (c,m) = 1
\end{equation}
\begin{equation}
a \mod q = 1\text{, für jeden Elementarteiler (Primfaktor) q von }m
\end{equation}
\begin{equation}
a \mod 4 = 1\text{, falls 4 Teiler von }m
\end{equation}
Ein Beispiel für $m=100$:
* Primfaktorzerlegung für $100$: $2\cdot 2 \cdot 5\cdot 5$
* Bedingung 1 erfüllen: $c$ muss auf $1$, $3$, $7$ oder $9$ enden
* Bedingung 2 erfüllen: $ a\ \mod\ 2\ =\ 1$ und $a\ \mod\ 5\ =\ 1\ \rightarrow \ a \in\ \{1,11,21,31,41,51,61,71,81,91 \}$
* Bedingung 3 erfüllen: $a\ \mod\ 4\ =\ 1\ \rightarrow\ a\ \in\ \{1,21,41,61,81 \}$
Diese Voraussetzungen hat Donald E. Knuth 1997 mathematisch bewiesen und veröffentlicht.
Daraus ergeben sich optimale Parameterkonstellationen, beispielsweise $a=61$ und $c=89$. Probieren Sie es in den Übungen aus!
Weiterhin befasste sich Robert Sedgewick mit dem Einfluss der Parameter auf die Kongruenzmethode und veröffentlichte 2002 Regeln
zur Anwendung dieser. Diese überschneiden sich mit den bereits eingeführten, beispielsweise die Wahl eines großen Moduls oder den
Wert $1$ für das Inkrement. Erweiternd fügte er hinzu, dass der Multiplikator ungefähr eine Zehnerpotenz kleiner sein sollte als das Modul.
Desweiteren existieren Verfahren, welche die Periodenlänge noch weiter verlängern. Diese seien nur erwähnt und können bei Interesse
nachgearbeitet werden: Die sogenannte Tabellenmethode von MacLaren und Marsaglia oder die Schieberegistermethode von Tausworthe.
Die Länge der Periode kann dadurch so stark erhöht werden, dass der Begriff Periodenlänge eigentlich nicht mehr verwendbar ist.
<code id="52725b3b7d702" hidden> void kongruenz(int multiplikator, int inkrement,
int start, int modul, int n) {
int y = start;
if (n == 0) {
return;
} else {
y = (multiplikator * y + inkrement) % modul;
System.out.println(y);
start = y;
kongruenz(multiplikator, inkrement, start, modul, (n - 1));
}
}</code>
<run id="52725b3b7d7e7">kongruenz(61,89,3,100,20)</run>
:'''Wo stehen wir?'''
Wir sind in der Lage, deterministisch Zufallszahlenfolgen mit möglichst großer Periodenlänge zu erzeugen. Anhand des Seeds, also des Startwertes, wählen wir einen Bereich
dieser Periode aus. Dabei kann eine Zahl nicht doppelt vorkommen, da dies eine Wiederholung der Periode bedeuten würde. Desweiteren können wir noch kein Intervall angeben, in dem
die Zufallszahlen liegen sollen.
===Gleitkommazufallszahlen===
Es kann notwendig sein, Zufallszahlen im halboffenen Intervall $[0\dots 1)$ zu erzeugen (Wertebereich: $0\leq x < 1)$.
Sowohl für weitere Zufallszahlengeneratoren als auch für mathematische Methoden, beispielsweise für die näherungsweise Berechnung
von $\pi$ mit der Zufallsregenmethode, benötigt man zufällige Gleitkommazahlen. Der Algorithmus kann leicht unter
Verwendung der linearen Kongruenzmethode angegeben werden, wobei ''randint()'' wie obige ''kongruenz''-Methode funktioniert,
aber eine Zufallszahl nach der anderen zurückgibt.
<code id="5272363fd332e">double randReal() {
start = randInt();
return start / ((double) modul);
}</code>
Dabei wird lediglich die erzeugte Zufallszahl durch das Modul dividiert.
:Hinweis:
Die Variable ''start'' dient dabei zur Zwischenspeicherung der $x_{n}$ Werte. Es werden also Algorithmen mit Gedächtnis genutzt, d.h. sie
können auf bereits berechnete Werte zugreifen. In der Programmiersprache C++ könnte man dies durch eine statische Variable innerhalb der Methode umsetzen,
in Java ist hierfür eine Klassenvariable notwendig.
===Zufallszahlen im Intervall===
Intervallbezogene Zufallszahlen werden wohl am häufigsten genutzt, da sich für die meisten Zufallsexperimente Grenzen angeben lassen.
Beispielsweise kann bei einer Münze keine dritte Seite und bei einem fairen Würfel keine sieben auftreten. Als Hilfsfunktion wird die oben definierte
''randReal()''-Methode verwendet. Desweiteren wird die ''Floor''-Methode benötigt, welche in der Einführungsveranstaltung vorgestellt wurde. Zur Erinnerung:
Die ''Floor''-Methode liefert eine Zahl $max(y) \leq x, y \in$ <math>\mathBB{N}</math>,$x \in$ <math>\mathBB{R}</math>, d.h. ''Floor()'' rundet immer ab.
===Normal verteilte Zufallszahlen===
==Gütetests für Zufallszahlen==
<!--
quelle suchen:radioaktiver zerfall für zufall hoher güte:
http://www.business-on.de/radioaktiver-zerfall-atomen-kernumwandlung-zerfallsreihe-halbwertszeit-_id31049.html
lottoziehung, warum echt zufällig
http://books.google.de/books?id=SVtnGzSmGuUC&pg=PA353&lpg=PA353&dq=kongruenzmethode+lehmer&source=bl&ots=z-A2RHm8CC&sig=Oe81gcijseJ-GvsdmcVb9CQWPGo&hl=de&sa=X&ei=pmtmUuKFBo6zhAfm4ICwBg&sqi=2&ved=0CEIQ6AEwAw#v=onepage&q=kongruenzmethode%20lehmer&f=false
http://www.informatik.hu-berlin.de/forschung/gebiete/algorithmenII/Lehre/ws07/stochastik/skript/FolienStochastik_24.pdf
http://www.math.uni-frankfurt.de/~ismi/hartung/PseudorandomNeuHO.pdf
http://www.google.de/url?sa=t&rct=j&q=&esrc=s&source=web&cd=6&cad=rja&sqi=2&ved=0CEsQFjAF&url=http%3A%2F%2Fwww.mathe.tu-freiberg.de%2Finst%2Fstoch%2FLehre%2FBNCSemDoc02%2FSimulation%2FPseudoZufgen.ppt&ei=pmtmUuKFBo6zhAfm4ICwBg&usg=AFQjCNHcNOUxYsDfjUtWJKOYqzGnoi9j3Q&bvm=bv.55123115,d.bGE
-->
=Numerisch probabilistische Algorithmen=
==Definition==
Numerisch probabilistische Algorithmen haben als Ergebnis eine Näherungslösung mit wählbarer Genauigkeit, in Folge dessen kann der Nutzer selbst durch Wahl seiner Eingaben bestimmen wie genau das gewünschte Ergebnis sein soll.
Weiterhin ist diese Art von Algorithmen nichtdeterministisch, dass bedeutet das bei mehrfacher Ausführung mit dem gleichen Wert unterschiedliche Lösungen zurückgegeben werden können.
<language>Java</language>
<language>Java</language>
==Beispiel: Zufallsregen==
Eine einfache Art der Bestimmung eines Näherungswertes für <math>\pi</math> ist die Methode des sogenannten Zufallregens.<br>
[[Bild:S3damuel_Regen-pi-sw2.png]]<br>
Man werfe dabei eine beliebige Anzahl an "Regentropfen" auf das oben abgebildete Quadrat mit Innenkreis, wobei der Radius des Innenkreises den Wert 1 besitzt. Um <math>\pi</math> zu bestimmen, werden zwei Arten von aufkommenden Tropfen gezählt: die Tropfen innerhalb des Kreises <math>T_{Kreis}</math> und die Tropfen innerhalb des Quadrates <math>T_{Quadrat}</math>. Um die Genauigkeit der Berechnung zu erhöhen, betrachtet man nur die Tropfen im ersten Quadranten der Quadrates. Damit ein Punkt innerhalb des Kreises liegt gelten für ihn folgende Bestimmungen: $x^2+y^2 \le 1$, wobei x,y reelle Zahlen im Bereich $0 < x,y \le 1$.<br>
Die Annäherung an $\pi$ ergibt sich dann aus folgenden Überlegungen:<br><math>\frac{A_{Kreis}}{A_{Quadrat}} = \frac{\pi r^2}{4r^2} \approx \frac{T_{Kreis}}{T_{Quadrat}}</math><br>
Da zunächst nur das Auftreffen im ersten Quadranten betrachtet wurde, ergibt sich nun nach folgender Operation der Näherungswert für $\pi$: <br>
<math>\pi = 4 * \frac{T_{Kreis}}{T_{Kreis}+T_{Quadrat}}</math>.<br>
Es wurde ja definiert, dass numerisch probabilistische Algorithmen eine wählbare Genauigkeit besitzen, in diesem Beispiel kann die Genauigkeit durch steigende Tropfenanzahl verbessert werden.
<code id="5274c53055071">double rain2(int n){
int k = 0;
for(int i = 0; i < n; i++){
double x = Math.random();
double y = Math.random();
if(x*x + y*y <= 1){
k = k+ 1;
}
}
double pi = new Double (4) *k/n;
return pi;
}</code>
<run id="5274c53055112">rain2(50);</run>
<code id="5274c2ce286dc"> boolean test(){
if(1==1){return true;}
else{return false;}
}</code>
<run id="5274c2ce28778">test();</run>
<code id="5272363fd33cb"> void rain(int anzahl) {
double roundpi = 0;
// Random a = new Random(System.currentTimeMillis());
double t_k = 0;
double t_q = 0;
for (int i = 0; i < anzahl; i++) {
double x, y;
x=Math.random();
y=Math.random();
// x = a.nextDouble();
// y = a.nextDouble();
if ((x * x + y * y <= 1)) {
t_k = t_k + 1;
} else {
t_q = t_q + 1;
}
}
// System.out.println(t_k + "kreis");
// System.out.println(t_q + "quadrat");
roundpi = 4*(t_k / anzahl);
System.Out.Println( roundpi);
}</code>
<run id="5272363fd3530">rain(50);</run>
=Las-Vegas-Algorithmen=
Las-Vegas-Algorithmen, sind Algorithmen, welche niemals ein falsches Ergebnis liefern, jedoch kann es vorkommen, dass sie kein Ergebnis liefern. Gelangt man in eine solche "Sackgasse", kann der Aufruf mit neuer Zufallszahl jedoch ein korrektes Ergebnis liefern. Mit jedem nicht vorhanden Ergebnis steigt die Chance auf ein richtiges.<br>
==Aufwandsanalyse für Las-Vegas-Algorithmen==
Man nehme eine einstellige Prozedur LV(x), welche der Aufruf eines beliebigen Las-Vegas-Algorithmus ist. Die Ausgabe dieser Prozedur ist ein Wertepaar aus y (dem eigentlichen, falls vorhandenem, Ergebnis) und dem Wahrheitswert Erfolg. Erfolg nimmt je nachdem ob ein Ergebnis zurückgegeben werden kann den Wert true oder false an.
==Sherwood-Algorithmen==
=Monte-Carlo-Algorithmen=
Monte-Carlo-Algorithmen sind ebenso wie numerisch probabilistische Algorithmen nichtdeterministisch, das bedeutet, bei mehrfachen Aufruf mit gleichen Parametern können unterschiedliche Ergebnisse auftreten. Das ist möglich, da diese Art von Algorithmen zwar oft das richtige Ergebnis ausgibt, selten jedoch auch Fehlern auftreten können. Diese Fehler sind keine Näherungswerte, sondern komplett falsch. Da beim Aufruf im Allgemeinen jedoch keine Lösung vorhanden ist, kann man auch nicht beurteilen ob das Ergebnis richtig ist oder sich der Algorithmus geirrt hat. Man kann nicht davon ausgehen, dass der Algorithmus bei den meisten Aufrufen ein richtiges Ergebnis liefert.
In den folgenden Abschnitten sollen einige Beispiele für diese Algorithmenart behandelt werden.
==Äquivalenz zweier Multimengen==
==Primzahltest nach Fermat==
Auf Grundlage des "kleinen Satzes von Fermat" gelingt es einen Algorithmus zu schaffen, der feststellt ob eine Zahl zusammengesetzt ist oder sie wahrscheinlich eine Primzahl ist.
Theoretische Grunlage (Euler):<br>
Für alle natürlichen Zahlen $n$ und $a$ mit $n \ge 2$ und $1 \le a \le n$, wobei $ggT(a,n) = 1$ (teilerfremd), gilt $a^{\phi (n)} \equiv 1 \mod n$. Speziell für Primzahlen gilt: $\phi(n) = n-1$ laut Definition.
Wenn $n$ eine Primzahl ist, dann gilt für alle Zahlen $a$ (mit $1 \leq a \leq n-1)\ \ a^{n-1} \equiv 1 \mod n$ (Kleiner Satz von Fermat)<br>Dabei muss die Bedingung gelten: $ggT(a,n)= 1$
===Verlauf des Primzahltest===
Der Test wird durchgeführt für eine natürliche Zahl $n$, als Ergebnis erhält man entweder die Aussage, dass die Zahl zusammengesetzt ist oder das keine Aussage über die Zahl getroffen werden kann. Es wird eine Basis $a$ gewählt, für welche die Bedingung $1 < a < n$ gilt und für die beiden Zahlen getestet ob diese teilerfremd sind.
Nun können drei Fälle eintreten:
* $ggT(a,n) \neq 1$ $\rightarrow$ Zahl zusammengesetzt
* $a^{n-1} \not \equiv 1 \mod n$ $\rightarrow$ Zahl zusammengesetzt
* $\rightarrow$ keine Aussage
Wenn der Test mit mehreren verschiedenen Basen ausgeführt wurde und es kam immer zum Ergebnis, dass keine Aussage möglich ist, so kann man feststellen, das die Zahl vermutlich eine Primzahl ist.
===Pseudoprimzahlen - Carmichelzahlen===
Warum ist keine Aussage möglich wenn keine der ersten beiden Bedingungen zutrifft?<br>
Man kann durch den Test mit einer Basis keine endgültige Entscheidung treffen, da es Basen gibt, für welche beide Bedingungen nicht gültig sind, obwohl die Zahl keine Primzahl ist, so dass man vom Programm das Ergebnis erhalten würde, dass keine Aussage möglich sei.
<br>Ein Beispiel dafür wäre die Zahl 561.
Es gilt:
*$561 = 11 \cdot 51$ jedoch auch
*$ggT(2,561)=1$ und $2^{560} \equiv 1 \mod 561$
für die Untersuchung mit der Basis 2.
Bis zum Wert 2000 gibt es 303 echte Primzahlen, jedoch nur 7 Pseudoprimzahlen nach dem Test von Fermat.
Zahlen dieser Art, welche für eine bestimmte Basis den Test erfüllen, nennt man ''fermatische Pseudoprimzahlen''.<br>
Es gibt jedoch auch Zahlen die den Test mit jeder gewählten Basis bestehen und dennoch keine Primzahlen sind, diese nennt man ''Carmichelzahlen''. Von ihnen gibt es bis zum Wert 2000 gerade einmal 3.
<!-- http://de.wikipedia.org/wiki/Fermatscher_Primzahltest -->
==Primzahltest nach Solovay und Strassen==
Durch den Primzahltest von Solovay und Strassen kann ein weiterer Algorithmus geschrieben werden, der bestimmt ob eine Zahl $n$ prim ist, dazu wird die sogenannte Jacobifunktion genutzt.
===Jacobi-Funktion===
=Probabilistische Analyse=
==Indikatorfunktion==
=Literaturverzeichnis=
* Wagenknecht, Christian: Algorithmen und Komplexität, Fachbuchverlag Leipzig, 2003
* Pomberger, Gustav; Dobler, Heinz: Algorithmen und Datenstrukturen, Pearson Studium, 2008
* Ziegenbalg, Jochen: Algorithmen, Spektrum Akademischer Verlag, 1996
* Mathar, Rudolph; Pfeifer, Dietmar: Stochstik für Informatiker, B.G. Teubner Verlag, 1990
* Wanka, Rolf: Approximationsalgorithmen, B.G. Teubner Verlag, 2006
* Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford: Algorithmen, eine Einführung,Oldenbourg Verlag, 2007
* Rempe, Lasse; Waldecker, Rebecca: Primzahltests für Einsteiger: Zahlentheorie – Algorithmik – Kryptographie, Vieweg + Teubner Verlag, 2009
* Abelson, Harold; Sussman, Jay Gerald; Sussman, Julie: Struktur und Interpretation von Computerprogrammen, Springer Verlag, 1998
* Gumm, Heinz; Sommer, Manfred: Einführung in die Informatik, Oldenbourg Verlag, 2006