Memoria 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 de 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 ]}

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. Consta de un programa almacenado , una unidad de memoria de computadora compuesta por 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 con los valores almacenados en los registros.

Las operaciones permitidas suelen incluir suma, resta, multiplicación y división, así como comparaciones, pero no módulo ni redondeo a enteros. La razón para evitar el redondeo de enteros y las operaciones de módulo es que permitir estas operaciones podría otorgar 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, normalmente se supone que cada operación permitida tarda un tiempo constante .

Se han desarrollado bibliotecas de software como LEDA que permiten a los programadores escribir programas informáticos que funcionan como si se ejecutaran en una RAM real. Estas bibliotecas representan valores reales mediante estructuras de datos que 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 mediante el leda_realtipo de dato, 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 subyacente de la RAM real que utiliza estos tipos de datos reales puede interpretarse como el recuento del número de llamadas a la biblioteca necesarias para un algoritmo dado. ^{[ 4 ]}

• En el modelo de máquina de Turing , la unidad básica de computación implica un bit. Por lo tanto, la complejidad temporal y espacial de los algoritmos numéricos depende del número de bits necesarios para representar los números. En cambio, en el modelo de RAM real, la unidad básica de computación implica un número real, independientemente de cuántos bits se requieran para representarlo. Esta diferencia es importante al analizar 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 forma ingenua) crecer exponencialmente, por lo que su tiempo de ejecución en el modelo de máquina de Turing es exponencial. ^{[ 5 ] : Sec.1.4}
• La RAM real se asemeja mucho a la posterior máquina de Blum-Shub-Smale . ^{[ 6 ]} Sin embargo, la RAM real se utiliza típicamente para el análisis de algoritmos concretos en geometría computacional , mientras que la máquina de Blum-Shub-Smale constituye la base para extensiones de la teoría de la NP-completitud al cálculo de números reales.
• Una alternativa a la RAM real es la RAM de palabras , en la que tanto las entradas de un problema como los valores almacenados en memoria y registros se consideran 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 de ordenación de enteros rápidos , mientras que la ordenación en la RAM real debe realizarse con algoritmos de ordenación por comparación más lentos . Sin embargo, algunos problemas de geometría computacional tienen entradas o salidas que no pueden representarse con exactitud mediante 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 de máquinas de acceso aleatorio reales factibles
• Computación geométrica: La ciencia de hacer funcionar los algoritmos geométricos.