Reducción del tiempo de acceso en memorias tipo disco, mediante ordenación de los registros, algoritmos de optimización
- Troya Linero, José María
- Vaquero Sánchez, Antonio
ISSN: 0210-8712
Año de publicación: 1981
Año: 14
Número: 49
Páginas: 5-12
Tipo: Artículo
Otras publicaciones en: Revista de informática y automática
Resumen
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.