Probabilistische Algorithmen SS09

Aus ProgrammingWiki

< AuK

Archivierte Version vom 2009-05-21T11:20:11+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Einführung in probabilistische Algorithmen
- 1.1 Zufallszahlen
  - 1.1.1 Einführung
  - 1.1.2 Es gibt natürlich auch noch andere Möglichkeiten Zufallszahlen zu erzeugen
2 Algorithmen
- 2.1 Monte-Carlo-Algorithmus Gruppe 2
3 Ausblick
- 3.1 Genetische Programmierung
- 3.2 [[Schwarmalgorithmen]]
4 Aufgaben
5 Quellen

Einführung in probabilistische Algorithmen

Einführung in probalistische Algorithmen

Zufallszahlen

Einführung

Für probabilistische Algorithmen und Vorhersagen benötigt man Zufällige Ereignisse.

Die Frage, was kann man überhaupt als Zufall bezeichnen?, beantworten wir für uns so: Ein Zustand tritt dann zufällig ein, wenn er nicht vorhersagbar ist.

Der Computer ist auf Grund des Determinismus (eine bestimmte Eingabe führt bei identischer Verarbeitung stets zu der selben Ausgabe) ein schlechter Zufallszahlengenerator.

Der prinzipielle Anspruch an Zufallszahlen ist: möglicht große bzw möglichst keine erkennbare Periode, gleichförmige Verteilung und keinerlei Zusammenhänge zwischen den gewonnen Zahlen.

Die 1948 von LEHMER entwickelte Kongruenzmethode ist ein deterministisches Verfahren zum erzeugen sogenannter Pseudozufallszahlen. Sie erzeugt eine ”zufällige” Zahlenfolge ausgehend von einem Startwert (seed), dabei folgt sie der rekursiven Vorschrift:

Z_n = (a * seed + b) mod\ c

Der Anspruch an Zufallszahlen variiert sehr stark je nach Anwendungsbereich. Für ein simples Würfelspiel reicht es schon aus, wenn man den Algorithmus nicht durchschauen kann...dh. die Ergebnisse ausreichend unvorhersehbar und ausreichend gleich verteilt sind. Für Anwendungen in der Kryptografie hingegen ist es unbedingt erforderlich nicht reproduzierbare Zahlen zu erzeugen - also benötigen wir ein nicht deterministisches Verfahren.

Im folgenden Beispiel nehmen wir einen Anfangswert (seed) und berechnen daraus unsere "Zufallszahl" ... schon die Aussage Zufallszahl BERECHNEN lässt uns erahnen, dass dahinter "nur" ein deterministischer Algorithmus steckt, der jedoch auf Grund seiner Komplexität einfach nicht so leicht überschaubar ist.

Wir nutzten für den Aufruf die Java-Funktion "Random".

Der Algorithmus, der sich dahinter verbirgt arbeitet in etwa so:

Damit kann man nun auch eine "zufällige" Kette von Zahlen erzeugen: Zufallszahl = (sehr_große_Prim * Zufallszahl-1 + sehr_große_Prim2) modulo 2⁶⁴

Nun liefert uns das jedoch zwar eine große Zahl, jedoch jedes mal die gleiche...wenn wir nun jedes Mal eine beliebige Zahl eingeben würden hätten wir ein durchaus unduchschaubares Ergebnis, JEDOCH nur wenn wir das Ergebnis noch nicht kennen. Noch besser währe es, wenn wir nichteinmal die Eingabezahl wüssten... Der implementierte Algorithmus kann das.

Rufen Sie die Prozedur ohne Eingabeparameter auf.

Der hierbei verwendete seed ist die UNIX-Systemzeit. Das ist ausreichend unvorhersehbar für zum Beispiel Simulationen, reicht jedoch noch lange nicht aus in der Kryptologie.

Da das ureigenste Prinzip des Computers der Determinismus ist, ist uns dieses nicht möglich. Vielmehr können wir nur versuchen unseren seed schon sehr beliebig (möglichst zufällig) zu wählen.

