________________________________________________________________________________
Inhalt....: Erzeugung und Testen von Zufall
Kategorie.: Arbeitsblatt
Mathematik: Stochastik, Statistik
MuPAD.....: 3.0.0
Datum.....: 2002-01-17
Autoren...: Julia Falek <faflek@upb.de>
Funktionen: mod, plot, plot::Point2d, Color,
________________________________________________________________________________
Selbstgemachter Zufall?
Der lineare Kongruenzgenerator
Hier soll gezeigt werden, wie man selbst Zufall erzeugen kann und wie man erkennen kann,
ob die so erzeugten Zahlen auch wirklich zufällig aussehen. Hier möge man sich an die wichtige
gen der Kryptographie erinnern.
Wir definieren zunächst folgende Berechnungsvorschrift:
Damit ist festgelegt, dass die erzeugten Zahlen nur zwischen 0 und n-1 liegen
können.
Wie zufällig die berechneten Zahlen aussehen, hängt von der Wahl der
Parameter ab. Wir definieren nun eine Prozedur, die uns eine Ausgabe der
Länge m eines linearen Kongruenzgenerators für beliebige Parameter a, b,
n und x0 berechnet.
LKG := proc(x0, a, b, n, m)
local x, i;
begin
x := [0 $ m];
x[1] := x0;
for i from 2 to m do
x[i] := a * x[i-1] + b mod n;
end_for;
return(x);
end_proc:
Übergeben wir der Prozedur nun die Saat x0 = 1 und die Parameter a = 2,
b = 3, n = 13, so erhalten wir folgende Ausgabe.
LKG(1, 2, 3, 13, 30)
Wir können erkennen, dass die Folge zyklisch ist, d.h. nach jeweils 12
Zahlen wiederholen sich die Zahlen in gleicher Reihenfolge. Damit ist klar,
dass diese Wahl der Parameter nicht sehr glücklich war.
Schaut man kurz auf die ausgegebene Liste der Zahlen, so erkennt man
sofort, dass die Folge berechnet worden und keinesfalls zufällig ist. Ein
besseres Ergebnis erhält man bei Eingabe der folgenden Parameter:
LKG(143, 1896, 467, 1301, 30)
Diese Zahlenfolge sieht zufällig aus. Die so erzeugten Pseudozufalls-
zahlen zwischen 0 und 1300 werden nun zu Pseudozufallszahlen aus dem
Intervall [0, 1[ transformiert, indem wir jedes Listenelement durch 1301 teilen.
Wir wollen graphisch veranschaulichen, wie zufällig diese transformierten
Zahlen tatsächlich sind.
L := LKG(143, 1896, 467, 1301, 500):
Punkte := [0 $ 499]:
for i from 1 to 499 do
Punkte[i] := plot::Point2d(L[i]/1301, L[i+1]/1301, Color = RGB::Black);
end_for:
plot(op(Punkte), Color = RGB::Black)
Die Punkte scheinen ziemlich gleichverteilt im Einheitsquadrat zu liegen.
Wir nehmen daher an, dass der lineare Kongruenzgenerator mit obigen
Parametern ziemlich „guten" Zufall simuliert.
Zum Vergleich stellen wir auch den ersten Generator mit den Parametern
a = 2, b = 3 und n = 13 graphisch dar:
L := LKG(1,2,3,13,500):
Punkte := [0 $ 499]:
for i from 1 to 499 do
Punkte[i] := plot::Point2d(L[i]/13, L[i+1]/13, Color = RGB::Black);
end_for:
plot(op(Punkte), Color = RGB::Black)
Die Punkte liegen auf drei parallelen Geraden -- keine gute Wahl, denn
wer wird schon behaupten, dass diese Punkte zufällig sind.
_______________________________________________________________________________
Anmerkungen:
1. Weitere Anregungen finden Sie in der Buchreihe Mathematik 1 x anders. In dieser Reihe
wird eine Vielzahl unterschiedlichster mathematischer Probleme mit MuPAD gelöst. Die
Bücher können unter www.schule.mupad.de/literatur kostenfrei kopiert werden.
_______________________________________________________________________________