RAM real

En informática, especialmente en geometría computacional , una RAM real ( máquina de acceso aleatorio ) es un modelo matemático de una computadora que puede realizar cálculos con números reales exactos en lugar de los números binarios de punto fijo o punto flotante que utilizan la mayoría de las computadoras actuales. La RAM real fue formulada por Michael Ian Shamos en su tesis doctoral de 1978. ^[1]

Modelo

La parte "RAM" del nombre del modelo de RAM real significa " máquina de acceso aleatorio ". Se trata de un modelo de computación que se asemeja a una versión simplificada de una arquitectura de computadora estándar. Consiste en un programa almacenado , una unidad de memoria de computadora que consiste en una matriz de celdas y una unidad central de procesamiento con un número limitado de registros . Cada celda de memoria o registro puede almacenar un número real. Bajo el control del programa, la RAM real puede transferir números reales entre la memoria y los registros, y realizar operaciones aritméticas sobre los valores almacenados en los registros.

Las operaciones permitidas incluyen normalmente la suma, la resta, la multiplicación y la división, así como las comparaciones, pero no el módulo ni el redondeo a números enteros. La razón para evitar el redondeo de números enteros y las operaciones de módulo es que permitir estas operaciones podría dar a la RAM real cantidades irrazonables de potencia computacional, lo que le permitiría resolver problemas PSPACE-completos en tiempo polinomial. ^[2]

Al analizar algoritmos para la RAM real, generalmente se supone que cada operación permitida toma un tiempo constante .

Implementación

Se han desarrollado bibliotecas de software como LEDA que permiten a los programadores escribir programas informáticos que funcionan como si se estuvieran ejecutando en una RAM real. Estas bibliotecas representan valores reales utilizando estructuras de datos que les permiten realizar operaciones aritméticas y comparaciones con los mismos resultados que produciría una RAM real. Por ejemplo, en LEDA, los números reales se representan utilizando el leda_realtipo de datos, que admite raíces k -ésimas para cualquier número natural k , operadores racionales y operadores de comparación. ^[3] El análisis temporal del algoritmo de RAM real subyacente que utiliza estos tipos de datos reales se puede interpretar como un recuento del número de llamadas a la biblioteca que necesita un algoritmo determinado. ^[4]

Comparación con otros modelos computacionales

En el modelo de la máquina de Turing , la unidad básica de cálculo implica un bit. Por lo tanto, la complejidad temporal y espacial de los algoritmos numéricos depende de la cantidad de bits necesarios para representar los números. En contraste, en el modelo de RAM real, la unidad básica de cálculo implica un número real, independientemente de cuántos bits se requieran para representarlo. Esta diferencia es importante cuando se analizan algoritmos como la eliminación gaussiana : este algoritmo requiere un número polinomial de operaciones aritméticas sobre números reales, por lo que es polinomial en el modelo de RAM real; sin embargo, los números utilizados en los cálculos intermedios pueden (si se implementan de manera ingenua) crecer exponencialmente, por lo que su tiempo de ejecución en el modelo de la máquina de Turing es exponencial. ^[5]^{: Sec.1.4}
La RAM real se parece mucho a la posterior máquina Blum–Shub–Smale . ^[6] Sin embargo, la RAM real se utiliza normalmente para el análisis de algoritmos concretos en geometría computacional , mientras que la máquina Blum–Shub–Smale forma la base para las extensiones de la teoría de NP-completitud al cálculo de números reales.
Una alternativa a la RAM real es la RAM de palabras , en la que se supone que tanto las entradas de un problema como los valores almacenados en la memoria y los registros son números enteros con un número fijo de bits. El modelo de RAM de palabras puede realizar algunas operaciones más rápidamente que la RAM real; por ejemplo, permite algoritmos rápidos de ordenamiento de números enteros , mientras que el ordenamiento en la RAM real debe realizarse con algoritmos de ordenamiento por comparación más lentos . Sin embargo, algunos problemas de geometría computacional tienen entradas o salidas que no se pueden representar exactamente utilizando coordenadas enteras; véase, por ejemplo, la configuración de Perles , una disposición de puntos y segmentos de línea que no tiene representación en coordenadas enteras.

Referencias

^ Shamos, Michael Ian (1978), Geometría computacional , tesis doctoral, Universidad de Yale.
^ Schönhage, Arnold (1979), "Sobre el poder de las máquinas de acceso aleatorio", Actas del Sexto Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP '79) , Lecture Notes in Computer Science , vol. 71, Springer, págs. 520–529, doi :10.1007/3-540-09510-1_42, ISBN 978-3-540-09510-1, Sr. 0573259.
^ Melhorn, Kurt; Näher, Stefan (1999). La plataforma LEDA de computación combinatoria y geométrica. Cambridge University Press . Consultado el 12 de noviembre de 2019 .
^ Mehlhorn, Kurt ; Schirra, Stefan (2001), "Cálculo exacto con leda_real: teoría y aplicaciones geométricas" (PDF) , Métodos algebraicos simbólicos y métodos de verificación (Dagstuhl, 1999) , Springer, págs. 163–172, doi :10.1007/978-3-7091-6280-4_16, ISBN 978-3-211-83593-7, Sr. 1832422.
^ Grötschel, M.; Lovász, L.; Schrijver, A. (1981-06-01). "El método del elipsoide y sus consecuencias en la optimización combinatoria". Combinatorica . 1 (2): 169–197. doi :10.1007/BF02579273. ISSN 1439-6912. S2CID 43787103.
^ Blum, Lenore ; Shub, Mike ; Smale, Steve (1989), "Sobre una teoría de la computación y la complejidad sobre los números reales: NP-completitud, funciones recursivas y máquinas universales", Boletín de la Sociedad Matemática Americana , 21 (1): 1–46, doi : 10.1090/S0273-0979-1989-15750-9 , Zbl 0681.03020.

Enlaces externos

Referencias factibles de máquinas de acceso aleatorio real
Computación geométrica La ciencia de hacer que los algoritmos geométricos funcionen