Inhaltsverzeichnis

1  Einführung  4

2  (Pseudo-)Zufallszahlen und Zufallszahlengeneratoren  5

3  Numerische Probabilistische Algorithmen  7

4  Las Vegas-Algorithmen  9

5  Monte-Carlo-Algorithmen  12

5.1  Äquivalenz zweier Multimengen  12

5.1.1  Analyse des Problems  12

5.1.2  Implementierung  14

5.2  Primzahltest nach Fermat  16

5.2.1  Analyse des Problems  16

5.2.2  Implementierung  18

5.3  Primzahltest von Solovay und Strassen  20

5.3.1  Analyse des Problems  21

5.3.2  Implementierung  22

6  Literaturverzeichnis  24

7  Aufgabenteilung  25

3

1 Einführung

Es ist mehrfach festgestellt worden, dass schnellere Rechner nur einen geringen Einuss auf die Aufwandsordnung haben, d.h. sie leisten nur einen begrenzten Beitrag zur schnelleren/ezienteren Verarbeitung eines Verfahrens. Die einzige Lösung besteht in dem Suchen und Finden immer besserer und schnellerer Algorithmen zur Lösung konkreter Probleme. Eine Kategorie von immer besseren Berechnungsverfahren sind die Probabilistischen Algorithmen. Diese Algorithmen verwenden Zufallsbits um ihren Ablauf zu steuern, was soviel bedeutet dass sie im Laufe der Berechnung, also während der Laufzeit des Algorithmuses, Zufallszahlen benutzen.

Diese Algorithmen haben mehrere Vorteile gegenüber ihren deterministischen Vettern. Sie sind in den meisten Fällen ˆ schneller (bezüglich der Laufzeit) ˆ benötigen weniger Speicher ˆ sind einfacher zu verstehen und damit... ˆ ...einfacher zu implementieren

als die schnellsten deterministischen Algorithmen für das selbe Problem. Der Nachteil probabilistischer Algorithmen ist, dass sie zufällig auch worst-case-Entscheidungen treen können. Ebenfalls nachteilig ist die Tatsache, dass diese Algorithmen falsche Aussagen produzieren (Monte Carlo-Algorithmen) können oder erst gar nicht terminieren, weil eine ungünstige Zufallszahlenauswahl so getroen wurde, dass die Berechnung in eine Sackgasse führt (Las Vegas-Algorithmus).

Der Zufall spielt eine bedeutende Rolle in fast allen Bereichen der Informatik. Wichtige Gebiete, wie z.B. die algorithmische Zahlentheorie und die Kryptographie sind in ihrer heutigen Form ohne probabilistische Algorithmen gar nicht denkbar.

Auch für Simulationen, Stichproben und Tests werden probabilistische Algorithmen bevorzugt verwendet. Es gibt beispielsweise mehrere Primzahltests, deren Verfahren probabilistisch sind.

4

2 (Pseudo-)Zufallszahlen und

Zufallszahlengeneratoren

Wie schon erwähnt nutzen probabilistische Algorithmen während der Laufzeit Zufallszahlen für die Lösung verschiedener Probleme. Diese müssen jedoch erst einmal bereitgestellt werden, wofür es sogenannte Zufallszahlengeneratoren gibt.

Alle höheren Programmiersprachen besitzen Sprachelemente zur Erzeugung von Zufallszahlen, also Zufallszahlengeneratoren.In Scheme gibt es dazu das Sprachelement random, welches eine natürliche Zahl n als Eingabe erwartetund nach der Terminierung eine (vermeintlich) zufällig gewählte Zahl zwischen 0 und (n-1) ausgibt.Eine Prozedur zuf

(define zuf

(lambda (a b) (+ a (random(+ (- b a) 1)))))

liefert eine Zufallszahl zwischen a und b.

Natürlich steckt hinter Algorithmen wie random eine deterministische Verfahrensweise, weshalb von solchen Zufallszahlengeneratoren erzeugte Zufallszahlen als Pseudozufallszahlen bezeichnet werden, weil sie nun einmal nicht zufällig, sondern nach einem ganz bestimmten Schema, also Algorithmus, erzeugt werden.

