En la teoría de la complejidad computacional , y más específicamente en el análisis de algoritmos con datos enteros , el modelo transdicotómico es una variación de la máquina de acceso aleatorio en la que se supone que el tamaño de la palabra de la máquina coincide con el tamaño del problema. El modelo fue propuesto por Michael Fredman y Dan Willard , [1] quienes eligieron su nombre "porque la dicotomía entre el modelo de la máquina y el tamaño del problema se cruza de manera razonable". [2]
En un problema como el ordenamiento de enteros en el que hay n enteros para ordenar, el modelo transdicotómico asume que cada entero puede almacenarse en una sola palabra de la memoria de la computadora, que las operaciones en palabras simples toman un tiempo constante por operación y que el número de bits que se pueden almacenar en una sola palabra es al menos log 2 n . El objetivo del análisis de complejidad en este modelo es encontrar límites de tiempo que dependan solo de ny no del tamaño real de los valores de entrada o las palabras de máquina. [3] [4]Al modelar el cálculo de números enteros, es necesario asumir que las palabras de máquina tienen un tamaño limitado, porque los modelos con precisión ilimitada son irrazonablemente poderosos (capaces de resolver problemas completos de PSPACE en tiempo polinomial). [5] El modelo transdicotómico hace una suposición mínima de este tipo: que hay algún límite y que el límite es lo suficientemente grande como para permitir la indexación de acceso aleatorio en los datos de entrada. [3]
Además de su aplicación a la ordenación de enteros, el modelo transdicotómico también se ha aplicado al diseño de colas de prioridad [6] ya problemas de geometría computacional [3] y algoritmos de grafos . [7]
Ver también
Referencias
- ^ Fredman, Michael L .; Willard, Dan E. (1993), "Superando el límite de la teoría de la información con árboles de fusión", Journal of Computer and System Sciences , 47 (3): 424–436, doi : 10.1016 / 0022-0000 (93) 90040-4 , MR 1248864.
- ^ Benoit, David; Demaine, Erik D .; Munro, J. Ian; Raman, Venkatesh, "Representación de árboles de grado superior", Algoritmos y estructuras de datos: 6º Taller Internacional, WADS'99 , p. 170.
- ^ a b c Chan, Timothy M .; Pǎtraşcu, Mihai (2009), "Resultados transdicotómicos en geometría computacional, I: ubicación de puntos en tiempo sublogarítmico" (PDF) , SIAM Journal on Computing , 39 (2): 703–729, doi : 10.1137 / 07068669X.
- ^ Chan, Timothy M .; Pǎtraşcu, Mihai (2010), Resultados transdicotómicos en geometría computacional, II: Búsqueda sin conexión , arXiv : 1010.1948 , Bibcode : 2010arXiv1010.1948C.
- ^ Bertoni, Alberto; Mauri, Giancarlo; Sabadini, Nicoletta (1981), "Una caracterización de la clase de funciones computables en tiempo polinomial en máquinas de acceso aleatorio", Actas del XIII Simposio Anual ACM sobre Teoría de la Computación (STOC '81) , págs. 168-176, doi : 10.1145 / 800076.802470.
- ^ Raman, Rajeev, "Priority Queues: Small, Monotone and Trans-dichotomous", Actas del Cuarto Simposio Europeo Anual sobre Algoritmos (ESA '96) , Lecture Notes in Computer Science, 1136 , Springer-Verlag, págs. 121-137, doi : 10.1007 / 3-540-61680-2_51.
- ^ Fredman, Michael L .; Willard, Dan E. (1994), "Algoritmos trans-dicotómicos para árboles de expansión mínimos y caminos más cortos", Journal of Computer and System Sciences , 48 (3): 533–551, doi : 10.1016 / S0022-0000 (05) 80064 -9.