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. Er steht allerdings vor dem Problem, dass er das Ergebnis vor dem Auftreffen der Münze berechnen muss (Zeitfrage). Demnach ist eine Differenzierung nötig, da augenscheinlich sowohl die Perspektive des Betrachters eine Rolle spielt, als auch der Stand der Wissenschaft. Es existieren Ereignisse, von denen bewiesen werden konnte, dass sie keine kausale Ursache haben. Ein Beispiel hierfür ist der Zerfallszeitpunkt eines (radioaktiven) Atoms. Außerdem ist es möglich, dass man zwar alle Einflussfaktoren kennt, die ein Ergebnis bestimmen, diese aber weder ändern noch messen kann. Offensichtlich trifft dies bei Zufallsexperimenten zu. Betrachtet man den Wurf eines Würfels kann man sich leicht vorstellen, wovon das Ergebnis abhängt: Der angewendeten Kraft, dem Auftreffwinkel auf dem Untergrund, das Material des Untergrundes und des Würfels usw. Bevor man dies alles berücksichtigt hat, steht das Ergebnis schon fest. Dies entspricht auch dem Beispiel 1. Desweiteren kann es sein, dass die Ursache nicht erkennbar ist. Hierbei spricht man auch vom Pseudozufall.

Zufallszahlen erzeugen

Numerisch probabilistische Algorithmen

Definition

Numerisch probabilistische Algorithmen haben als Ergebnis eine Näherungslösung mit wählbarer Genauigkeit, in Folge dessen kann der Nutzer selbst durch Wahl seiner Eingaben bestimmen 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