Codificación eficiente de modelos de configuración utilizando BDD'S

Résumé

Información de la tesis Título: Codificación Eficiente de modelos de configuración utilizando BDD’s Autor: Roberto Carlos Beán Castelló DNI: 73201823E Director: Rubén Heradio Gil Co-Director: David Fernández Amorós Doctorado en Ingeniería de Sistemas y Control – Universidad Nacional de Educación a Distancia Introducción La industria y los consumidores necesitan productos personalizados, que se adapten a ellos. La ingeniería de líneas de productos software aborda este problema mediante la creación de productos extremadamente configurables. Estos, se definen mediante modelos de configuración, posibilitando su análisis, mediante su transformación a lógica Booleana. Este análisis permite, por ejemplo, identificar errores del modelo antes de su producción. El análisis de lógica Booleana, a través de SAT solvers o BDD’s (Binary Decision Diagrams), es un problema no soluble en tiempo polinomial. La representación de un producto con tan sólo 37 opciones, utilizando BDD's requiere en el peor de los casos 2⋅〖10〗^11 nodos, tantos como galaxias hay en el universo conocido. En esta tesis se proponen soluciones que permiten las representaciones del modelo completo más escalable, y cuando esto no es posible, se ofrece: dar soluciones a problemas parciales, simplificar el problema completo resolviendo primero problemas. En la tesis se ha realizado el estado del arte de las heurísticas de codificación de BDD’s existentes aplicables a modelos de configuración, y posteriormente un análisis sistemático de las mismas. En la tesis se ha realizado el estado del arte de las heurísticas de codificación de BDD’s existentes aplicables a modelos de configuración, y posteriormente un análisis sistemático de las mismas.   Contribuciones Se ha realizado el primer análisis sistemático de heurísticas de ordenación de BDD’s, tanto dinámicas como estáticas, aplicadas a modelos de configuración. Se ha propuesto el span como herramienta de selección de heurísticas. Se ha desarrollado la heurística PSG (Posible Symmetric Groups) para modelos de configuración mejora la heurística de ordenación dinámica de sifting simétrico. Se ha creado un nuevo algoritmo de cálculo de características core y dead que mejora los existentes, y se ha desarrollado una variante que permite distribuir el problema. Se ha creado un nuevo algoritmo que reduce el problema eliminando características core y dead sin construir el modelo completo. Artículos publicados Perez-Morago, Hector ; Heradio, Ruben ; Fernández-Amorós, David ; Bean, Roberto ; Cerrada, Carlos: Efficient Identification of Core and Dead Features in Variability Models. In: {IEEE} Access Bd. 3 (2015), S. 2333–2340 Heradio, Ruben ; Perez-Morago, Hector ; Fernández-Amorós, David ; Bean, Roberto ; Cabrerizo, Francisco Javier ; Cerrada, Carlos ; Herrera-Viedma, Enrique: Binary Decision Diagram Algorithms to Perform Hard Analysis Operations on Variability Models. In: New Trends in Software Methodologies, Tools and Techniques - Proceedings of the Fifteenth SoMeT16, Larnaca, Cyprus, 12-14 September 2016 (2016).