Análisis medio de algoritmos de reducción sobre árboles
- Jean-Marc Steyaert Zuzendaria
Defentsa unibertsitatea: Universidad Complutense de Madrid
Defentsa urtea: 1988
- Antonio Vaquero Sánchez Presidentea
- Francisco Luis Hernández Rodríguez Idazkaria
- Philippe Flajolet Kidea
- Josep Díaz Cort Kidea
- Mario Rodríguez Artalejo Kidea
Mota: Tesia
Laburpena
EN ESTA TESIS SE ABORDA EL ESTUDIO DEL COMPORTAMIENTO MEDIO DE DIVERSOS ALGORITMOS DE REDUCCION DE ESTRUCTURAS ARBORESCENTE DEL ESTILO DE LAS UTILIZADAS PARA REPRESENTAR EXPRESIONES ARITMETICO-LOGICAS; CON LA CARACTERISTICA COMUN DE SU PROCEDER ASCENDENTE RECURSIVO SOBRE LA ESTRUCTURA QUE RECIBEN COMO ENTRADA (FILOSOFIA BOTTOM-UP ), ALGORITMO DE ESTE TIPO SE ENCUENTRAN EN EL CONTEXTO DE LA SIMPLIFICACION ALGEBRAICA Y EN PARTICULAR POR EJEMPLO EN LA SIMPLIFICACION DE TERMINOS DEL CALCULO PROPOSICIONAL. SE PRESENTA UN TRATAMIENTO SISTEMATICO Y UNIFORME PARA TALES PROCESOS EN EL QUE SE RECURRE A DIVERSAS TECNICAS DEL ANALISIS COMBINATORIO Y COMPLEJO HACIENDOSE EN PARTICULAR UN USO EXHAUSTIVO DEL TEOREMA DE DARBOUX PARA LA APROXIMACION ASINTOTICA DE COEFICIENTES DE SERIES DE POTENCIAS ASI COMO DEL TEOREMA DE WEIERSTRASS SOBRE LA COMPLETITUD DEL ESPACIO DE LAS FUNCIONES HOLOMORFAS. SE CONTRASTAN LOS RESULTADOS OBTENIDOS PARA EL COMPORTAMIENTO MEDIO DE LOS ALGORITMOS ESTUDIADOS CON SU COMPORTAMIENTO EN EL CASO PEOR. EL ESTUDIO DE LA COMPLEJIDAD MEDIA DE LOS ALGORITMOS DE SIMPLIFICACION CONSIDERADOS VA PRECEDIDO DEL PREVIO SOBRE DIVERSOS PARAMETROS DEFINIDOS SOBRE LAS ESTRUCTURAS OBTENIDAS COMO SALIDAS DE DICHOS ALGORITMOS EN CONCRETO LA MEDIA Y LA VARIANZA DE SU TAMAÑO. PARA ESTOS RESULTADOS TEORICOS SE DAN ADEMAS SENDAS SIMULACIONES EXPERIMENTALES QUE SE AJUSTAN FIELMENTE A LOS MISMOS VALIDANDOLOS DESDE EL PUNTO DE VISTA DE LA PRACTICA REAL.