Análisis medio de algoritmos de reducción sobre árboles

Resumen

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.