RAM de palabras

En informática teórica , el modelo de palabra RAM (máquina de acceso aleatorio de palabras) es un modelo de computación en el que una máquina de acceso aleatorio realiza operaciones aritméticas y bit a bit en una palabra de $w$ bits. Michael Fredman y Dan Willard lo crearon en 1990 para simular lenguajes de programación como C. ^[1]

Modelo

El modelo de RAM de palabras es una máquina abstracta similar a una máquina de acceso aleatorio , pero con memoria y longitud de palabras finitas. Funciona con palabras de hasta $w$ bits, lo que significa que puede almacenar números enteros de hasta . Debido a que el modelo supone que el tamaño de la palabra coincide con el tamaño del problema, es decir, para un problema de tamaño $n$ , el modelo de RAM de palabras es un modelo transdicotómico . ^[2] El modelo permite realizar operaciones aritméticas y operaciones bit a bit , incluidos cambios lógicos , en tiempo constante (el conjunto de instrucciones preciso asumido por un algoritmo o prueba que utiliza el modelo puede variar). $2^{w}-1$ $w\geq \log n$

Algoritmos y estructuras de datos.

En el modelo de RAM de palabras, la clasificación de números enteros se puede realizar de manera bastante eficiente. Yijie Han y Mikkel Thorup crearon un algoritmo aleatorio para ordenar números enteros en el tiempo esperado (en notación O grande ) , ^[3] mientras que Han también creó una variante determinista con tiempo de ejecución . ^[4] $O(n{\sqrt {\log \log n}})$ $O(n\log \log n)$

El problema del predecesor dinámico también se analiza comúnmente en el modelo de RAM y fue la motivación original del modelo. Dan Willard utilizó intentos y-fast para resolver esto en el tiempo o, más precisamente, donde $U$ es un límite de los valores almacenados. ^[5]Michael Fredman y Willard también resolvieron el problema utilizando árboles de fusión a tiempo. ^[1] Utilizando árboles de búsqueda exponenciales , se puede realizar una consulta en . ^[6] $O(\log w)$ $O(\log \log U)$ ${\ Displaystyle O (\ log _ {w} n)}$ $O({\sqrt {\log n/\log \log n}})$

Resultados adicionales en la palabra modelo RAM se enumeran en el artículo sobre búsqueda de rango .

Los límites inferiores aplicables a los algoritmos de RAM de palabras a menudo se demuestran en el modelo de sonda celular .

Ver también

Modelo transdicotómico

Referencias

^ ab Fredman, Michael ; Willard, Dan (1990). "Atravesando la barrera de la teoría de la información con árboles de fusión". Simposio sobre teoría de la informática : 1–7.
^ De hecho, normalmente se supone que $n$ es menor que , de modo que la estructura de datos considerada puede indexarse con direcciones $de w bits.$ $2^{w}$
^ Han, Yijie; Thorup, M. (2002), "Clasificación de enteros en $O ($ $n$ $\sqrt$ $log log$ $n$ $)$ tiempo esperado y espacio lineal", Actas del 43º Simposio anual sobre fundamentos de la informática (FOCS 2002) , IEEE Computer Society, págs.135 –144, CiteSeerX 10.1.1.671.5583 , doi :10.1109/SFCS.2002.1181890, ISBN 978-0-7695-1822-0
^ Han, Yijie (2004), "Clasificación determinista en $O$ $($ $n$ $log log$ $n$ $)$ tiempo y espacio lineal", Journal of Algorithms , 50 (1): 96–105, doi :10.1016/j.jalgor.2003.09.001, Señor 2028585
^ Willard, Dan E. (1983). "Las consultas de rango logarítmico logarítmico en el peor de los casos son posibles en el espacio Θ (N)". Cartas de procesamiento de información . 17 (2): 81–84.
^ Andersson, Arne; Thorup, Mikkel (2007). "Conjuntos ordenados dinámicos con árboles de búsqueda exponenciales". Revista de la ACM . 54 (3): 1–40. arXiv : cs/0210006 . doi :10.1145/1236457.1236460.