Por favor, use este identificador para citar o enlazar este ítem:
http://repositorio.udec.cl/jspui/handle/11594/817
Título : | Generación de pares de hipergrafos duales difíciles |
Autor : | Polyméris Paravicini, Andreas; profesor guía Riquelme Csóri, Fabián Rolando |
Palabras clave : | Software Computacional - Desarrollo;Teoría de Grafos.;Algoritmos Computacionales. |
Fecha de publicación : | 2009 |
Editorial : | Universidad de Concepción. |
Resumen : | En esta tesis se define el concepto de clase difícil, como una relación de pre-orden que permite relacionar clases de instancias pertenecientes a un problema de decisión dado. Mientras más difícil sea una clase utilizada como dominio de aplicación en un plan de testing para un algoritmo, más confiables resultar an las conclusiones a las que lleguemos acerca de la eficiencia de ese algoritmo. En particular, se definen y caracterizan clases difíciles para el problema de completitud de hipergrafos, así como para el problema de completitud restringido a pares coherentes; algunas de estas clases ya eran conocidas en la literatura, y otras son propias de este trabajo. Además se demuestra que los benchmark utilizados en la práctica por los algoritmos que resuelven este problema no son estrictamente difí ciles, y se de ne una nueva subclase de este tipo, la de los pares triangulares, perteneciente a una clase muy difí cil, que se presenta como un benchmark exigente (aunque no su ciente), no utilizado hasta ahora. Finalmente, se describen algunos mecanismos para ayudar a generar pares de hipergrafos pertenecientes a clases difíciles, y se indaga acerca de las dificultades para la realización de esta tarea. |
Descripción : | Tesis (Magister en Ciencias de la Computación) 2009. |
URI : | http://repositorio.udec.cl/jspui/handle/11594/817 |
metadata.dc.identifier.other: | 000186934 |
Aparece en las colecciones: | Ingeniería Informática y Ciencias de la Computación - Tesis Magister |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | |
---|---|---|---|---|
Tesis_Generacion_de_Pares_de_Hipergrafos_duales_dificiles.Image.Marked.pdf | 684,16 kB | Adobe PDF | Visualizar/Abrir |
Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons