Anzeigegulli:Toolbox |
gulli:lexikon » Zufallszahlengenerator
gulli:lexikon - Alle Begriffe der Untergrund-SzeneTipp: Benutze die Suche, um weitere Begriffe im gulli:lexikon nachzuschlagen. {{ #ifeq: | | }}
}} Als Zufallszahlengenerator, gelegentlich auch zu Zufallsgenerator oder schlicht Generator verkürzt, bezeichnet man ein Verfahren, das eine Folge von Zufallszahlen erzeugt. Der Bereich, aus dem die Zufallszahlen erzeugt werden, hängt dabei vom speziellen Zufallszahlengenerator ab. Es kann beispielsweise die Menge aller 32-Bit-Zahlen oder auch die Menge der reellen Zahlen im Intervall [0,1] sein. Meistens ist von einem Zufallszahlengenerator erwünscht, dass er gleichverteilte Werte aus dem jeweiligen Bereich erzeugt. Für gewisse statistische Simulationen sind auch solche Zufallszahlengeneratoren interessant, die eine vorgegebene Verteilung (z. B. Normalverteilung oder Poissonverteilung) erzeugen. Zufallszahlen werden unter anderem bei verschiedenen Methoden der Statistik benötigt, z. B. bei der Auswahl einer Stichprobe aus einer Grundgesamtheit, bei der Verteilung von Versuchstieren auf verschiedene Versuchsgruppen (Randomisierung) oder bei der Monte-Carlo-Simulation. Typische weitere Anwendungsgebiete sind (Computer-, Glücks-) Spiele und diverse Kryptographieverfahren. Man unterscheidet grundsätzlich zwischen nicht-deterministischen und deterministischen Zufallszahlengeneratoren. Nicht-deterministisch ist ein Zufallszahlengenerator dann, wenn er auch bei gleichen Ausgangsbedingungen unterschiedliche Werte liefert. Da die Implementierung einer Software-Prozedur immer deterministisch arbeitet, muss zur Realisierung eines nicht-deterministischen Zufallszahlengenerators ein externer, beispielsweise ein physikalischer, Vorgang einbezogen werden. Ein deterministischer Zufallszahlengenerator liefert bei gleichen Ausgangsbedingungen dagegen immer die gleiche Folge von Zahlen. Oft werden beide Formen zu einem hybriden Generator kombiniert.
Nichtdeterministische ZufallszahlengeneratorenPhysikalischer ZufallszahlengeneratorBeispielsweise kann ein Geigerzähler die Zahl der radioaktiven Zerfälle in einer bestimmten Zeitspanne messen. Man nutzt die Tatsache, dass radioaktive Isotope nach einer rein zufälligen Zeitspanne in das Tochterelement bzw. -isotop zerfallen. Die Zeitspanne hat aber beim gleichen Isotop immer den gleichen Mittelwert (die sogenannte Halbwertszeit). Da der radioaktive Zerfall unabhängig von Umgebungsbedingungen abläuft, kann dieser Vorgang Zufallszahlen hoher Güte liefern. Eine weitere Methode zum Aufbau von Zufallsgeneratoren in digitalen Schaltungen besteht in der Ausnützung der Metastabilität bei taktflankengesteuerten Flipflops <ref>D.J. Kinniment, et al: Design of an on–chip random number generator using metastability, Proceedings of the 28th European Solid-State Circuits Conference, 24. bis 26. Sept. 2002, Seiten 595 bis 598</ref>. Bei physikalischen Zufallszahlengeneratoren gibt es allerdings das Problem der Alterung. Beispielsweise haben Geiger-Müller-Zählrohre eine Lebensdauer von typischerweise einer Billion Pulse und sind zudem abhängig von Temperatur, Magnetfeldern und der Versorgungsspannung. Zudem muss bei Geigerzählern die Pulsrate „deutlich höher“ als die Taktfrequenz sein, mit der die Pulse eingelesen werden. Eine Lösung dieses Problems ist viele mehr oder minder gute Zufallszahlengeneratoren zu nehmen und von diesen Zufallszahlen nur das letzte Bit zu verwenden um damit die Modulo-Zwei-Summe zu bilden. Nach dem zentralen Grenzwertsatz der Statistik erhält man damit auch mit schlechten Zufallszahlengeneratoren perfekt zufällige Zufallsbits, wenn man nur genügend viele Zufallszahlengeneratoren verwendet. Quasizufällige EreignisseEs wird beispielsweise die Systemzeit bestimmt, in der eine Benutzeraktion eintritt. Auf diese Weise erzeugte Zufallszahlen haben meist eine geringe Güte, lassen sich aber als Startwert für deterministische Verfahren verwenden. Deterministische ZufallszahlengeneratorenDeterministische Zufallszahlengeneratoren erzeugen Pseudozufallszahlen und werden daher in der Regel Pseudozufallszahlengeneratoren genannt (engl. PRNG, pseudo random number generator). Sie erzeugen eine Zahlenfolge, die zwar zufällig aussieht, es aber nicht ist, da sie durch einen deterministischen Algorithmus berechnet wird. Bei jedem Start der Zufallszahlenberechnung mit gleichem Startwert, der so genannten Saat (engl. seed), wird die gleiche pseudozufällige Zahlenfolge erzeugt. Sie verletzen damit Eigenschaften echter Zufallszahlen, sind jedoch von Computern wesentlich einfacher zu erzeugen. Sie sind in praktisch allen Programmiersprachen verfügbar. Dass es sich bei diesen Implementationen lediglich um Generatoren handelt, die pseudozufällige Zahlen (von oftmals nur geringer Güte) erzeugen, wird häufig übersehen. Des weiteren vorteilhaft ist, dass diese deterministisch erzeugten Pseudozufallszahlen bei hinreichend genauer Dokumentation später reproduziert werden können. Diese Eigenschaft der Reproduzierbarkeit ist bedeutsam für die Anerkennung wissenschaftlicher Experimente. Güte eines PseudozufallszahlengeneratorsDie erzeugten Zahlen werden durch statistische Eigenschaften charakterisiert. Dazu gehört die erzeugte Verteilung (z. B. Normalverteilung, Gleichverteilung, Exponentialverteilung etc.) oder die Unabhängigkeit aufeinanderfolgender Zahlen. Wie gut die erzeugten Zahlen den statistischen Vorgaben entsprechen, bestimmt die Güte eines Pseudozufallszahlengenerators. Besonders strenge Anforderungen werden an kryptographisch sichere Zufallszahlengeneratoren gestellt. Nicht-periodischer/unendlicher GeneratorMan nehme die Nachkommastellen einer Wurzel einer ganzen Zahl als Zufallszahlen. Hierbei ist selbstverständlich darauf zu achten, dass die resultierende Wurzel eine irrationale Zahl ist, das heißt, dass <math>\sqrt{n}\notin \mathbb{Q}</math> gilt, was immer der Fall ist, wenn die Wurzel keine ganze Zahl ist. Klassischerweise kann man statt <math>\sqrt{n}</math> auch die Kreiszahl Pi verwenden. Aufgrund der endlichen Speicherkapazität eines Computers kann es in der Praxis jedoch keinen nicht-periodischen deterministischen Zufallszahlengenerator geben. Möglich sind aber nicht-periodische deterministische Zufallszahlengeneratoren mit zwei Takt-Generatoren, deren Takte inkommensurabel sind; wenn also deren Frequenzverhältnis <math>\tfrac{f_1}{f_2}</math> eine irrationale Zahl ist, also <math>n_1*f_1 = n_2*f_2</math> nicht erfüllt wird. Weil unter den reellen Zahlen die rationalen Zahlen eine Lebesgue-Nullmenge bilden, ist dies praktisch immer der Fall und damit ein aus beiden Takten generiertes Signal nichtperiodisch. Ein Beispiel hierfür ist ein mit der Frequenz <math>f_1</math> erzeugtes Pseudozufallssignal, das mit der Frequenz <math>f_2</math> abgetastet/eingelesen wird. Softwaretechnische Realisierungen
Hardwaretechnische Realisierungen
Hybride GeneratorenPseudozufallszahlengeneratoren, die als Input einige wenige echte Zufallszahlen verwenden, also nicht nur Pseudozufallszahlen erzeugen. Ein Beispiel hierfür ist Sonstige Zufallszahlengeneratoren
Siehe auchEinzelnachweise<references/> Weblinks
en:Random number generation es:Generador de números aleatorios fr:Générateur de nombres aléatoires nl:Toevalsgenerator pl:Generator liczb losowych sv:Slumptalsgenerator ur:تصادفی عدد مولّد zh:随机数发生器 Dieser Artikel basiert auf dem Artikel Zufallszahlengenerator aus der freien Enzyklopädie Wikipedia und steht unter der GNU-Lizenz für freie Dokumentation. In der Wikipedia ist eine Liste der Autoren verfügbar. 
 |
Weitere Tipps |
gulli news abonnieren
news feed
suchbox
banner & buttons