Probabilistische Algorithmen

Inhaltsverzeichnis

1 Einführung

2 (Pseudo-)Zufallszahlen und Zufallszahlengeneratoren

3 Numerische Probabilistische Algorithmen

4 Las Vegas-Algorithmen

5 Monte-Carlo-Algorithmen
5.1 Äquivalenz zweier Multimengen
5.1.1 Analyse des Problems
5.1.2 Implementierung
5.2 Primzahltest nach Fermat
5.2.1 Analyse des Problems
5.2.2 Implementierung
5.3 Primzahltest von Solovay und Strassen
5.3.1 Analyse des Problems
5.3.2 Implementierung

6 Literaturverzeichnis

7 Aufgabenteilung

1 Einführung

Es ist mehrfach festgestellt worden, dass schnellere Rechner nur einen geringen Einfluss auf die Aufwandsordnung haben, d.h. sie leisten nur einen begrenzten Beitrag zur schnelle­ren/effizienteren 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 wor.V-ca.se-Entseheidungen treffen 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 getroffen 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.

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 Spraehelemente zur Erzeugung von Zufallszahlen, also Zufallszahlengeneratoren,In Scheme gibt es dazu das Spraehelement 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 enwiekelt wurde. Sie erzeugt eine sieh wiederholende Folge von (vermeintlichen) Zufallszahlen, Ausgehend von einer Startzahl, dem Seed, (auf dt, Samen, Keim) wird die rekursive Vorschrift

Abbildung in dieser Leseprobe nicht enthalten

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

Diese Zahlen haben natürlich nur Beispieleharakter, 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äufig immer die selbe Folge entsteht.

2 (Pseudo-)Zufallszahlen und Zufallszahlengeneratoren

Will man einen wirklieh 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 zuriiekgegeben wird.

Abbildung in dieser Leseprobe nicht enthalten

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

Abbildung in dieser Leseprobe nicht enthalten

3 Numerische Probabilistische Algorithmen

Numerische Probabilistische Algorithmen liefern für ein Problem eine Xährungslösung, Allgemein gesehen kann man sieh 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 sieh ein Quadrat vor, in dem sieh ein Kreis befindet. 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,Xun 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 TQuadrat, sowie die Anzahl derjenigen Objekte, die innerhalb des Teilquadrates und innerhalb des Viertelkreises liegen TKreis.

Abbildung in dieser Leseprobe nicht enthalten

Man beachte nun folgende Formeln:

Abbildung in dieser Leseprobe nicht enthalten

[...]