Der bekannteste Algorithmus zur Erzeugung von (Pseudo-)Zufallszahlen ist die Kongruenzmethode, welche 1948 von dem Mathematiker LEHMER enwickelt wurde. Sie erzeugt eine sich wiederholende Folge von (vermeintlichen) Zufallszahlen. Ausgehend von einer Startzahl, dem Seed, (auf dt. Samen, Keim) wird die rekursive Vorschrift z n = (a ∗ z n−1 + b) mod c

für geeignete a, b, und c befolgt. Für a=28, b=17, c=6 und dem Seed(z 0 )=3 entsteht die Folge (5,1,3), welche sich nach jedem Durchlauf wiederholt.

Diese Zahlen haben natürlich nur Beispielcharakter. Erstens sind die gewählten Zahlen und damit die erzeugte Folge viel zu klein, zweitens wird die Folge immer mit dem gleichen Seed aufgerufen, wodurch zwangsläug immer die selbe Folge entsteht.

5

2 (Pseudo-)Zufallszahlen und Zufallszahlengeneratoren

Will man einen wirklich guten Zufallszahlengenerator mit Hilfe der Kongruenzmethode erzeugen, so muss das Seed bei jedem Aufruf der Prozedur/Methode neu gewählt werden, wodurch immer, d.h. bei jedem erneuten Aufruf, eine neue Folge entsteht. Eine Möglichkeit des Erstellen immer anderer Seed-Werte ist das Abfragen der Zeit, welche in Java in Millisekunden zurückgegeben wird.

public static void kon() {

Date d = new java.util.Date(); //Erstellen eines Objektes vom Typ Date long seed = d.getTime(); //aktuelle Systemzeit wird dem Seed zugewiesen

long a = 34543; //Beispielwerte long b = 56789; long c = 556;

for(int i=0; i<=10;i++) { //Darstellen der ersten 10 Werte einer //(Pseudo-)Zufallszahlenfolge

long zn = (a * seed + b) % c ; //Verwenden der Kongruenzmethode als seed = zn; //(Pseudo-)Zufallszahlengenerator

System.out.println(zn); } }

In Scheme verwendet man das Sprachelement real-time, um immer neue Seed-Werte generieren zu können.

(define seed1 0) ;Erzeugen des Seed

(define randomize ;Systemzeit wird Seed zugewiesen. (lambda () (set! seed1 (real-time))))

(define zn2 ;Kongruenzmethode in Scheme (lambda (a b c )

(let ((seed2 (modulo (+ (* a seed1) b) c))) (set! seed1 seed2) seed2)))

6

3 Numerische Probabilistische

Algorithmen

Numerische Probabilistische Algorithmen liefern für ein Problem eine Nährungslösung. Allgemein gesehen kann man sich diese Art von Algorithmen als nichtdeterministische Simulation vorstellen, d.h. es ist nicht gegeben, dass bei wiederholter Ausführung auch exakt die gleichen Resultate geliefert werden. Vorteil dieser Algorithmen ist die wähl- und veränderbare Genauigkeit. Ein bekanntes Beispiel für diese Algorithmen ist der sogenannte Zufallsregen. Man stelle sich ein Quadrat vor, in dem sich ein Kreis bendet. Dieser Kreis passt exakt in das Quadrat, d.h. er liegt an den Kanten des Quadrates an. Wir gehen bei unserem Beispiel von dem Einheitskreis aus, d.h. einem Kreis mit dem Radius von 1.

Es ist zweckmäÿig, folgende Beobachtung nur auf den Viertelkreis im ersten Quadranten zu beschränken.

Nun wirft man zufällig viele Regentropfen oder etwas andereres, z.B. faulige Tomaten, auf den Auschnitt. Anschlieÿend zählt man die Anzahl der geworfenen Objekte, die innerhalb des Vier-

telkreises liegen T Quadrat ^{, sowie die Anzahl derjenigen Objekte, die innerhalb des Teilquadrates} und innerhalb des Viertelkreises liegen T Kreis .

Man beachte nun folgende Formeln:

A Kreis = π∗r ² sowie A Quadrat = r ² .

^{4 Es gilt also:} = π∗r ² A Kreis

4∗r ² A Quadrat

Man könnte nun folgende Vermutung aufstellen:

≈ T Kreis A Kreis

A Quadrat T Quadrat

7