Ordenación lineal de grafos para el almacenamiento de registros en memorias secundarias

• Autores: José María Troya Linero
• Directores de la Tesis: Antonio Vaquero Sánchez (dir. tes.)
• Lectura: En la Universidad Complutense de Madrid ( España ) en 1980
• Idioma: español
• Tribunal Calificador de la Tesis: Antonio Vaquero Sánchez (presid.) , Fernando Sáez Vacas (secret.) , Rafael Dominguez Ruiz (voc.) , Maximino Rodríguez Vidal (voc.) , Mariano Mellado Rodríguez (voc.)
• Texto completo no disponible (Saber más ...)
• Resumen

  • SE ABORDA EL PROBLEMA DE MINIMIZAR EL TIEMPO DE ACCESO A UNA MEMORIA SECUNDARIA CUANDO LOS DATOS QUE SE QUIEREN ALMACENAR ESTAN RELACIONADOS ENTRE SI, EL PROBLEMA SE REDUCE A ORDENAR LINEALMENTE LOS VERTICES DEL GRAFO QUE REPRESENTA LAS RELACIONES ENTRE LOS REGISTROS DE FORMA QUE SE OPTIMICE UNA DETERMINADA FUNCION DE COSTE. EL PROBLEMA PLANTEADO ES NP-COMPLETO POR LO QUE LA SOLUCION OPTIMA SOLO PUEDE OBTENERSE MEDIANTE UN ALGORITMO DE COMPLEJIDAD EXPONENCIAL EN EL TIEMPO. SE REALIZA UN ALGORITMO BASADO EN LA PROGRAMACION DINAMICA QUE OBTIENE LA SOLUCION OPTIMA EN UN TIEMPO O(A32N). SE ENCUENTRA UN SUBPROBLEMA RESOLUBLE OPTIMAMENTE EN TIEMPO POLINOMIAL Y SE REALIZAN ALGORITMOS DE APROXIMACION QUE OBTIENEN BUENAS SOLUCIONES APROXIMADAS. EL ESTUDIO SE APLICA A DOS CASOS PARTICULARES.