Hierfür bietet sich die UNIX-Systemzeit an (ein sich immerhin im Sekundentakt ändernder Wert). Für Anwendungen die unter allen Umständen unnachvollziehbar bleiben sollen oder eine sehr hohe Taktrate an Zufallszahlen benötigen ist dies jedoch immernoch nicht ausreichend.

Testen sie die Java-Prozedur myRandom, zunächst mit selbst gewähltem seed. Bei keinem selbst vorgegebenen seed, nimmt die Prozedur myRandom die UNIX-Systemzeit und wir erhalten (für uns) echte unvorhersagbare Zufallszahlen.

static long myRandom(long seed){
     java.util.Random r = new java.util.Random(seed);
     return r.nextInt();

}
 static long myRandom(){
     java.util.Random r = new java.util.Random();
     return r.nextInt();

}

<eval> myRandom(123456789); </eval>

...ein kleiner Anreiz zum ausprobieren: java.lang.Math.abs(myRandom()%100);

Es gibt natürlich auch noch andere Möglichkeiten Zufallszahlen zu erzeugen

Um für die manche Anwendungsfälle in der Praxis taugliche Zufallszahlen zu erzeugen werden physikalische Zufallszahlengeneratoren verwendet. Sie nutzten physikalische Prozesse wie elektrisches oder thermisches Rauschen, Bildrauschen von Web-Cams oder Radioaktiven Zerfall. Ein nettes Beispiel findet ihr hier: http://von-und-fuer-lau.de/randcam.html

Algorithmen

Las-Vegas-Algorithmen

Monte-Carlo-Algorithmus Gruppe 2

Ein Monte-Carlo-Algorithmus ist ein Algorithmus welcher immer ein Ergebnis liefert, allerdings mit einer festlegbaren Wahrscheinlichkeit ein fehlerhaftes Resultat zurückliefert. Mithilfe von Monte-Carlo-Algorithmen lassen sich Probleme lösen die sonst nur schwer bis unlösbar sind.

Multimengenvergleiche

Zum Anfang, was sind überhaupt Multimengen. Multimengen unterscheiden sich von normalen Mengen nur insoweit das jeder Wert 1 bis n mal vorkommen kann. Viel mehr gibt es dazu auch nicht zu sagen. Nun kommt man zu dem Problem der Äquivalenzprüfung.

Würde man zum Beispiel die Multimengen $M_1=\{1,2,2,3,4,5\}$ und $M_2=\{5,4,2,3,2,1\}$ auf Äquivalenz überprüfen wollen, müsste man die beiden Multimengen ordnen und dann auf Äquivalenz prüfen. Dies kostet im Mittel $\mathcal{O}(n log n)$, besser wäre allerdings $\Theta(n)$, dies vermag ein propabilistischer Algorithmus zu erreichen. Es wird verabredet das jeder Multimenge $M_m=\{x_1,x_2,...,x_n\}$ ein Polynom $p_{M_m}$ zugeordnet wird. Dieses Polynom wird nach folgendem Muster gebildet.

$p_{M_m}(x)=(x-x_1)(x-x_2)...(x-x_n)$

Nun werden folgende Regeln verabredet:

1. $M_1\equiv M_2$, wenn $p_{M_1}(x)\ =\ p_{M_2}(x)$ für alle ganzen Zahlen $x$ zutrifft. 

2. $M_1\not\equiv M_2$, wenn in 1. beschriebenes Verfahren für mindestens ein $x$ fehlschlägt.

Was bedeutet das für uns. Nunja, sobald wir auf ein $x$ stoßen, für welches die Funktionswerte der beiden Polynome unterschiedlich sind so ist ziemlich sicher das die Multimengen unterschiedlich sind. Um die Wahrscheinlichkeit zu erhöhen wird der Test für zufällige $x$ wiederholt. Konkret schaut das dann wie folgt aus.

