Word RAM - Word RAM

I teoretisk datavetenskap är ordet RAM (ord random-access machine) en beräkningsmodell som är en random-access-maskin som kan utföra bitvisa operationer på ett enda ord av w- bitar. Modellen skapades av Michael Fredman och Dan Willard 1990 för att simulera programmeringsspråk som C .

Modell

Ordet RAM-modell är en abstrakt maskin som liknar en random-access-maskin , men med ytterligare funktioner. Det fungerar med ord med storlek upp till w bitar, vilket innebär att den kan lagra heltal upp till storlek . Eftersom modellen antar att ordstorleken matchar problemstorleken, det vill säga för ett problem med storlek n , är ordet RAM-modell en transdikotom modell . Modellen gör att bitvisa operationer som aritmetik och logiska skift kan göras i konstant tid . Antalet möjliga värden är U , var . ${\ displaystyle 2 ^ {w}}$${\ displaystyle w \ geq \ log n}$${\ displaystyle 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 (i Big O-notering ) , medan Han också skapade en deterministisk variant med körtid . ${\ displaystyle O (n {\ sqrt {\ log \ log n}})}$ ${\ displaystyle O (n \ log \ log n)}$

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

Se även

• Transdikotom modell

Referenser