Word RAM - Word RAM

In der theoretischen Informatik ist das Wort-RAM -Modell (Word Random-Access Machine) ein Berechnungsmodell , bei dem es sich um eine Direktzugriffsmaschine handelt , die bitweise Operationen an einem einzelnen Wort von w Bits ausführen kann . Das Modell wurde 1990 von Michael Fredman und Dan Willard entwickelt , um Programmiersprachen wie C zu simulieren .

Modell

Das Wort RAM-Modell ist eine abstrakte Maschine , die einer Maschine mit wahlfreiem Zugriff ähnelt , jedoch zusätzliche Funktionen bietet. Es funktioniert mit Wörtern mit einer Größe von bis zu w Bits, was bedeutet, dass ganze Zahlen bis zu einer Größe gespeichert werden können . Da das Modell davon ausgeht, dass die Wortgröße mit der Problemgröße übereinstimmt, dh für ein Problem der Größe n , ist das Wort-RAM-Modell ein transdichotomes Modell . Das Modell ermöglicht bitweise Operationen wie arithmetische und logische Verschiebungen in konstanter Zeit . Die Anzahl der möglichen Werte ist U , wobei . ${\ displaystyle 2 ^ {w}}$${\ displaystyle w \ geq \ log n}$${\ displaystyle U \ leq 2 ^ {w}}$

Algorithmen und Datenstrukturen

Im Wort-RAM-Modell kann die Ganzzahlsortierung ziemlich effizient durchgeführt werden. Yijie Han und Mikkel Thorup erstellten einen randomisierten Algorithmus zum Sortieren von ganzen Zahlen in der erwarteten Zeit von (in Big O-Notation ) , während Han auch eine deterministische Variante mit Laufzeit erstellte . ${\ displaystyle O (n {\ sqrt {\ log \ log n}})}$ ${\ displaystyle O (n \ log \ log n)}$

Das dynamische Vorgängerproblem wird auch häufig im Wort RAM-Modell analysiert und war die ursprüngliche Motivation für das Modell. Dan Willard verwendet y-schnell versucht dies in zu lösen Zeit. Michael Fredman und Willard gelöst auch das Problem mit Fusion Bäume in der Zeit. ${\ displaystyle O (\ log \ log U)}$${\ displaystyle O (\ log _ {w} n)}$

Siehe auch

• Transdichotomes Modell

Verweise