Das Kefk Network Wiki befindet sich im Testbetrieb.

---

Aus Kefk.

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Pseudozufall, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.

Als Pseudozufall wird bezeichnet, was zufällig erscheint, in Wirklichkeit jedoch berechenbar ist.

Inhaltsverzeichnis 1 Pseudozufallszahlen 1.1 Güte eines Pseudozufallszahlengenerators 1.2 Verwendung von Pseudozufallszahlen 1.3 Nicht-periodischer/unendlicher Generator 2 Pseudozufall in der Berechenbarkeitstheorie 3 Siehe auch 4 Weblinks

Pseudozufallszahlen

Die wichtigste Anwendung von Pseudozufallszahlen sind die so genannten Zufallsgeneratoren, die in praktisch allen Programmiersprachen verfügbar sind. Dass es sich dabei meist lediglich um Pseudozufallszahlengeneratoren (engl. PRNG, pseudo random number generator) handelt, wird häufig übersehen. Sie erzeugen eine Zahlenfolge, die zwar zufällig aussieht, es aber nicht wirklich 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 bestimmte Eigenschaften echter Zufallszahlen, sind jedoch von Computern wesentlich einfacher herzustellen.

Güte eines Pseudozufallszahlengenerators

Die 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.

Meist werden periodische Zahlenfolgen erzeugt, die gleichen Zahlen wiederholen sich also nach einer bestimmten Länge. Ihr Vorteil ist die hohe Geschwindigkeit. Durch geschickte Wahl der Parameter kann man die Periode genügend groß machen. Einige Pseudozufallszahlengeneratoren generieren nur endliche Zahlenfolgen.

Die bedeutendsten Pseudozufallszahlengeneratoren sind rekursive arithmetische Zufallszahlengeneratoren.

Verwendung von Pseudozufallszahlen

Pseudozufallszahlen finden u. a. Anwendung

• in der Computersimulation, bei der statistische Prozesse mit Hilfe von Software simuliert werden (Monte-Carlo-Simulation)
• bei der Fehlersuche in Computerprogrammen
• bei der künstlichen Erzeugung von Rauschen
• in der Spreizspektrum-Technik

Unangebracht ist das Nutzen von Pseudozufallszahlen in Bereichen, wo echter Zufall vonnöten ist. Zur Erzeugung echter Zufallszahlen benötigt man entweder einen echten Zufallsgenerator (z. B. durch Digitalisieren von Rauschen oder durch Ausnutzen von Quanteneffekten) oder zumindest eine Quelle quasizufälliger (normalerweise nicht vorhersagbarer) Ereignisse wie Zeiten von Benutzereingaben oder Netzwerkaktivität.

Nicht-periodischer/unendlicher Generator

Man 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 gilt. Klassischerweise kann man statt 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 Parser-Fehler (Unbekannter Fehler\tfrac): \tfrac{f_1}{f_2}

eine irrationale Zahl ist, also nf1 = nf2 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 f1 erzeugtes Pseudozufallssignal, das mit der Frequenz f2 abgetastet/eingelesen wird.

Pseudozufall in der Berechenbarkeitstheorie

In der Berechenbarkeitstheorie wird alles das als pseudozufällig bezeichnet, was durch den Betrachter nicht von wirklicher Zufälligkeit unterschieden werden kann. Das Ergebnis eines Münzwurfs wird beispielsweise generell als zufällig angesehen. Befindet sich die Münze bereits in der Luft, ist es theoretisch möglich, anhand ihrer Rotation, Geschwindigkeit usw. das Ergebnis vorherzusagen. Jemandem, dem entsprechende Messgeräte (und Rechenkapazität) nicht zur Verfügung stehen, erscheint der Wurf aber immer noch zufällig; der Wurf mit der Münze in der Luft ist für ihn pseudozufällig. Generell definiert man in der Berechenbarkeitstheorie als pseudozufällig, was durch effiziente Algorithmen nicht vorhergesagt werden kann. Pseudozufälligkeit ist aber immer noch berechenbar (man kann sie effizient erzeugen), nur nicht vorhersagbar. Pseudozufallsgeneratoren nach dieser Definition von Pseudozufälligkeit setzen die Existenz expliziter harter Funktionen voraus.

Siehe auch

• Zufall, Zufallsgenerator

Weblinks

• Ausführliche Bearbeitung des Themas Pseudozufallszahlengenerator (englisch)
• Vorlesungsskript zum Thema Pseudozufallszahlen

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Pseudozufall, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.