Statistics under the BST model

• Autores: Conrado Martínez Parra
• Directores de la Tesis: Rafael Casas Muñoz (dir. tes.)
• Lectura: En la Universitat Politècnica de Catalunya (UPC) ( España ) en 1992
• Idioma: inglés
• Tribunal Calificador de la Tesis: Josep Díaz Cort (presid.) , Marc Steyaert Jean (secret.) , José Luis Balcázar Navarro (voc.) , Carles Simó (voc.) , Philippe Flajolet (voc.)
• Texto completo no disponible (Saber más ...)
• Resumen

  • EL PRESENTE TRABAJO ESTA DEDICADO AL ANALISIS DE ALGORITMOS ASUMIENDO QUE SUS ENTRADAS ESTAN DISTRIBUIDAS SEGUN EL MODELO PROBALISTICO BST O SEGUN EL MODELO EQUILIBRADO, QUE GENERALIZA AL ANTERIOR, EL CONJUNTO DE ENTRADAS DE TALES ALGORITMOS ES SIEMPRE ALGUNA FAMILIA DE ARBOLES SIMPLEMENTE GENERADOS. EN AMBOS MODELOS, DOS ARBOLES DEL MISMO TAMAÑO NO SON NECESARIAMENTE EQUIPROBABLES; BIEN AL CONTRARIO, LOS ARBOLES MEJOR EQUILIBRADOS SON MAS PROBABLES QUE LOS POCO EQUILIBRADOS.

    EL MODELO BST CORRESPONDE A LOS ARBOLES BINARIOS DE BUSQUEDA, Y TAMBIEN, A LOS ARBOLES K-D Y "HEAP ORDERED".

    EL ANALISIS DEL COMPORTAMIENTO MEDIO DE ALGORITMOS PARA LOS MODELOS BST Y EQUILIBRADO CONDUCE EN MUCHOS CASOS, A ECUACIONES DIFERENCIALES ORDINARIAS Y EN DERIVADAS PARCIALES, MIENTRAS LOS CORRESPONDIENTES ANALISIS PARA ARBOLES UNIFORMEMENTE DISTRIBUIDOS REQUIEREN LA RESOLUCION DE PROBLEMAS ALGEBRAICOS Y DE ENUMERACION COMBINATORIA. LA TESIS CONSTA DE CUATRO PARTES. LAS DOS PRIMERAS SE DEDICAN AL MATERIAL INTRODUCTORIO: CONCEPTOS BASICOS, DEFINICIONES Y LAS TECNICAS MATEMATICAS (ALGEBRAICAS Y ANALITICAS) QUE SE USAN, TAMBIEN SE PRESENTA EN LA PARTE II UNA COLECCION DE MODELOS PROBABILISTICOS SOBRE ARBOLES, AMEN DEL MODELO BST Y DEL MODELO EQUILIBRADO. LA PARTE III CONSTITUYE LA PRINCIPAL CONTRIBUCION DE LA TESIS COMIENZA CON UN CAPITULO EN EL QUE SE ANALIZA LA OCUPACION, UNA CARACTERISTICA RELACIONADA CON EL GRADO DE EQUILIBRIO DE LOS ARBOLES. SE ANALIZA DICHA CARACTERISTICA PARA DIVERSOS MODELOS DE PROBABILIDAD. EN EL SIGUIENTE CAPITULO, SE ABORDA LA DEFINICION DE UN SISTEMA DE REGLAS ALGEBRAICAS QUE PERMITE LA TRADUCCION DE VARIAS ESPECIFICACIONES RECURSIVAS ALGORITMICAS A ECUACIONES MATEMATICAS QUE DESCRIBEN EL COMPORTAMIENTO MEDIO DE LOS ALGORITMOS QUE INVOLUCRAN DICHO TIPO DE CONSTRUCCIONES. EN EL CAPITULO POSTERIOR SE EXAMINA UN ESQUEMA DE RECURSION SIMPLE, ASOCIADO A LO QUE DENOMINAMOS PROPIEDADES HEREDITARIAS.

    DICHAS PROPIEDADES APARECEN