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 calcular con números reales exactos en lugar de los números binarios de coma fija o de coma flotante utilizados por la mayoría de las computadoras reales. La RAM real fue formulada por Michael Ian Shamos en su Ph.D. de 1978. disertación. [1]
Modelo
La parte "RAM" del nombre del modelo de RAM real significa " máquina de acceso aleatorio ". Este es 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 consta de 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 generalmente incluyen suma, resta, multiplicación y división, así como comparaciones, pero no módulo o redondeo a números enteros. La razón para evitar el redondeo de enteros y las operaciones de módulo es que permitir estas operaciones podría dar a la RAM real cantidades irrazonables de poder computacional, permitiéndole resolver problemas completos de PSPACE en tiempo polinomial. [2]
Cuando se analizan algoritmos para la RAM real, se asume 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_real
tipo 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 de tiempo del algoritmo de RAM real subyacente utilizando estos tipos de datos reales puede interpretarse como un recuento del número de llamadas de biblioteca necesarias para un algoritmo dado. [4]
Modelos relacionados
La RAM real se parece mucho a la posterior máquina Blum-Shub-Smale . [5] Sin embargo, la RAM real se usa típicamente para el análisis de algoritmos concretos en geometría computacional , mientras que la máquina Blum-Shub-Smale en cambio forma la base para extensiones de la teoría de NP-completitud al cálculo de números reales.
Una alternativa a la RAM real es la palabra RAM , en la que se supone que tanto las entradas a un problema como los valores almacenados en la memoria y los registros son números enteros con un número fijo de bits. La palabra modelo RAM puede realizar algunas operaciones más rápidamente que la RAM real; por ejemplo, permite algoritmos de clasificación de enteros rápidos, mientras que la clasificación en la RAM real debe realizarse con algoritmos de clasificación de comparación más lentos . Sin embargo, algunos problemas de geometría computacional tienen entradas o salidas que no se pueden representar exactamente usando coordenadas enteras; vea, por ejemplo, la configuración de Perles , una disposición de puntos y segmentos de línea que no tiene representación de coordenadas enteras.
Referencias
- ^ Shamos, Michael Ian (1978), Geometría computacional , Ph.D. disertación, 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 , 71 , Springer, págs. 520–529 , doi : 10.1007 / 3-540-09510-1_42 , ISBN 978-3-540-09510-1, MR 0573259.
- ^ Melhorn, Kurt; Näher, Stefan (1999). La Plataforma LEDA de Computación Combinatoria y Geométrica . Prensa de la Universidad de Cambridge . Consultado el 12 de noviembre de 2019 .
- ^ Mehlhorn, Kurt ; Schirra, Stefan (2001), "
leda_real
Cálculo exacto con —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, MR 1832422. - ^ 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 American Mathematical Society , 21 (1): 1-46, doi : 10.1090 / S0273-0979-1989-15750-9 , Zbl 0681.03020.
enlaces externos
- Referencias de máquinas de acceso aleatorio reales factibles
- Computación geométrica La ciencia de hacer que los algoritmos geométricos funcionen