RAM de palabras

En informática teórica , el modelo de máquina de acceso aleatorio ( RAM ) es un modelo de computación en el que una máquina de acceso aleatorio realiza operaciones aritméticas y de bits 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 finita y longitud de palabra. Funciona con palabras de tamaño 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 que tanto las operaciones aritméticas como las operaciones bit a bit, incluidos los desplazamientos lógicos, se realicen en tiempo constante (el conjunto de instrucciones preciso asumido por un algoritmo o una prueba que utilice el modelo puede variar). $Estilo de visualización 2^{w}-1$ $w\geq \log n$

Algoritmos y estructuras de datos

En el modelo de Word RAM, la ordenación de números enteros se puede realizar con bastante eficiencia. Yijie Han y Mikkel Thorup crearon un algoritmo aleatorio para ordenar números enteros en un tiempo esperado de (en notación Big O ) ^[3] , mientras que Han también creó una variante determinista con un tiempo de ejecución de . ^[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 Word RAM y fue la motivación original para el modelo. Dan Willard usó y-fast para intentar resolver esto en el tiempo o, más precisamente, donde $U$ es un límite en los valores almacenados. ^[5]Michael Fredman y Willard también resolvieron el problema usando árboles de fusión en el tiempo. ^[1] Usando árboles de búsqueda exponencial , se puede realizar una consulta en . ^[6] $O(\log w)$ $O(\log \log U)$ $O(\log _{w}n)$ $O({\sqrt {\log n/\log \log n}})$

Resultados adicionales en el modelo de palabra 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 prueban en el modelo de sonda celular .

Véase también

Modelo transdicotómico

Referencias

^ ab Fredman, Michael ; Willard, Dan (1990). "Superando la barrera de la teoría de la información con árboles de fusión". Simposio sobre teoría de la computación : 1–7.
^ De hecho, generalmente se supone que $n$ es menor que , de modo que la estructura de datos considerada se puede indexar con direcciones $de w$ bits. $Estilo de visualización 2^{w}}$
^ Han, Yijie; Thorup, M. (2002), "Ordenamiento de enteros en tiempo esperado y espacio lineal $O($ $n$ $\sqrt$ $log log$ $n$ $) ",$ 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), "Ordenamiento determinista en tiempo $O$ $($ $n$ $log log$ $n$ $)$ y espacio lineal", Journal of Algorithms , 50 (1): 96–105, doi :10.1016/j.jalgor.2003.09.001, MR 2028585
^ Willard, Dan E. (1983). "Las consultas de rango log-logarítmicas en el peor de los casos son posibles en el espacio Θ (N)". Information Processing Letters . 17 (2): 81–84.
^ Andersson, Arne; Thorup, Mikkel (2007). "Conjuntos ordenados dinámicos con árboles de búsqueda exponencial". Revista de la ACM . 54 (3): 1–40. arXiv : cs/0210006 . doi :10.1145/1236457.1236460.