Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


35. Zufallszahlen



Anwendungen

Wir haben in diesem Buch bereits viele Anwendungen kennengelernt, in denen Zufallszahlen von Nutzen sind. Einige von ihnen umreißen wir hier. Eine offensichtliche Anwendung liegt in der Kryptographie, wo das Hauptziel darin besteht, eine Nachricht so zu verschlüsseln, daß sie von niemandem außer von dem vorgesehenen Empfänger gelesen werden kann. Wie wir in Kapitel 23 gesehen haben, besteht ein Weg, dies zu erreichen, darin, die Nachricht zufällig aussehen zu lassen, indem man eine pseudo-zufällige Folge verwendet, um die Nachricht so zu verschlüsseln, daß der Empfänger die gleiche pseudo-zufällige Folge für ihre Entschlüsselung benutzen kann.

Ein weiteres Gebiet, in dem Zufallszahlen breite Anwendung gefunden haben, ist die Simulation. Eine typische Simulation beinhaltet ein umfangreiches Programm, welches einen bestimmten Aspekt der realen Welt modelliert: Zufallszahlen eignen sich in natürlicher Weise für die Eingabe solcher Programme. Selbst dann, wenn keine echten Zufallszahlen benötigt werden, werden für Simulationen gewöhnlich viele beliebige Zahlen für die Eingabe benötigt, und es ist zweckmäßig, diese mit Hilfe eines Zufallszahlengenerators zur Verfügung zu stellen.

Wenn eine große Datenmenge analysiert werden soll, ist es manchmal ausreichend, nur eine sehr kleine Teilmenge dieser Daten zu verarbeiten, welche durch die Entnahme einer zufälligen Stichprobe ausgewählt wird. Entsprechende Anwendungen sind weit verbreitet, wobei das bekannteste Beispiel Meinungsumfragen sein dürften.

Oft ist es erforderlich, eine Auswahl zu treffen, wenn alle zu berücksichtigenden Faktoren gleich zu sein scheinen. Die Lottozahlen oder die Vergabe von Studienplätzen an Gleichberechtigte sind Beispiele für die Verwendung von Zufallszahlen für die Entscheidungsfindung. Auf diese Weise wird die Verantwortung für die Entscheidung dem »Schicksal« (oder dem Computer) übertragen.

Der Leser wird sicher feststellen, daß er selbst häufig von die Simulation von Zufallszahlen Gebrauch macht: um zufällige oder beliebige Eingabedaten für Programme bereitzustellen. Eine andere Anwendung, die wir kennengelernt haben, betrifft Algorithmen, deren Effizienz sich dadurch erhöht, daß sie Zufallszahlen zur Entnahme von Stichproben oder als Hilfsmittel bei der Entscheidungsfindung verwenden. Ausgezeichnete Beispiele dafür sind Quicksort (siehe Kapitel 9) und das Verfahren von Rabin-Karp für die Suche in Zeichenfolgen (siehe Kapitel 19).


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]