Wir haben die 3 Multimengen m1 ,m2 ,m3 zur Verfügung. m2 ist identisch zu m1, m3 ist eine gänzlich andere Multimenge Die Methode poly liefert den Polynomwert der Multimengen für einen gegebenen Wert.

java.util.List m1=multimenge(7,6);
java.util.List m2=m1;
java.util.List m3=multimenge(7,6);
	int poly(int x,java.util.List nstlist){
		int erg=1;
		if(nstlist.isEmpty())return 1;
		for(int i=0;i<nstlist.size();i++){
			erg=erg*(x-(Integer)nstlist.get(i));
		}
		return erg;
	}

<eval> System.out.println("Polynomwerte:\nm1 "+poly(3,m1)+"\tm2 "+poly(3,m2)+"\tm3 "+poly(3,m3)); </eval> Bitte mehrmals ausführen und Rückgaben beobachten.

Wenn man die Prozedur über alle 3 Multimengen laufen lässt bekommt man mit hoher Wahrscheinlichkeit verschiedene Werte. Es kann aber auch vorkommen das für alle 3 Multimengen der gleiche Polynomwert herauskommt. Man kann deshalb allerdings noch nicht von einer Äquivalenz ausgehen. Dafür sind mehrere Versuch mit zufälligen Eingabewerten notwendig. Dafür verwenden wir die Methode aequivalenztest, diese testet mit einem zufälligen Wert und wiederholt den Test.

boolean aequivalenztest(java.util.List m1,java.util.List m2,int r,int wdh){
		java.util.Random rand=new java.util.Random();
		int random=0;
		for(int i=0;i<wdh;i++){
			random=rand.nextInt(r);
			if(poly(random, m1)!=poly(random, m2))return false;
		}
		return true;
	}

<eval> System.out.println("m1=m2? "+aequivalenztest(m1,m2,4,10)+" m1=m3? "+aequivalenztest(m1,m3,4,10)); </eval> Und noch eine komplette Ausgabe von Anfang bis Ende. <eval> System.out.println("m1 "+printmenge(m1)+"\tm2 "+printmenge(m2)+"\tm3 "+printmenge(m3)); System.out.println("Polynomwerte für den ersten Durchlauf:\nm1="+poly(3,m1)+"\tm2="+poly(3,m2)+"\tm3="+poly(3,m3)); System.out.println("m1=m2? "+aequivalenztest(m1,m2,4,10)+"\tm1=m3? "+aequivalenztest(m1,m3,4,10)); </eval>

Fermat

Ganz klassisch lässt sich der Primcharakter einer Zahl durch durchprobieren mit Probeteilern herausfinden, aber besonders bei großen Primzahlen ist diese Methode schrecklich ineffizient.

Mittels des "Kleinen Satzes von Fermat" kann man mittels randomisieren einen Monte-Carlo Algorithmus entwickeln. Dieser Primzahltest besitzt dann einen Aufwand von \mathcal{O}(log n).

Der "Kleine Satz von Fermat sagt folgendes aus:

a^{primzahl}\equiv a (mod\ prim)

Alternativ wird auch häufig folgende Version benutzt:

a^{primzahl-1}\equiv 1 (mod\ prim)

Wobei a eine beliebige Ganzzahl ist. Nun nimmt man noch den "Satz von Euler dazu.

Für alle natürlichen Zahlen n und a mit n \geq 2 und 1 \leq a < n, wobei ggt(a,n)=1, gilt a^{\varphi(n)}\equiv 1 mod n

PGP

<eval>fermattest(java.math.BigInteger.valueOf(341));</eval>

boolean fermattest(java.math.BigInteger n,int wdh){
		 for (int c = 0; c < wdh; c++) {
	            if(!potMod(n)) {
	                return false;
	            }
	        }
	        return true;

		
	}
	boolean potMod(java.math.BigInteger n){
		

        return java.math.BigInteger.valueOf(2).modPow((n.subtract(n.ONE)), n).equals(n.ONE);

	}

