ALGORITMOS COMBINATORIOS: FRAC-CONVEXIDAD. SU ESTRUCTURA Y COMPLEJIDAD

Autor: RODRIGUEZ LEON CASIANO
Año: 1986
Universidad: LA LAGUNA
Centro de realización: DEPARTAMENTO DE ESTADISTICA E INVESTIGACION OPERATIVA UNIVERSIDAD DE LA LAGUNA
Centro de lectura: MATEMATICAS
Director:
Tribunal: YAÑEZ DE DIEGO ILDEFONSO , CANO SEVILLA FRANCISCO JOSE , QUESADA PALOMA VICENTE , GONZALEZ MARTIN CARLOS , LOPEZ MARTIN LUIS JAVIER
Resumen de la tesis

DEDICAMOS LA PRESENTE MONOGRAFIA AL ESTUDIO DE DOS IMPORTANTES TOPICOS: -ESTRUCTURAR LOS CONCEPTOS SOBRE MAQUINAS DE COMPUTAR UNIVERSALES PARA CON ESTA BASE DESARROLLAR LA COMPLEJIDAD ALGORITMICA DE DISTINTOS PROBLEMAS. -DESARROLLAR ALGORITMOS PARA RESOLVER COMPUTACIONALMENTE PROBLEMAS COMBINATORIOSY PARA LA BUSQUEDA DEL OPTIMO EN FUNCIONES FRAC-CONVEXAS. EN RELACION CON EL PRIMER OBJETIVO SE EXPONEN LOS CONCEPTOS DE MAQUINA DE TURING FUNCIONES PARCIALMENTE RECURSIVAS SISTEMAS DE POST SISTEMAS DE MARKOFFY MAQUINAS DE REGISTROS ILIMITADOS; SINTETIZANDO LAS PRUEBAS SOBRE EL IMPORTANTERESULTADO DE QUE ESTOS MODELOS COMPUTAN LA MISMA CLASE DE FUNCIONES ENTENDIDO EN UN CONTEXTO TEORICO. SIGUIENDO LA OBRA DE WAGNER Y WECHSUG DESARROLLAMOS EN UN AMPLIO CAPITULO LOSPROBLEMAS QUE PLANTEA LA COMPLEJIDAD ALGORITMICA; SOBRE TODO EN CONEXION CON LOSCONCEPTOS DE REDUCIBILIDAD CLASES DE COMPLEJIDAD Y VELOCIDAD-ACELERACION DE LA COMPUTACION. RESPECTO AL SEGUNDO OBJETIVO DAMOS UNA CLASIFICACION DE LOS PRINCIPALES PROBLEMAS COMBINATORIOS; SINTETIZANDO A CONTINUACION LAS PRINCIPALES TECNICAS APLICADAS A LA RESOLUCION DE ESTOS PROBLEMAS. OBSERVAMOS CON AGRADO QUE GRAN PARTE DE LOS PROBLEMAS COMBINATORIOS SE ENGLOBAN EN LAS CLASES DE SUBCONJUNTO DISTINGUIDO Y EN LA DE PROBLEMAS DE ORDENACION. HACEMOS ALGUNAS APORTACIONES ORIGINALES SOBRE EL PLANTEAMIENTO Y LA RESOLUCION DE ESTAS CLASES DE PROBLEMAS. FINALMENTE INTRODUCIMOS EL CONCEPTO DE FUNCION FRA-CONVEXA ESTUDIAMOS SUS PROPIEDADES Y DESARROLLAMOS ALGORITMOS PARA EL CALCULO DEL OPTIMO DE ESTAS FUNCIONES.
Materias relacionadas