Word RAM - Word RAM

V teoretické informatice je slovo RAM (word random-access machine) model výpočtu, což je stroj s náhodným přístupem schopný provádět bitové operace s jediným slovem w bitů. Tento model byl vytvořen Michaelem Fredman a Dan Willard v roce 1990, aby simuloval programovací jazyky jako C .

Modelka

Slovo RAM model je abstraktní stroj podobný stroji s náhodným přístupem , ale s dalšími schopnostmi. Funguje se slovy o velikosti až w bitů, což znamená, že může ukládat celá čísla až do velikosti . Neboť model předpokládá, že slovo velikost odpovídá velikosti problému, to jest na problém velikosti n , model slovo RAM je transdichotomous modelu . Model umožňuje provádět bitové operace, jako jsou aritmetické a logické posuny, v konstantním čase . Počet možných hodnot je U , kde . ${\ displaystyle 2 ^ {w}}$${\ displaystyle w \ geq \ log n}$${\ displaystyle U \ leq 2 ^ {w}}$

Algoritmy a datové struktury

V modelu RAM slovo lze třídění celých čísel provádět poměrně efektivně. Yijie Han a Mikkel Thorup vytvořili randomizovaný algoritmus pro třídění celých čísel v očekávaném čase (v Big O notaci ) , zatímco Han také vytvořil deterministickou variantu s časem běhu . ${\ displaystyle O (n {\ sqrt {\ log \ log n}})}$ ${\ displaystyle O (n \ log \ log n)}$

Problém dynamického předchůdce je také běžně analyzován ve slově RAM model a byl původní motivací pro model. Dan Willard používá y-rychlý pokusů na odstranění tohoto problému v čase. Michael Fredman a Willard také vyřešil problém s využitím fúzních stromy v čase. ${\ displaystyle O (\ log \ log U)}$${\ displaystyle O (\ log _ {w} n)}$

Viz také

• Transdichotomický model

Reference