<eval> fermattest(java.math.BigInteger.valueOf(341),4); </eval>

boolean fermattest_proba(java.math.BigInteger n,int wdh){
		 for (int c = 0; c < wdh; c++) {
	            if(!potModa(n)) {
	                return false;
	            }
	        }
	        return true;

		
	}
	boolean potModa(java.math.BigInteger n){
		java.util.Random rand = new java.util.Random();
		
        java.math.BigInteger b = java.math.BigInteger.valueOf(1 + rand.nextInt(99));
        return b.modPow((n.subtract(n.ONE)), n).equals(n.ONE);

	}

<eval> fermattest_proba(java.math.BigInteger.valueOf(341),4); </eval>

<eval>primzahlen_bis(50);</eval>

Solovay/Strassen

boolean solovay_strassen_wdh(int a,int wdh){
		boolean erg=true;
		for(int i=0;i<wdh;i++){
			erg=solovay_strassen(a);
			if(!erg)return false;
		}
		return erg;
	}	
	boolean solovay_strassen(int a){
		java.util.Random rand=new java.util.Random();
		int randn=rand.nextInt(a-1);
		int x=ggt(randn,a);
		if(x!=1)return false;
		float y=randn/a,z=randn*(a-1/2);
		if(y==z%a)return true;
		return false;
	}

<eval>solovay_strassen_wdh(341,10); </eval>

Ausblick

Genetische Programmierung

Schwarmalgorithmen

Aufgaben

Implementieren Sie einen Generator für Pseudozufallszahlen nach der Kongruenzmethode. (Buch S. 124)

z_{n}=(a*z_{n-1}+b)mod\ c

mit

z_0=4567\\a=9749\\b=0\\c=2^{18}=262144

/*(define seed1 12347899 )

(define zf
;Kongruenzmethode in Scheme
(lambda ()
(let ((seed2 (modulo (+ (* 9749 seed1) 0) 262144)))
(set! seed1 seed2)
seed2)))*/

(Um einen zufälligen Startwert anzunehemn gibt es zwar auch Sprachelemente in Scheme, jedoch funktionieren diese hier in der Wiki nicht.)

Setzen Sie sich an einem schönen Tag ins Freie, und beobachten Sie Ameisen bei der Futtersuche. Welche Beziehungen zu dem Ameisenalgorithmus können Sie erkennen? Welche Beispiele aus der Natur können noch einen Anreiz darstellen, sie als Vorbild für einen Algorithmus zu nutzen?

Entwerfen sie einen Quicksort-Algorithmus, welcher sein Pivot-Element zufällig wählt. Vergleichen sie die effizienz mit der Quicksort-Variante, welche immer das erste Element als Pivot-Element nutzt.

Aufgabenverteilung

Quellen

http://www.riskglossary.com/link/monte_carlo_method.htm

Oliver Lau "Faites vos jeux! - Zufallszahlen erzeugen, erkennen und anwenden" (c't 2009, Heft 2)

http://www.addison-wesley.de/Service/Krueger/kap12006.htm

Schickinger, Steger - Diskrete Strunkturen - Band 2 - Wahrscheinlichkeitstheorie und Statistik

Juraj Hromkovič - Algorithmics for Hard Problems

Juraj Hromkovič - Randomisierte Algorithmen

http://www.m-boehmer.de/pdf/Schwarmintelligenz_Artikel.pdf

Jörg Rothe - Komplexitätstheorie und Kryptologie

Probabilistische Algorithmen SS09

Inhaltsverzeichnis

Einführung in probabilistische Algorithmen

Zufallszahlen

Einführung

Es gibt natürlich auch noch andere Möglichkeiten Zufallszahlen zu erzeugen

Algorithmen

Monte-Carlo-Algorithmus Gruppe 2

Multimengenvergleiche

Fermat

Solovay/Strassen

Ausblick

Genetische Programmierung

Schwarmalgorithmen

Aufgaben

Quellen

Suche