Ordet RAM

Inom teoretisk datavetenskap är ordet RAM- modellen (ordet random-access machine) en beräkningsmodell där en random-access-maskin utför bitvisa operationer på ett ord med w bitar. Michael Fredman och Dan Willard skapade den 1990 för att simulera programmeringsspråk som C .

Modell

Ordet RAM-modell är en abstrakt maskin som liknar en maskin med slumpmässig åtkomst, men med ytterligare möjligheter. Den fungerar med ord i storlek upp till w bitar, vilket betyder att den kan lagra heltal upp till storlek $2^{w}$ . Eftersom modellen antar att ordstorleken matchar problemstorleken, det vill säga för ett problem av storlek n , $w\geq \log n$ , är ordet RAM-modell en transdikotom modell . Modellen tillåter bitvisa operationer som aritmetiska och logiska skift att utföras i konstant tid . Antalet möjliga värden är U , där $U\leq 2^{w}$ .

Algoritmer och datastrukturer

I ordet RAM-modell kan heltalssortering göras ganska effektivt. Yijie Han och Mikkel Thorup skapade en randomiserad algoritm för att sortera heltal i förväntad tid av (i Big O notation ) $O(n{\sqrt {\log \log n}})$ , medan Han också skapade en deterministisk variant med körtid $O(n\log \log n)$ .

Problemet med dynamiska föregångare analyseras också ofta i ordet RAM-modell och var den ursprungliga motivationen för modellen. Dan Willard använde y-fast försök att lösa detta i $O(\log \log U)$ tid. Michael Fredman och Willard löste också problemet med hjälp av fusionsträd i ${\displaystyle O(\log _{w}n)}-$ tid.

Se även

• Transdikotom modell