Hispanopedia Wiki
Articulo de referencia

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 c...

Hispanopedia WikiContenido en espanolLectura gratuita

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 ]

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. 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 .

Implementación

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 ]

Comparación con otros modelos computacionales

  • In the Turing machine model, the basic unit of computation involves one bit. Therefore, the time and space complexity of numeric algorithms depends on the number of bits needed to represent the numbers. In contrast, in the Real RAM model, the basic unit of computation involves a real number, regardless of how many bits are required to represent it. This difference is important when analyzing algorithms such as Gaussian elimination: this algorithm requires a polynomial number of arithmetic operations on real numbers, so it is polynomial in the Real RAM model; however, the numbers used in the intermediate computations may (if implemented naively) grow exponentially large, so its run-time in the Turing Machine model is exponential.[5]:Sec.1.4
  • The real RAM closely resembles the later Blum–Shub–Smale machine.[6] However, the real RAM is typically used for the analysis of concrete algorithms in computational geometry, while the Blum–Shub–Smale machine instead forms the basis for extensions of the theory of NP-completeness to real-number computation.
  • An alternative to the real RAM is the word RAM, in which both the inputs to a problem and the values stored in memory and registers are assumed to be integers with a fixed number of bits. The word RAM model can perform some operations more quickly than the real RAM; for instance, it allows fast integer sorting algorithms, while sorting on the real RAM must be done with slower comparison sorting algorithms. However, some computational geometry problems have inputs or outputs that cannot be represented exactly using integer coordinates; see for instance the Perles configuration, an arrangement of points and line segments that has no integer-coordinate representation.

References

  1. ↑Shamos, Michael Ian (1978), Computational Geometry, Ph.D. dissertation, Yale University.
  2. ↑Schönhage, Arnold (1979), "On the power of random access machines", Proceedings of the Sixth International Colloquium on Automata, Languages and Programming (ICALP '79), Lecture Notes in Computer Science, vol. 71, Springer, pp. 520–529, doi:10.1007/3-540-09510-1_42, ISBN 978-3-540-09510-1, MR 0573259.
  3. ↑Melhorn, Kurt; Näher, Stefan (1999). The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press. Retrieved 12 November 2019.
  4. ↑ Mehlhorn, Kurt ; Schirra, Stefan (2001), "Exact computation with —theory and geometric applications" (PDF) , Symbolic Algebraic Methods and Verification Methods (Dagstuhl, 1999) , Springer, pp. 163–172 , doi : 10.1007/978-3-7091-6280-4_16 , ISBNleda_real  978-3-211-83593-7, MR 1832422 .
  5. ↑ 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 .  
  6. ↑ 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", Bulletin of the American Mathematical Society , 21 (1): 1–46 , doi : 10.1090/S0273-0979-1989-15750-9 , Zbl 0681.03020 .
  • Referencias de máquinas de acceso aleatorio reales factibles
  • Computación geométrica: La ciencia de hacer funcionar los algoritmos geométricos.