Resumen de Reducción del tiempo de acceso en memorias tipo disco, mediante ordenación de los registros, algoritmos de optimización

José María Troya Linero , Antonio Vaquero Sánchez

• El tiempo medio de acceso a una memoria secundaria puede reducirse ordenando adecuadamente los registros. En este artículo tratamos este problema bajo la suposición de que la secuencia de acceso a los registros es una cadena de Markov estacionaria. Mediante una transformación, el problema se reduce a resolver el de la ordenación lineal óptima de un grafo. Este es un conocido problema NP-completo, por lo que no puede esperarse obtener la solución óptima en tiempo polinomial. Nosotros damos tres algoritmos de optimización basados en las técnicas de programación dinámicas y evaluación y separación con el objeto de resolver el problema para el mayor número posible de registros.