Resum

Una bona estratègia per a provar un component de programari, implica la generació de tot el conjunt de casos que participen en el seu funcionament. Mentre que provar només alguns valors pot no ser suficient, fer una prova exhaustiva de totes les combinacions no sempre és factible. Una tècnica alternativa per a aconseguir aquest objectiu és coneguda com combinatorial testing. Combinatorial testing és un mètode que pot reduir els costos i incrementar l'eficàcia de les proves de programari per a moltes aplicacions. Es basa en la construcció de petits casos de prova funcionals, que proporcionen la cobertura de les configuracions més comunes. Els covering arrays són objectes combinatoris, que han sigut aplicats per a realitzar proves funcionals en diverses àrees, entre elles, les proves de components de programari. L'ús dels covering arrays permet provar totes les interaccions, d'una determinada grandària, entre els paràmetres d'entrada, utilitzant el menor nombre de casos de prova 
possible.

Per a les proves de programari, el problema fonamental és trobar un covering array amb el mínim nombre de línies possible, la qual cosa reduiria: el nombre de proves, el cost i el temps emprat en el procés de proves de programari. A causa de la importància de la construcció de covering arrays òptims o cuasi-òptims, s'ha dut a terme molta investigació sobre el desenvolupament de mètodes eficaços per a construir-los. Hi ha diversos mètodes reportats per a la construcció d'aquests models combinatoris, entre ells estan: (1) mètodes algebraics, (2) mètodes recursivos, (3) algorismes voraços, i (4) algorismes aproximats (metaheurísticas).

Els mètodes basats en metaheurísticas, especialment els basats en simulated annealing han proporcionat els resultats més precisos en diverses ocasions fins avui. El simulated annealing és un mètode d'optimització estocàstica de propòsit general que ha demostrat ser una eina eficaç per a resoldre una àmplia gamma de problemes d'optimització combinatòria. No obstant açò, un dels majors inconvenients del simulated annealing és el temps que requereix per a obtenir solucions òptimes o properes a l'òptim.

En aquesta tesi, es proposa el desenvolupament d'un algorisme de simulated annealing per a la construcció de covering arrays de força t >= 2, per a aplicar-los al desenvolupament de proves funcionals de components de programari. A més, es proposa l'ús de les tecnologies de Grid Computing i Supercomputing per a fer front a la gran quantitat de temps que requereix l'algorisme de simulated annealing per a obtenir covering arrays òptims o propers a l'òptim.