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

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