Sebastian Rick
Görlitz, den 17. Februar 2008
Jörg Wiesner
Görlitz, den 17. Februar 2008
Algorithmen und Komplexität
Beleg:
Probabilistische Algorithmen
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 schnelle-
ren/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 Algorith-
men. 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 un-
gü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 Kongruenzme-
thode, 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
longa = 34543;
//Beispielwerte
longb = 56789;
longc = 556;
for(int i=0; i<=10;i++) {
//Darstellen der ersten 10 Werte einer
//(Pseudo-)Zufallszahlenfolge
longzn = (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
2
4
sowie A
Quadrat
= r
2
.
Es gilt also:
A
Kreis
A
Quadrat
=
r
2
4r
2
Man könnte nun folgende Vermutung aufstellen:
A
Kreis
A
Quadrat
T
Kreis
T
Quadrat
7
0 Kommentare