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.

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.

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 \pi ist die Methode des sogenannten Zufallregens.

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 \pi zu bestimmen, werden zwei Arten von aufkommenden Tropfen gezählt: die Tropfen innerhalb des Kreises T_{Kreis} und die Tropfen innerhalb des Quadrates T_{Quadrat}. 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.
Die Annäherung an \pi ergibt sich dann aus folgenden Überlegungen:
\frac{A_{Kreis}}{A_{Quadrat}} = \frac{\pi r^2}{4r^2} \approx \frac{T_{Kreis}}{T_{Quadrat}}
Da zunächst nur das Auftreffen im ersten Quadranten betrachtet wurde, ergibt sich nun nach folgender Operation der Näherungswert für \pi:
\pi = 4 * \frac{T_{Kreis}}{T_{Kreis}+T_{Quadrat}}.
Es wurde ja definiert, dass numerisch probabilistische Algorithmen eine wählbare Genauigkeit besitzen, in diesem Beispiel kann die Genauigkeit durch steigende Tropfenanzahl verbessert werden.

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.

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):
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)
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? Man kann nicht durch den Test mit einer Basis eine endgültige Entscheidung treffen, da es Basen gibt, für welche beide Bedingungen nicht gültig sind, obwohl die Zahl keine Primzahl ist.
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.

Primzahltest nach Solovay und Strassen

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
• Gumm, Heinz; Sommer, Manfred: Einführung in die Informatik, Oldenbourg Verlag, 2006