AuK/Probabilistische Algorithmen WS13-14

Wiki-Quelltext dieser Seite.

=Einleitung=
=Zufall=
==Was ist Zufall?==
Auf der Suche nach der Definition des Begriffes Zufall liegt es nahe,
die Wortbedeutung im Duden nachzuschlagen. Hier ist der Zufall als "etwas, was man nicht vorhergesehen hat, was unerwartet geschah" definiert.
Hieraus ergibt sich die Fragestellung, ob das eingetretene Ereignis niemals vorausgesagt werden kann, oder nur in einem speziellen Fall nicht vorhergesehen werden konnte.
Ein Beispiel:
Wir betrachten den Wurf einer Münze, genauer gesagt den Zeitpunkt t, an welchem die Münze wieder beginnt, abwärts zu fallen.
Das Ergebnis des Wurfes erscheint zufällig. Doch für einen begabten Mathematiker mit entsprechender Rechentechnik wäre
es zum Zeitpunkt t durchaus möglich, anhand der Rotation, Umweltbedingungen und weiterer Parameter eine Vorhersage bezüglich des Ergebnis zu treffen.
 
==Zufallszahlen erzeugen==
<!--
radioaktiver zerfall für zufall hoher güte
lottoziehung, warum echt zufällig


 -->

=Numerisch probabilistische Algorithmen=
==Definition==

Numerisch probabilistische Algorithmen haben als Ergebnis eine Näherungslösung mit wählbarer Genauigkeit. Das heißt, dass der Nutzer selbst durch Wahl seiner Eingaben bestimmen kann wie genau das gewünschte Ergebnis sein soll.
Weiterhin ist diese Art von Algorithmen nichtdeterministisch, dass bedeutet das bei mehrfacher Ausführung mit dem gleichen Wert unterschiedliche Lösungen zurückgegeben werden können.

==Beispiel: Zufallsregen==
=Las-Vegas-Algorithmen=
=Monte-Carlo-Algorithmen=
==Prinzahltest nach Fermat==
==Primzahltest nach Solovay und Strassen==


=Literaturverzeichnis=
* Wagenknecht, Christian: Algorithmen und Komplexität, Fachbuchverlag Leipzig, 2003
* Ziegenbalg, Jochen: Algorithmen, Spektrum Akademischer Verlag, 1996
* Mathar, Rudolph; Pfeifer, Dietmar: Stochstik für Informatiker, B.G. Teubner Verlag, 1990
* Wanka, Rolf: Approximationsalgorithmen, B.G. Teubner Verlag, 2006
* Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford: Algorithmen, eine Einführung,Oldenbourg Verlag, 2007
* Gumm, Heinz; Sommer, Manfred: Einführung in die Informatik, Oldenbourg Verlag, 2006