Algoritmos combinatoriosfrac-convexidad. Su estructura y complejidad

  1. Rodríguez León, Casiano
Dirigida por:
  1. Miguel Sánchez García Director/a

Universidad de defensa: Universidad de La Laguna

Año de defensa: 1987

Tribunal:
  1. Ildefonso Yáñez de Diego Presidente/a
  2. Luis Javier López Martín Secretario/a
  3. Francisco José Cano Sevilla Vocal
  4. Vicente Quesada Paloma Vocal
  5. Carlos González Martín Vocal

Tipo: Tesis

Teseo: 15846 DIALNET

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.