Algoritmos combinatoriosfrac-convexidad. Su estructura y complejidad

Abstract

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.