AuK/Probabilistische Algorithmen WS13-14
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
=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.
===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 \}$
Daraus ergeben sich optimale Parameterkonstellationen, beispielsweise $a=61$ und $c=89$. Probieren Sie es in den Übungen aus!
<!--
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.
==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> 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 = 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>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=
==Primzahltest nach Fermat==
Auf Grundlage des "kleinen Satzes von Fermat" gelingt es einen Algorithmus zu schaffen, der eine Rechenzeit von $\mathcal O(\log n)$ besitzt.
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$
* $a^{n-1} \not \equiv 1 \mod n$
*
==Primzahltest nach Solovay und Strassen==
=Probabilistische Analyse=
==Indikatorfunktion==
=Literaturverzeichnis=
* Wagenknecht, Christian: Algorithmen und Komplexität, Fachbuchverlag Leipzig, 2003
* 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
* Gumm, Heinz; Sommer, Manfred: Einführung in die Informatik, Oldenbourg Verlag, 2006