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
Datum der Publikation: 1981
Jahr: 14
Nummer: 49
Seiten: 5-12
Art: Artikel
Andere Publikationen in: Revista de informática y automática
Zusammenfassung
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.