Tesis "Construcción de Sequence Covering Arrays"
Alumno: Daniel Ramírez Acuña
Asesor: Dr. José Torres Jiménez
Sinodales: Dr. Ricardo Landa Becerra, Dr. Hector Hugo Avilés Arriaga
Resumen:
Los Covering Arrays (CAs) son diseños combinatorios que han sido usados con éxito para la realización de pruebas de componentes de hardware y de software. Los CAs permiten reducir la cardinalidad de una prueba y maximizar la cobertura de la misma, i.e. minimizar el número de pruebas y cubrir todas las combinaciones de valores entre t columnas. Un aspecto que no es cubierto por un CA es el manejo de la temporalidad en la ocurrencia de eventos. Por esta razón fueron propuestos los Sequence Covering Arrays (SCAs) que permiten minimizar la cardinalidad de una prueba al tiempo que cubren todas las subsecuencias de eventos de un cierto tamaño t. En esta tesis se propone una metodología que permite la construcción de SCAs competitivos (competitivo se usa en el sentido de reducir o igualar el menor tamaño que ha sido reportado en la literatura para un SCA en particular). La metodología usa un algoritmo avaro para construir una solución inicial, un algoritmo metaheuristico para mejorar dicha solución y un algoritmo de postoptimización para reducir aún más la cardinalidad de cada SCA construido. Respecto al estado del arte se construyeron 507 nuevas cotas.