Direkt zum Inhalt Direkt zur Navigation
Sie sind hier: Startseite Nachrichten IT/Computer Algorithmus wirft effizient gezinkte Würfel

Algorithmus wirft effizient gezinkte Würfel

Archivmeldung vom 30.05.2020

Bitte beachten Sie, dass die Meldung den Stand der Dinge zum Zeitpunkt ihrer Veröffentlichung am 30.05.2020 wiedergibt. Eventuelle in der Zwischenzeit veränderte Sachverhalte bleiben daher unberücksichtigt.

Freigeschaltet durch Thorsten Schmitt
Würfel: Virtuelles Zinken macht durchaus Sinn.
Würfel: Virtuelles Zinken macht durchaus Sinn.

Bild: Jose-Luis Olivares/mit.edu

Forscher am Massachusetts Institute of Technology (MIT) haben einen neuen Algorithmus entwickelt, der virtuelle gezinkte Würfel wirft. Der "Fast Loaded Dice Roller" (FLDR) bietet dem Team nach die derzeit beste Kombination aus Geschwindigkeit, Genauigkeit und geringer Speichernutzung. Das soll die Simulation komplexer Systeme, in denen Dinge zwar zufällig, aber nicht mit gleicher Wahrscheinlichkeit passieren, erleichtern - von der Klimaforschung über die Epidemiologie bis hin zu Finanzmärkten.

Gewichteter Zufall

Das schnelle, effiziente Generieren von Zufallszahlen ist eine der grundlegendsten Herausforderungen in der Informatik und für Computersimulationen. Oft wäre dabei eine Gewichtung sinnvoll, dass also verschiedene Zahlen mit unterschiedlicher Wahrscheinlichkeit auftreten. Wenn zum Beispiel zwei Sportteams aufeinandertreffen, gibt es nur drei mögliche Ergebnisse - aber dass das stärkere Team gewinnt, ist wahrscheinlicher als ein Überraschungssieg oder Unentschieden. Hier könnte also ein passend gezinkter Würfel am schnellsten geeignete Zufallszahlen liefern - und genau das ist die Aufgabe des FLDR.

Der Algorithmus, der kommende Woche bei der 23rd International Conference on Artificial Intelligence and Statistics näher vorgestellt wird, verspricht nämlich exakt gewichtete Ergebnisse. Das heißt: Jede einer Reihe von Zufallszahlen tritt mit genau der gewünschten Wahrscheinlichkeit auf. Das allerdings ist gar nicht das Entscheidende am neuen Algorithmus; der eigentliche Durchbruch liegt darin, wie wenig Speicherbedarf dieser hat. Eben das sollte ihn den MIT-Forschern zufolge für Simulationsanwendungen sehr interessant machen.

Kompakt und schnell

Die Informatiker Donald Knuth und Andrew Yao haben bereits 1976 einen Algorithmus vorgestellt, der gezinkte Würfel mit der größtmöglichen zeitlichen Effizienz wirft. Allerdings ist ihr Ansatz ein unglaublicher Speicherfrssser. "Wir sind fast so zeiteffizient, aber wesentlich speicherffizienter", betont MIT-Doktorand Feras Saad; einer der Entwickler des FLDR. Dieser erfordert bis zu 10.000 Mal weniger Speicher, braucht aber höchstens 1,5 Mal so lange für eine Operation. Im Vergleich zum derzeit für gewichtete Zufallszahlen gängigen Ansatz "Alias" sei FLDR etwas effizienter und bisweilen auch schneller.

Das macht den neuen Algorithmus für immer größere, komplexere Computersimulationen interessant. Denn hier gibt es oft nur eine begrenzte Zahl möglicher Ergebnisse, die nicht gleich wahrscheinlich sind. Als Beispiel verweist das MIT besonders auf Inferenz-Verfahren, wo mehrere Simulationen reale Daten erklären sollen. Das ist klarerweise rechenaufwendiger als eine einfache Simulation, kommt aber beispielsweise bei den UN zum Einsatz, um seismische Daten zu interpretieren. Zu anderen Feldern, die profitieren könnten, zählt die dank COVID-19 ins Rampenlicht geratene Epidemiologie.

Quelle: www.pressetext.com/Thomas Pichler

Videos
Symbolbild
... Und wenn Dein Körper das kleine Corona Problem schon selbst erledigt hat?
Vernon Coleman 2019
Dr. Vernon Coleman: „Das könnte unmöglich passieren! Oder doch?“
Termine
Das Ende der Pandemie - Der Tag der Freiheit / Lockdown-Großdemo
Berlin
01.08.2020
Newsletter
Wollen Sie unsere Nachrichten täglich kompakt und kostenlos per Mail? Dann tragen Sie sich hier ein:
Schreiben Sie bitte elend in folgendes Feld um den Spam-Filter zu umgehen

Anzeige