Лекции. Тестирование ПО (all in one) (1186159), страница 24
Текст из файла (страница 24)
Оказывается, есть общая конструкцияпокрывающего набора для числа значений, являющегося произведением чисел значений вуже построенных покрывающих наборов: покрывающие наборы с k параметрами глубины tдля n1 и n2 значений дают покрывающий набор с k параметрами для глубины t для n1·n2.Для его построения обозначим элементы двух исходных наборов через aij и blj — у этихнаборов одинаковое число столбцов, и, возможно, разное число строк. В первом набореучаствуют элементы от 0 до (n1–1), во втором — от 0 до (n2–1). Любое число от 0 до (n1·n2–1)можно однозначно представить в виде n2·q + r, где q лежит от 0 до (n1–1), r — от 0 до (n2–1).Кроме того, обозначим строки новой таблицы парами индексов строк двух исходных таблиц.Тогда ее элементы могут быть построены по формуле x(i,m)j = n2·aij + bmj.
Подученная тактаблица представляет покрывающий набор с k параметрами для глубины t для n1·n2.Как следствие CAN(t; k, n1·n2) <= CAN(t; k, n1)·CAN(t; k, n2).Пример для n = 6 = 2·3.01230011001011011001234567800011122200120120121012120201201220112000010203040506070810111213141516171820212223242526272830313233343536373800011122200011122233344455533344455500120120123453453450120120123453453421012120201345453534345453534012120204Описанные выше техники позволяют строить покрывающие наборы любой глубины слюбыми значениями для небольшого количества параметров. Чтобы увеличить количествопараметров, нужно использовать другие подходы.Во-первых, для глубины 2 и произвольного числа параметров k, принимающих только 2значения, есть алгоритм, позволяющий достаточно быстро находить минимальныйвозможный покрывающий набор.Выберем наименьшее N такое, что выполнено k ≤ C N N−1/ 2 .
Здесь x — наименьшее целоечисло, большее или равное x, C rq — биномиальный коэффициент. Получаемые значения Nдля разных k сведены в следующую таблицу.k2-345-1011-1516-3536-5657-126127-210211-462N456789101112k1717-30033004-64356436-1144011441-2431024311-4375843759-9237892377-167960167961-352716352717-646646N151617181920212223k2496145-52003005200301-96577009657701-2005830020058301-3744216037442161-7755876077558761-145422675145422676-300540195300540196-565722720565722721-1166803110N262728293031323334463-792793-17161314646647-13520781352079-249614424251166803111-22039614302203961431-45375676503536Это число N равно числу строк в покрывающем наборе глубины 2 с двумя значениямидля k параметров.
Из таблицы видно, что небольшое число тестов может покрыть всекомбинации пар значений для огромного количества параметров — 10 тестов достаточно для126 параметров, а 20 тестов — для более чем 92000.Первую строка набора сделаем состоящей целиком из 0. Остается N–1 строк, элементыкоторых строятся по столбцам. В качестве этих столбцов берутся все возможныепоследовательности из N/2 единиц и N/2-1 нулей.Примеры.CAN(2; 4, 2) = 500001110110110110111CAN(2; 10, 2) = 600000 0000011111 1000011100 0111010011 0110101010 1101100101 10111CAN(2; 15, 2) = 700000 00000 0000011111 11111 0000011111 10000 1111011100 01110 1110110011 01101 1101101010 11011 1011100101 10111 01111CAN(2; 35, 2) = 800000 00000 00000 00000 00000 00000 0000011111 11111 11111 11111 00000 00000 0000011111 11111 00000 00000 11111 11111 0000011110 00000 11111 10000 11111 10000 1111010001 11000 11100 01110 11100 01110 1110101001 00110 10011 01101 10011 01101 1101100100 10101 01010 11011 01010 11011 1011100010 01011 00101 10111 00101 10111 01111CAN(2; 56, 2) = 900000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 011111 11111 11111 11111 11111 11111 11111 00000 00000 00000 00000 011111 11111 11111 11111 00000 00000 00000 11111 11111 11111 00000 011111 11111 00000 00000 11111 11111 00000 11111 11111 00000 11111 011110 00000 11111 10000 11111 10000 11110 11111 10000 11110 11110 110001 11000 11100 01110 11100 01110 11101 11100 01110 11101 11101 101001 00110 10011 01101 10011 01101 11011 10011 01101 11011 11011 100100 10101 01010 11011 01010 11011 10111 01010 11011 10111 10111 100010 01011 00101 10111 00101 10111 01111 00101 10111 01111 01111 1Доказать, что получаемый так набор действительно покрывающий достаточно просто, авот для доказательства того, что он минимальный нужны нетривиальные комбинаторныефакты, а именно — теорема Ердеша-Ко-Радо.Для всех остальных значений параметров хороших алгоритмов построения минимальныхпокрывающих наборов неизвестно, более того, показано, что построение минимальныхпокрывающих наборов CA(2, k, n), CA(t, k, 2) — NP-полные задачи.Для построения однородных покрывающих наборов для числа значений, не равного 2, идля большого количества параметров проще всего использовать рекурсивные конструкции, спомощью которых набор для большого количества параметров строится из наборов дляменьшего количества.
Ниже рассматриваются две такие конструкции — для глубины 2 и дляглубины 3.Рекурсивная конструкция для покрывающих наборов глубины 2 и n = pk.Строим набор для nm+1 параметра из набора для m параметров.Обозначим через Aij (i <= N, j <= m) элементы исходного набора из CA(2; m, n).Обозначим также через Bij элементы из нижней части (без n верхних строк)покрывающего набора, построенного с помощью самой первой конструкции, число строк внаборе B равно z = n2–n.Строим новый набор в соответствии с приведенной ниже схемой — в ней первая строка, атакже первый столбец отмечают группировку элементов.nnnN0A11A11… A11A12A12… A12… A1mA1m… A1m0A21A21A21A22A22A22A2mA2mA2m…………………………0AN1 AN1AN1AN2 AN2AN2ANm ANmB11 B12B13… B1(n+1) B12B13… B1(n+1) … B12…………………Bz1 Bz2Bz3Bz(n+1) Bz2Bz3Bz(n+1)ANmB13… B1(n+1)………Bz2Bz3Bz(n+1)Получаем соотношение CAN(2; mpk+1, pk) <= CAN(2; m, pk) + p2k – pk.Пример для n = 3, m = 4 Исходный набор A, набор B получается из него отбрасыванием 3х верхних строк.012345678001201201200011122210121202012012201120111222012012120201201120012012012120201012012012201120012120201012012012120201120201Получаемый набор размера 15 для 13 параметров выглядит так.01234567891011121314000000000111222000111222012012000111222120201000111222201120012012012012012012120201201120012201120012012012201120120201012201120201120Рекурсивная конструкция для покрывающих наборов глубины 3.Строим набор глубины 3 для числа элементов n и 2k параметров из набора глубины 3 длятого же числа элементов и k параметров и набора глубины 2 для того же числа элементов и kпараметров.Обозначим элементы исходного набора глубины 3 через Aij (i <= N, j <= k), элементыисходного набора глубины 2 — через Bij (i <= z, j <= k ).Строим новый набор в соответствии с приведенной ниже схемой — в ней первый столбецотмечает группировку элементов, а все сложения проводятся по модулю n.N12…A11A11A12A12A13A13A1kA1k……………………AN1 AN1AN2 AN2AN3 AN3ANk ANkB11(B11+1)B12(B12+1)B13(B13+1)B1k(B1k+1)……………………Bz1(Bz1+1)Bz2(Bz2+1)Bz3(Bz3+1)Bzk(Bzk+1)B11(B11+2)B12(B12+2)B13(B13+2)B1k(B1k+2)……………………Bz1(Bz1+2)Bz2(Bz2+2)Bz3(Bz3+2)Bzk(Bzk+2)……………………B11(B11+(n-1)) B12(B12+(n-1)) B13(B13+(n-1))B1k(B1k+(n-1))……………(Bz3+(n-1))Bzk(Bzk+(n-1))n-1 …Bz1…(Bz1+(n-1)) Bz2…(Bz2+(n-1)) Bz3Получаем соотношение CAN(3; 2k, n) <= CAN(3; k, n) + (n-1)CAN(2; k, n).Для представленных выше в различных местах наборов с n = 3 и k = 4 можно получитьнабор из CA(3; 8, 3), имеющий 45 строк.Приведенные выше конструкции позволяют строить наборы, число тестов в которыхпримерно пропорционально логарифму числа параметров.
Доказаны следующиесоотношения.При n→∞ CAN(2, k, n) ~ (n/2)log(k)CAN(t, k, 2) <~ t2tlog(k)O(log(t))CAN(t, k, n) <~ (t-1)log(k)/log(nt/(nt-1)), что при nt→∞ можно ограничить выражением(1+ε)tntlog(k) для любой положительной константы ε.Построение неоднородных покрывающих наборовНеоднородные покрывающие наборы часто можно достаточно быстро построить изблизких по конфигурации однородных.Например, самый первый приведенный выше набор из CA(2, 3,⋅2,⋅5,⋅4,⋅3,⋅5) был построентак. Переставляя параметры его можно свести к CA(2, 5, 5, 4, 3, 3, 2). Уже видно, чтопотребуется как минимум 25 строк.
Есть однородный набор CA(2, 5, 5, 5, 5, 5, 5), состоящийв точности из 25 строк — берем его и приводим все параметры с меньшим числом значенийпо модулю этого числа значений.Описанный прием может не дать покрывающий набор, если есть параметры с числомзначений, не взаимно простым с числом значений в исходном однородном наборе. В такихслучаях часто все равно можно построить соответствующий неоднородный набор, толькодля «проблемных» параметров придется отдельно подбирать расположение их значений.Еще один пример — покрывающий набор из CA(2, 10, 9, 8, 7, 6, 5, 4, 3, 2).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
