Por favor, use este identificador para citar o enlazar este ítem: http://repositorio.udec.cl/jspui/handle/11594/896
Registro completo de metadatos
Campo DC Valor Lengua/Idioma
dc.contributor.advisorSeco Naveiras, Diego; supervisor de gradoes
dc.contributor.advisorAbreu Salas, José Ignacio; supervisor de gradoes
dc.contributor.authorSánchez Mirabal, Pedro Anieles
dc.date.accessioned2020-10-17T13:30:08Z-
dc.date.available2020-10-17T13:30:08Z-
dc.date.issued2019-
dc.identifier.urihttp://repositorio.udec.cl/jspui/handle/11594/896-
dc.descriptionTesis para optar al grado de Doctorado en Ciencias de la Computación.es
dc.description.abstractEl problema de la cadena media es NP-hard para muchas de sus formulaciones, específicamente cuando se emplea la distancia de edición de Levenshtein. Las heurísticas más competitivas aplicadas a este problema usan algoritmos basados en hacer perturbaciones sucesivas a una solución inicial, estos algoritmos son llamados perturbation-based iterative algorithms. La cadena inicial y la política para establecer un orden entre las posibles ediciones son esenciales en la eficiencia de estos algoritmos. En esta tesis se abordan estos sub-problemas. Primero, se estudia cómo una mejor clasificación de las posibles perturbaciones atendiendo a su calidad, tiene efectos en la convergencia de los algoritmos, como consecuencia de esto, se obtiene un nuevo ranking de perturbaciones, que no solamente tiene en cuenta lo que ocurre en relación con las cadenas en las que dicha perturbación está presente, si no, también con respecto al resto de las cadenas del conjunto. Luego, se muestra como la cadena inicial influye en el proceso, analizando principalmente dos variantes de inicialización para estos algoritmos, la cadena perteneciente al conjunto con menos distancia al resto, y la media de un subconjunto de la entrada del algoritmo. Este subconjunto mencionado anteriormente es determinado por los vecinos obtenidos al aplicar el algoritmo Half Space Proximal (HSP) a la cadena mediana del conjunto. De la misma forma, se proponen alternativas para la reducción del conjunto de datos a procesar, sustituyéndolo por un subconjunto de éste, con el fin de disminuir los costes computacionales de los algoritmos. Finalmente, se valida la calidad de los algoritmos obtenidos mediante algoritmos de optimización que resuelven este problema de forma óptima. En el proceso de validación se lleva a cabo un gran número de experimentos que dan soporte a las conclusiones obtenidas. En estos experimentos se muestra que el error de los algoritmos diseñados se encuentra bien acotado, obteniendo soluciones óptimas para los casos en que SAT o ILP logran determinar el ´óptimo. En los casos en que el óptimo no es determinado por SAT o ILP, la solución encontrada es mejor o igual, logrando obtenerla en un tiempo de cómputo menor.es
dc.language.isospaes
dc.publisherUniversidad de Concepción.es
dc.rightsCreative Commoms CC BY NC ND 4.0 internacional (Atribución-NoComercial-SinDerivadas 4.0 Internacional)-
dc.rights.urihttps://creativecommons.org/licenses/by-nc-nd/4.0/deed.es-
dc.subjectAlgoritmos Computacionales-
dc.subjectProgramación Lineal-
dc.subjectIndustria, Innovación e Infraestructura-
dc.titleAlgoritmos para el cálculo de la cadena media.es
dc.typeTesises
dc.description.facultadDepartamento de Ingeniería Informática y Ciencias de la Computaciónes
dc.description.departamentoDepartamento de Ingeniería Informática y Ciencias de la Computación.es
Aparece en las colecciones: Ingeniería Informática y Ciencias de la Computación - Tesis Doctorado

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
Tesis algoritmo para el calculo.pdf1,22 MBAdobe PDFVista previa
Visualizar/Abrir


Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons Creative Commons