RAM Worda

W informatyce teoretycznej model słowa RAM (maszyna o swobodnym dostępie słów) jest modelem obliczeniowym , w którym maszyna o swobodnym dostępie wykonuje operacje bitowe na słowie złożonym z w bitów. Michael Fredman i Dan Willard stworzyli go w 1990 roku, aby symulować języki programowania, takie jak C .

Model

Model Word RAM to abstrakcyjna maszyna podobna do maszyny o swobodnym dostępie , ale z dodatkowymi możliwościami. Działa ze słowami o rozmiarze do w bitów, co oznacza, że ​​może przechowywać liczby całkowite do rozmiaru ${\ displaystyle 2 ^ {w}}$ . Ponieważ model zakłada, że ​​rozmiar słowa odpowiada rozmiarowi problemu, to znaczy dla problemu o rozmiarze n , ${\ Displaystyle w \ geq \ log n$ } model transdychotomiczny . Model umożliwia wykonywanie operacji bitowych , takich jak przesunięcia arytmetyczne i logiczne, w stałym czasie . Liczba możliwych wartości to U , gdzie ${\ Displaystyle U \ równoważnik 2 ^ {w}}$ .

Algorytmy i struktury danych

W słownym modelu RAM sortowanie liczb całkowitych można przeprowadzić dość wydajnie. Yijie Han i Mikkel Thorup stworzyli losowy algorytm do sortowania liczb całkowitych w oczekiwanym czasie (w notacji Big O ) ${\ Displaystyle O (n {\ sqrt {\ log \ log n}})}$ , podczas gdy Han stworzył również wariant deterministyczny z czasem działania ${\ Displaystyle O (n \ log \ log n)}$ .

Dynamiczny problem poprzednika jest również powszechnie analizowany w słownym modelu RAM i był pierwotną motywacją dla modelu. Dan $_$ użył prób rozwiązania w Michael Fredman i Willard również rozwiązali problem za pomocą drzew fuzyjnych w ${\ Displaystyle O (\ log _ {w} n)}$ czas.

Zobacz też

• Model transdychotomiczny