AuK/Probabilistische Algorithmen SS09
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Java</language>
==Einführung in probabilistische Algorithmen==
====Was sind probalistische Algorithmen?====
Probalistische, oder auch stochastische oder randomatisierte Algorithmen, zeichnen sich dadurch aus, dass der intere Ablauf eines Programms dem Zufall unterliegt. Im Gegensatz dazu gibt es die deterministischen Programme, bei welchen der Ablauf von vornhinein fest steht.
<code>
/*
switch((int)rand()*3){
case 0: return 1;
case 1: return 3;
case 2: return 7;
default: return -1;
}
*/
</code>
Man kann sich probalistische Algorithmen als deterministischen Algorithmus vorstellen, bei dem jede Entscheidungsmöglichkeit im Programm einer gewissen Wahrscheinlichkeit unterliegt. Für eine fixe Inputgröße ''x'' kann der probalistische Algorithmus evt. unterschiedliche Ergebnisse liefern und/oder unterschiedliche Zeiten zur Berechnung brauchen. Algorithmen, deren Ergebnis immer korrekt ist, falls sie eines liefern, heißen [[Las-Vegas-Algorithmen]]. Im Gegensatz dazu gibt es [[Monte-Carlo-Algorithmen]], welche zwar immer ein Ergebnis liefern, welches aber nicht zwangsläufig korrekt sein muss. Außerdem gibt es Sherwood-Algorithmen, welche einen Spezialfall von Las-Vegas-Algorithmen darstellen, aber keine Sackgassen besitzen. Diese Sherwood-Algorithmen arbeiten im mittleren Fall bedeutend effizienter, als im schlechtesten. Durch ein Zufallselement wird dann dafür gesorgt, dass sich alle Fälle ähnlich dem mittleren Fall verhalten, wordurch im Mittel die Effizienz gesteigert wird. Dies nennt man den Robin-Hood-Effekt.
====Wozu probalistische Algorithmen====
Randomatisierte Algorithmen können effizienter arbeiten und einfachter zu verstehen und implementieren sein als die besten deterministischen Algorithmen für das gleiche Problem. Zur Bestimmung einer Primzahl gibt es etwa
# einen effizient in Polynomzeit arbeitenden probalistischen Algorithmus,
# keinen bekannten deterministischen, in Polynomialzeit arbeitenden Algorithmus und
# es ist nicht bekannt, ob es sich um ein P oder NP- Problem (oder EXPTIME) handelt (Also ob das Problem mit einem deterministischen Algorithmus in '''P'''olynomialer Zeit oder '''n'''ichtdeterministisch in '''P'''olynomialer Zeit gelößt werden kann)
Für Probleme, bei denen selbst der beste bekannte, deterministisch arbeitende Algorithmus einen hohen polynomialen Aufwand hat, lassen sich oft efizientere probalistische Algorithmen finden.
Als Beispiel betrachten wir uns hier die Berechnung der Kreiszahl Pi:
Als Formel für eine numerische Näherung könnte man zum Beispiel der Formel des Inders Srinivasa Ramanujan aus dem Jahr 1914 nutzen:
<math>\frac{1}{\pi}=\frac{\sqrt{8}}{9801}\cdot \sum_{n=0}^{\infty}\frac{(4n)!\cdot(1103+26390n)}{(n!)^4\cdot396^{4n}}</math>
Alternativ ist es möglich, einen Kreis durch ein Quadrat zu Zeichnen, in dieses zufällig gewählte Punkte zu werfen, und über deren Verteilungsverhältnis Pi zu ermitteln.
[[Bild:Pi_statistisch.png]]
Ein Algorithmus, in dem dies Implementiert ist, findet sich hier:
<code>public static double berechne_pi(int tropfenzahl) {
double pi = 0;
int innerhalb = 0;
int gesamt = tropfenzahl;
while (tropfenzahl > 0) { // generiere Tropfen und addiere je nach Zugehörigkeit
double dotx = Math.random();
double doty = Math.random();
if (dotx*dotx + doty*doty <= 1) { // Punkt liegt innerhalb des Kreises
innerhalb++;
} else { // Punkt liegt außerhalb des Kreises
}
tropfenzahl--;
}
pi = 4*(double)innerhalb/gesamt;
return pi;
}
</code>
<eval>
berechne_pi(100);
</eval>
====Probalistische Algorithmen in kritischen Anwendungen====
Monte-Carlo-Algorithmen liefern ein Ergebnis, welches nicht zwangsläufig korrekt sein muss. Es gibt Menschen, die daraus Schlussfolgern, dass probalistische Algorithmen für etwa sicherheitskritische Anwendungen nicht geeignet sind. Dies muss so aber nicht stimmen, da die Wahrscheinlichkeit eines Fehlers signifikant gesenkt werden kann, in dem man den Algorithmus mehrmals mit dem gleichen Eingabeparameter laufen lässt. Unter Umständen ist es auch möglich, für einen Monte-Carlo-Algorithmus einen Las-Vegas-Algorithmus anzugeben. In der Regel braucht es dazu aber einen Verifizierer für die Lösung, also einen Algorithmus, der zu einem Lösungsvorschlag testen kann, ob der Vorschlag korrekt ist. Man erhält dann einen Las-Vegas-Algorithmus, in dem man den gegebenen Monte-Carlo-Algoroithmus ausführt, anschließend die Lösung mit dem Verifizierer überprüft, und dieses Verfahren solange wiederholt, bis eine korrekte Lösung berechnet wurde. Bei dieser Methode ist zwar die Rechenzeit nicht nach oben beschränkt, man kann aber die Anzahl der Iterationen grob nach oben abschätzen.
Umgekehrt lässt sich aus jedem Las-Vegas-Algorithmus ein Monte-Carlo-Algorithmus machen, in dem man einen obere Schranke für die Rechenzeit festlegt und, falls diese Überschritten wurde, eine beliebige Ausgabe liefert (etwa "?"), welche dann als falsche Ausgabe interpretiert wird.
====Formalisierung von probalistischen Algorithmen====
Um eine formale Notation für probalistische Algorithmen zu erhalten, kann man eine deterministische Turingmaschine ''M'' mit einem zusätzlichen unendlichen Band nehmen. Dieses zusätzliche Band kann nur gelesen werden und enthält eine unendliche, zufällige Sequenz von "0" und "1". Die Maschine ''M'' schiebt dieses Band nur von links nach rechts.
Jeder randomisierter Algorithmus ''A'' zusammen mit einem festen Eingangswert ''x'' stellt also ein Zufallsexperiment dar.
Für jeden probalistischen Algorithmus können wir die Komplexität prüfen, in dem wir die Anzahl der Zufallsbits mit betrachten. Wenn die Funktion
<math>Random_{A}(n)</math>
das Höchstmaß an Zufallszahlen in allen Durchläufen von ''A'' für ''x'' ist, dann gilt
<math>Random_{A}(n) = max\left\{Random_A(x) | n \in \mathbb{N}\right\}</math>
Dieses Maß ist aus folgenden Gründen sehr wichtig:
* Es kostet viel Arbeit, um eine Prozedur zu schreiben, die das gleiche Verhalten hat, wie ein probalistischer Algorithmus. Und diese Arbeit wächst mit Länge der Prozedur an.
* Wenn <math>Random_{A}(n)</math> von ''A'' an eine logarithmische Funktion gebunden ist, dann konvergiert die Anzahl der Durchläufe für einen festen Eingangswert ''x'' gegen <math>2^{Random_{A}(n)}</math>.
Das heißt, dass ''A'' deterministisch Simuliert werden kann, in dem man jeden Durchlauf nacheinander simuliert. Wenn ''A'' das Problem in Polynomzeit löst, benötigt auch die deterministische Simulation von ''A'' nur Polynomzeit. Dies wird als [[Derandomisierung]] bezeichnet.
Für jeden Durchlauf ''C'' von ''A'' mit ''x'' kann eine Wahrscheinlichkeit zur Lösung von ''x'' angegeben werden. Diese ergibt sich aus der Multiplikation aller Wahrscheinlichkeiten der Zufallsentscheidungen, welche in ''C'' getroffen wurden. Diese bezeichnen wir im Folgenden als <math>Prob_{A,x}(C)</math>.
Ein probalistischer Algorithmus ''A'' kann für den gleichen Eingabewert ''x'' unterschiedliche Resultate liefern. Die Wahrscheinlichkeit, dass ''A'' für ''x'' das korrekte Ergebnis ''y'' liefert, also <math>Prob(A(x) = y)</math> ist die Summe aller <math>Prob_{A,x}(C)</math>, bei denen ''C'' 'y'' ausgibt. Das Ziel beim konstruieren eines probalistischen Algorithmus ist es also, ein möglichst hohes <math>Prob(A(x) = y)</math> zu erhalten.
Verschiedene Durchläufe von ''A'' mit ''x'' können aber auch unterschiedliche Rechenzeiten (oder Kosten) haben. Wenn <math>Time(C)^{10}</math> die Komplexität des Durchlaufs ''C'' von ''A'' mit ''x'' ist, dann ist die erwartete Zeitkomplexität von ''A'' mit ''x''
<math>ExpTime_A(x)=E\left[Time\right] = \sum Prob_{A,x}(C)\cdot Time(C)</math>
Wobei die Summe von allen Durchläufen ''C'' von ''A'' mit ''x'' gebildet wird.
Man könnte die Exp-Time-Funktion auch als Funktion über den Eingabewert definieren, in dem man
<math>ExpTime_A(n) = max\left\{ExpTime_A(x) \right\} </math> berechnet.
Oft ist es jedoch nicht ganz einfach, <math>ExpTime_A(n) </math> für einen bestimmten Algorithmus ''A'' anzugeben. Um mit dieser
Schwierigkeit aufzuräumen, wird nur der worst case betrachtet.
Wenn also <math>Time_A(x) = max\left\{Time(C) \right\}</math> wobei ''C'' ein Durchlauf von ''A'' mit ''x'' ist, dann ist die worst-case-Zeitkomplexität von ''A''
<math>Time_A(n) = max\left\{Time_A(X) \right\} </math>.
Leider ist diese Definition in manchen Fällen etwas irrführend, weil es sein kann, dass in dem probalistischen Algorithmus endlos läuft. Bei einem deterministischen Algorithmus sind endlose Rechenzeiten verboten, da der Computer in einer Endlosschleife feststecken würde, und das Problem nie lösen wird. Bei probalistischen Algorithmen ist es durchaus möglich, dass ein Algorithmus endlos rechnet, da dies auch ohne Endlosschleife möglich ist. Bei jeden neuen Durchlauf werden neue Zufallsparameter gewählt, und der Algorithmus könnte terminieren. Eine Möglichkeit, um die Rechenzeit einzuschränken, ist, wie schon beschrieben, eine Schranke in den Algorithmus einzubauen, welche immer ein falsches Ergebnis liefert, wenn der Algorithmus bis zu einer bestimmten Zeit nicht terminiert ist.
==(Pseudo)Zufallszahlen==
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:
<math>Z_n = (a * Z_n-1 + b) mod\ c</math>
mit
<math>a= grosse\ Primzahl\ z.B: 16807 </math>
<math>b= Konstante</math>
<math>c= grosse\ 2er-Potenz\ z.B: 2^{64}</math>
Diese Methode liefert uns jedoch bei gleichem seed immer die gleiche Zahlen-kette, noch dazu ist sie periodisch (hängt von der Größe von c ab).
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.
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 könnten wir zum Beispiel die UNIX-Systemzeit verwenden.
'''Ein Beispiel:'''
Testen sie die Java-Prozedur myRandom, zunächst mit selbst gewähltem seed.
<code>
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();
}
</code>
<eval>
myRandom(123456789);
</eval>
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, wir erhalten (für uns) echte unvorhersagbare Zufallszahlen.
...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===
Las-Vegas-Algorithmen sind randomisierte Algorithmen, die uns garantieren, dass jede berechnete Ausgabe korrekt ist. Somit ist ein falsches Resultat in diesem Modell der randomisierten Berechnung verboten. In der Literatur benutzt man aber zwei unterschiedliche Modelle der Las-Vegas-Algorithmen und zwar abhängig davon, ob auch eine Antwort "?" mit der Bedeutung "Ich weiß es nicht" bzw. "In diesem Lauf war ich nicht im Stande, die richtige Lösung zu berechnen", zulässig ist.
Bei der ersten, strengeren Möglichkeit, definiert sich ein Algorithmus ''A'' als Las-Vegas-Algorithmus für die Berechnung der Funktion ''F'', wenn für jede Eingabe ''x'' von ''F'' gilt:
<math>Wahr(A(x) = F(x)) = 1</math>.
Bei dieser Definition des Las-Vegas-Algorithmus wird immer die erwartete Komplexität der Algorithmen untersucht, etwa die erwartete Zeitkomplexität <math>Exp-Time_A(n)</math>. Hier ist es zu erwarten, dass man unterschiedlich lange Läufe auf einer Eingabe erhält. Wären nämlich alle Läufe ungefähr gleich lang, könnte man einfach einen genauso effizienten deterministischen Algorithmus entwerfen, indem immer ein fester Lauf des randomisierten Algorithmus simuliert wird. Da die Zufallsbits nur Einfluss auf die Vorgehensweise des Algorithmus haben, liefert der Las-Vegas-Algorithmus immer ein korrektes Ergebnis, wenn er terminiert. Die Zeitkomplexität ist in diesem Fall eine Zufallsvariable. Ein bekanntes Beispiel ist der Random-Quicksort-Algorithmus, der sein Pivotelement zufällig wählt, dessen Ausgabe aber immer sortiert ist. Dadurch lassen sich keine Best-Case und Worst-Case-Beispiele mehr konstruieren. Aber der Worst-Case kann natürlich auch dann noch eintretten, wenn zufällig das schlechteste Pivot-Element gewählt wird.
Die zweite Möglichkeit der Spezifikation von Las-Vegas-Algorithmen sagt aus, dass der Algorithmus ''A'' ein Las-Vegas-Algorithmus für eine Funktion ''F'' ist, wenn für jede Eingabe ''x'' gilt:
* <math>Wahr(A(x) = F(x)) \geq \frac{1}{2} </math> und
* <math>Wahr(A(x) = "?") = 1 - Wahr(A(x) = F(x)) \leq \frac{1}{2}</math>
Wie zu erkennen ist, schließt die zweite Bedingung eine falsche Antwort aus, d. h. es wird entweder die richtige Antwort ausgegeben, oder die Antwort "?". Die erste Bedingung legt fest, dass ein richtiges Resultat von <math>F(x)</math> mindestens eine Wahrscheinlichkeit von größer oder gleich <math>\frac{1}{2}</math> haben muss. Die Konstante <math>\frac{1}{2}</math> ist dabei recht willkürlich gewählt und kann mit jedem beliebigen Wert zwischen 0 und 1 ersetzt werden, da sich die Wahrscheinlichkeit, das richtige Ergebnis berechnet zu haben, durch die Anzahl der unabhängigen Läufe von <math>F(x)</math> beliebig erhöhen lässt.
Um aus dem Modell, bei dem die Antwort "?" erlaubt ist, ein Modell zu erhalten, bei dem immer alle Aussagen korrekt sind, kann man wie folgt vorgehen: Wenn ''A'' ein Las-Vegas-Algorithmus ist, der mit beschränkter Wahrscheinlichkeit ein "?" ausgeben darf, dann wird ''A'' modifiziert, in dem immer, anstatt "?" auszugeben, der Algorithmus auf die selbe Eingabe neu gestartet. Das führt zu einem neuen Algorithmus A'. Wenn man annimmt, dass der Algorithmus dabei in einem Durchlauf immer mit der Wahrscheinlichkeit <math>\frac{1}{2}</math> das richtige Ergebnis liefert, hat man schnell eine hohe Wahrscheinlichkeit, nach wenigen Durchläufen ein richtiges Ergebnis zu erhalten.
* Soll die Zeitkomplexität des Algorithmus beschränkt werden, liegt die Wahrscheinlichkeit, dass der Algorithmus ein korrektes Ergebnis liefert. Es gibt also Fälle, in denen der Algorithmus kein Ergebnis ausgibt.
Dame n*n
Die Wahrscheinlichkeit, dass ein Las-Vegas-Algorithmus terminiert, lässt sich durch eine Erhöhung der Rechenzeit erkaufen. Es kann jedoch auch sinnvoll sein, eine größere Wahrscheinlichkeit für das Scheitern in Kauf zu nehmen, wenn dadurch die Zeit abnimmt, einen Misserfolg zu erkennen.
===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.
Er liefert demzufolge, keine Näherungslösungen sondern ebend entweder ein richtiges oder falsches Ergebnis - was sich jedoch nicht direkt feststellen lässt. Das gelieferte Ergebnis wird als "wahr" befunden.
Mithilfe von Monte-Carlo-Algorithmen lassen sich Probleme lösen die sonst nur schwer bis unlösbar sind.
====Fehlerwarscheinlichkeit====
Durch häufiges Wiederholen lässt sich die Warscheinlichkeit, dass der Algorithmus ein falsches Ergebnis liefert soweit eindämmen, dass ein Hardwareversagen um ein vielfaches wahrscheinlicher sein kann.
====Multimengenvergleiche====
<code hidden>
public java.util.List multimenge(int intervall,int anzahl){
java.util.List mmenge=new java.util.LinkedList();
java.util.Random r=new java.util.Random();
if(intervall==0)
return null;
for(int i=0;i<anzahl;i++){
mmenge.add(r.nextInt(intervall));
}
return mmenge;
}
String printmenge(java.util.List list){
String liste="";
liste+=" (";
for(int i=0;i<list.size();i++){
liste+=list.get(i)+" ";
}
liste+=")";
return liste;
}
</code>
Zum Anfang, was sind überhaupt Multimengen. Multimengen unterscheiden sich von normalen Mengen nur insoweit das jeder Wert <math>1</math> bis <math>n</math> 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 <math>$M_1=\{1,2,2,3,4,5\}$</math> und <math>$M_2=\{5,4,2,3,2,1\}$</math> auf Äquivalenz überprüfen wollen, müsste man die beiden Multimengen ordnen und dann auf Äquivalenz prüfen. Dies kostet im Mittel <math>$\mathcal{O}(n log n)$</math>, besser wäre allerdings<math> $\Theta(n)$</math>, dies vermag ein propabilistischer Algorithmus zu erreichen.
Es wird verabredet das jeder Multimenge <math>$M_m=\{x_1,x_2,...,x_n\}$</math> ein Polynom <math>$p_{M_m}$</math> zugeordnet wird.
Dieses Polynom wird nach folgendem Muster gebildet.
<math>$p_{M_m}(x)=(x-x_1)(x-x_2)...(x-x_n)$</math>
Nun werden folgende Regeln verabredet:
1. <math>$M_1\equiv M_2$</math>, wenn <math>$p_{M_1}(x)\ =\ p_{M_2}(x)$</math> für ''alle'' ganzen Zahlen <math>$x$</math> zutrifft.
2. <math>$M_1\not\equiv M_2$</math>, wenn in 1. beschriebenes Verfahren für mindestens ein <math>$x$</math> fehlschlägt.
Was bedeutet das für uns. Nunja, sobald wir auf ein <math>$x$</math> 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 <math>$x$</math> 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.
<code>
java.util.List m1=multimenge(7,6);
java.util.List m2=m1;
java.util.List m3=multimenge(7,6);
public static 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;
}
</code>
<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.
<code>
public static 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;
}
</code>
<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====
<code>
</code>
Ganz klassisch lässt sich der Primzahlcharakter einer Zahl durch durchprobieren mit Probeteilern herausfinden, aber besonders bei großen Primzahlen ist diese Methode schrecklich ineffizient.
Mittels des "Kleinen Satzes von <tt>Fermat</tt>" kann man mittels randomisieren einen Monte-Carlo Algorithmus entwickeln. Dieser Primzahltest besitzt dann einen Aufwand von <math>\mathcal{O}(log\ n)</math>.
Der "Kleine Satz von <tt>Fermat</tt> sagt folgendes aus:
<math>a^{primzahl}\equiv a (mod\ prim)</math>
Alternativ wird auch häufig folgende Version benutzt:
<math>a^{primzahl-1}\equiv 1 (mod\ prim)</math>
Wobei <math>a</math> eine beliebige Ganzzahl ist.
Über den "Satz von <tt>Euler</tt>" lässt sich die zweite Formel herleiten:
Für alle natürlichen Zahlen <math>n</math> und <math>a</math> mit <math>n \geq 2</math> und <math>1 \leq a < n</math>, wobei <math>ggt(a,n)=1</math>, gilt <math>a^{\varphi(n)}\equiv 1\ mod\ n</math>
Da unter der Bedingung das <math>$1\leq a < n$</math> gilt das <math>\varphi (n) \equiv n-1</math> für Primzahlen ist, lässt sich dies im Satz von <tt>Fermat</tt> einsetzen.
Die Standardimplementation des Fermattests liefert schon recht zuverlässig aussagen über den Primzahlcharakter vieler Zahlen, allerdings scheitert der Algorithmus an sogenannten Pseudoprimzahlen und den <tt>Carmichael</tt>-Zahlen. Im Intervall von <math>$0\ -\ 10000$</math> gibt es nur 22 solcher Pseudoprimzahlen und gerademal 7 <tt>Carmichael</tt>-Zahlen.
<code hidden>
boolean fermattest(java.math.BigInteger n){
return potMod(n);
}
</code>
<eval>fermattest(java.math.BigInteger.valueOf(341));</eval>
Durch randomisieren und wiederholen lässt sich ein Primzahltest herstellen der auch Pseudoprimzahlen und Carmichael-Zahlen bei 10 Wiederholungen meistens entdeckt. Durch mehr Wiederholungen kann die Genauigkeit weiter erhöht werden.
<code hidden>
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);
}
</code>
<eval>
fermattest_proba(java.math.BigInteger.valueOf(341),4);
</eval>
<code hidden>
void primzahlen_bis(int n){
String erg="";
for(int i=1;i<=n;i+=2){
if(fermattest_proba(java.math.BigInteger.valueOf(i),4))erg+=i+",";
}
System.out.println(erg);
}
</code>
<eval>primzahlen_bis(50);</eval>
====Primzahltest nach Solovay und Strassen====
<code hidden>
int ggt(int zahl1, int zahl2) {
while (zahl2 != 0) {
if (zahl1 > zahl2) {
zahl1 = zahl1 - zahl2;
} else {
zahl2 = zahl2 - zahl1;
}
}
return zahl1;
}
</code>
Bei dem Primzahltest von Solovay und Strassen handelt sich ein weiteres mal um einen weiteren Monte-Carlo-Algorithmus.
<code>
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;
}
</code>
<eval>solovay_strassen_wdh(341,10);
</eval>
==Ausblick==
===Genetische Programmierung===
'''TODO'''
===Schwarmalgorithmen===
Die Schwarmintelligenz ist ein Forschungsfeld der künstlichen Intelligent und hat nahe Bindungen an die Agententechnologie. Als Agent meinen wir hier ein Computerprogramm, welches zu einem gewissen eigenständigem Verhalten fähig ist. Auch die Begriffe verteilte künstliche Intelligenz sowie kollektive Intelligenz im Allgemeinen sind für Schwarmintelligent i.w.S. gebräuchlich. Dabei wird versucht, in einem Computerprogramm das Verhalten von intelligenten Schwärmen zu simulieren. Besonders geeignet sind Schwarmalgorithmen, um für sehr komplexe Probleme schnell gute (keine optimalen) Lösungen zu finden.
====Schwärme in der Natur====
Die Schwarmalgorithmen sind, wie neuronale Netze, genetische Algorithmen und vieles andere auch, aus der Natur abgeguckt. Etwa bei Ameisen, Termiten, Vögeln, Fischen, Bienen und anderen Tieren kann man beobachten, dass sie in einem Schwarm Aufgaben lösen, zu denen ein Individuum allein nicht fähig wäre.
<video type=youtube>kJiKKNCQorQ</video>
So schaffen es Termiten z. B. extrem komplexe Bauten zu errichten, obwohl keine Termite weiß, wie der gesamte Bau aussehen und es keine "Super-Termite" gibt, welche den anderen Anweisungen gibt.
[[Bild:Termit6.jpg.jpeg]]
Wenn wir uns überlegen, was passieren würde, wenn man ein paar Hundert Menschen hinsetzt, und sie unkoordiniert versuchen lässt, ein Haus zu bauen, erkennt man schnell, dass bei einem Schwarm diesen Tieren eine Art Intelligenz vorliegt.
====Futtersuche von Ameisen====
Die Suche nach Futter gehört für jedes Lebewesen zu einer existentiellen Aufgabe. Ameisen sind dabei bei der Bewältigung dieser Aufgabe besonders effizient. Dabei markieren die Ameisen beim Ausschwärmen aus dem Nest ihren Weg mit Pheromonen, die ihre Artgenossen als Wegweiser wahrnehmen. Sobald eine Ameise Futter gefunden hat, kehrt sie damit zum Nest zurück. Der Rückweg ist dabei der Weg, mit der größten Intensität an Pheromonen. Wenn die Ameise als erste an ihrem Futter war, kehrt sie auf ihrem eigenen Weg wieder zurück, und hinterlässt auf dem Weg wieder Pheromone. Da alle Ameisen etwa die gleiche Geschwindigkeit haben, wird automatisch der kürzeste Weg zum Futter der, mit der höchsten Intensität an Pheromonen, da die anderen Ameisen noch nicht wieder am Nest angekommen sind. Dabei ist aber zu beachten, dass jede Ameise nur mit einer bestimmten Wahrscheinlichkeit dem Weg mit der stärksten Ausprägung an Pheromonen folgt, so können Abkürzungen gefunden werden und neue Wege zu neuen Futterquellen erschlossen werden. Außerdem verliert das Pheromon mit der Zeit an Intensität.
<video type=youtube>tEZXh-8JGds</video>
Die Ameise schafft es also automatisch, den kürzesten Weg zu ihrem Ziel zu finden. Dieses Problem erinnert uns, leicht abgewandelt, an das altbekannte Problem des Travelling Salesman. Mit Hilfe von sogenannten Ameisenalgorithmus kann man hierfür in wenigen Iterationen eine gute Lösung bekommen.
<video type=youtube>C1XYMG5R5cQ</video>
<video type=youtube>HAQbTh6gzCw</video>
Java-Applet für TSP-Simulation mit Ameisen
http://www.ameisenalgorithmus.de/appletantstour.htm
TSP - Manuell
http://www.ameisenalgorithmus.de/appletmanuelletour.htm
Die Ameisen laufen dabei erst einmal Willkürlich einen bestimmten Kurs, wenn sie wieder am Zielpunkt sind, wird abhängig von der benötigten Entfernung die Stärke der Pheromone für die Strecke bestimmt, auf der die Ameise unterwegs war. Desto kürzer die Rundreise, desto mehr Pheromone. Die darauffolgende Ameise orientiert sich an der Gesamtheit der Pheromone auf dem Weg, und es ist Wahrscheinlicher, dass sie einen Weg benutzt, welcher schon viele Pheromone besitzt. So bekommt man schnell eine gute Näherungslösung für das Problem.
Eine exakte Umsetzung dieses Problems, inc Code, findet sich hier: http://www.m-boehmer.de/pdf/Schwarmintelligenz_Artikel.pdf
====Robotik====
Eine andere Möglichkeit der Anwendung bei Schwarmalgorithmen ist die Robotik. Hier steht nicht die Optimierung im Vordergrund, sondern die Fähigkeit, dass sich mehrere Individuen zusammen schließen, um Probleme zu lösen, die sie allein nicht bewältigen können. So z.B. das Überqueren von Hindernissen, die größer sind als sie selbst, oder Schluchten, die breiter sind, als sie selbst.
[[Bild:Roboter.PNG]]
Diese Roboterschwärme arbeiten zusammen, ohne dass es eine zentrale Steuerung gibt. So wie Ameisen sich verständigen, in dem sie Pheromone hinterlassen, könnten Roboter etwa Lichtsignale aussenden, welche dann über Sensoren aufgenommen werden.
Darüber hinaus gibt es noch zahlreiche andere Anwendungsmöglichkeiten für Schwarmalgorithmen, wie etwa alle möglichen Optimierungsprobleme, geschickte Sortiervorgänge (manche Ameisen sortieren ihre Larven nach Größe) und vieles mehr.
==Aufgaben==
'''1.'''
Implementieren Sie einen Generator für Pseudozufallszahlen nach der Kongruenzmethode. (Buch S. 124)
<math>z_{n}=(a*z_{n-1}+b)mod\ c</math>
zum Beispiel mit
<math>z_0=4567\ a=9749\ b=0\ c=2^{18}=262144</math>
<code>
/*(define seed1 1234789)
(define zf
;Kongruenzmethode in Scheme
(lambda ()
(let ((seed2 (modulo (+ (* 9749 seed1) 0) 262144)))
(set! seed1 seed2)
seed2)))*/
</code>
<eval>//(zf)</eval>
(Um einen zufälligen Startwert anzunehemn gibt es zwar auch Sprachelemente in Scheme, jedoch funktionieren diese hier in der Wiki nicht.)
'''2'''
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?
'''3'''
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