Algoritmos combinatorios: frac-convexidad. Su estructura y complejidad

• Autores: Casiano Rodríguez León
• Directores de la Tesis: Miguel Sánchez García (dir. tes.)
• Lectura: En la Universidad de La Laguna ( España ) en 1987
• Idioma: español
• Tribunal Calificador de la Tesis: Ildefonso Yáñez de Diego (presid.) , Luis Javier López Martín (secret.) , Francisco José Cano Sevilla (voc.) , Vicente Quesada Paloma (voc.) , Carlos González Martín (voc.)
• MSC2000 :
  • Combinatoria
• Texto completo no disponible (Saber más ...)
• Resumen

  • 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.