Tesis "Construcción de Covering Arrays de Alfabeto Ternario y Fuerza Variable"
Alumno: Jorge Armando Martínez Peña
Asesor: Dr. José Torres Jiménez
Los Covering Arrays (CA) son objetos combinatorios que garantizan tener una mínima cardinalidad y una máxima cobertura. En términos simples un CA es una matriz de "N" renglones y "k" elementos cuyos elementos pertencen a un alfabeto "v", y garantizan que todos los subconjuntos de columnas de tamaño "t" (llamado fuerza o grado de interacción) contienen al menos una vez cada una de las combinaciones de {0,1,...,v-1}^t. En el contexto práctico los CA han sido utilizados ampliamente para el proceso de pruebas de componentes de software.
La construcción de CA es un problema de alta complejidad computacional dado el gran espacio de búsqueda potencial que tiene que ser explorado/discriminado para poder encontrar una solución aceptable. En esta tesis se presentan tres algoritmos (uno exacto, un voraz y un metaheurístico) para construir CA ternarios para diveros valores de "t". La representación usada en los tres algoritmos es original (hasta donde se tiene conocimiento) y está basada en el uso de coeficientes trinomiales( que resultan del desarrollo de un trinomio elevado a una potencia).
Los mejores resultados obtenidos son competitivos al ser comparados contra dos métodos de búsqueda reportados en la literatura. De manera adicional para valores pequeños de "k" se logró obtener el valor óptimo.
La contribución más importante del trabajo radica en la determinación de construcciones directas derivadas de los resultados obtenidos de la experimentación con los tres algoritmos mencionados.
Como trabajo futuro se tiene contemplado el extender el alcance para cubrir CA de alfabetos mayores que 3 (v>3) haciendo uso de coeficientes "v-nomiales" (que resultan de elevan un "v-nomio" a una potencia).