Algoritmos combinatoriosfrac-convexidad. Su estructura y complejidad

  1. Casiano Rodríguez León
Supervised by:
  1. Miguel Sánchez García Director

Defence university: Universidad de La Laguna

Year of defence: 1987

Committee:
  1. Ildefonso Yáñez de Diego Chair
  2. Luis Javier López Martín Secretary
  3. Francisco José Cano Sevilla Committee member
  4. Vicente Quesada Paloma Committee member
  5. Carlos González Martín Committee member

Type: Thesis

Teseo: 15846 DIALNET

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.