Tesis "Clasificación de Coverings Arrays"
Sustentante: Idelfonso Izquierdo Márquez.
Director: Dr. José Torres Jiménez, investigador Cinvestav Tamaulipas.
Sinodales: Dr. Héctor Hugo Avilés Arriaga, Universidad Politécnica de Victoria; Dr. Said Polanco Martagón, Universidad Politécnica de Victoria; Dr. José Juan García Hernández, Cinvestav Tamaulipas; Dr. Ricardo Landa Becerra, Cinvestav Tamaulipas.
Resumen:
Un covering array CA(N;t,k,v) es un arreglo de tamaño N x k sobre Z_v={0,1,...,v-1} tal que cada subarreglo de t columnas contiene como renglón al menos una vez cada una de las t-tuplas sobre Z_v. El mínimo número de renglones para el cual existe un CA con fuerza t, k columnas, y orden v, es el covering array number de t, k, v, y se denota por CAN(t,k,v). Hay tres isomorfismos en los CAs: permutaciones de renglones, permutaciones de columnas, y permutaciones de símbolos en una columna. Para valores particulares de N, t, k, v, el conjunto de todos los covering arrays CA(N;t,k,v) se particiona en clases de CAs isomórficos. Todos los CAs de una clase son isomórficos entre sí, pero ningún CA de una clase es isomórfico a un CA de otra clase. La clasificación de CAs implica la generación de un elemento de cada clase. En esta tesis se desarrollan dos nuevos algoritmos de clasificación. El primero de ellos es una versión mejorada de un algoritmo reportado previamente, el cual sigue la estrategia de generación ordenada de subarreglos. El segundo algoritmo se basa en yuxtaponer verticalmente v CAs de fuerza t para generar CAs de fuerza t + 1. Estos dos algoritmos pueden clasificar CAs más grandes que los clasificados por algoritmos del estado del arte. Para reducir el tiempo de ejecución de los algoritmos, desarrollamos versiones paralelas de ellos usando el modelo de paso de mensajes. Los resultados computacionales más importantes son la clasificación de 39 nuevos CAs, el hallazgo de 19 nuevos CANs, y la mejora de 13 cotas inferiores de CANs.