лекции, страница 20
Описание файла
PDF-файл из архива "лекции", который расположен в категории "". Всё это находится в предмете "тестирование на основе моделей" из 9 семестр (1 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 20 страницы из PDF
ниже).Для однородных наборов глубины 2, в которых число значений параметров равно степенипростого числа n = pk есть метод построения, основанный на арифметике конечных полей.Известно, что для каждой степени простого числа pk есть конечное поле с таким количествомэлементов, называемое полем Галуа GF(pk). Для k = 1, т.е. когда число элементов самоявляется простым, GF(p) изоморфно полю вычетов по модулю p — ]p.Рассмотрим таблицу из элементов поля GF(pk), построенную следующим способом.Первый столбец состоит из n2 значений, сгруппированных по n одинаковых значений.Каждую такую группу значений, равных i, будем называть i-м блоком. Первому столбцуприсваивается номер ∞.Второй столбец состоит из n2 значений, выстроенных так, что в каждом блокевстречаются все возможные n значений.
Значение, стоящее во втором столбце обозначимчерез j. Второму столбцу присвоим номер 0.Все остальные столбцы, с третьего по (n+1)-й, с номерами m = 1...(n-1) построим так,чтобы в блоке i в j-м ряду стояло значение, получаемое как m*i+j в арифметике GF(pk).Построенная так таблица будет покрывающим набором из множества CA(2; n+1, n), еслирассматривать каждую ее строку как набор значений n+1 параметров, соответствующихстолбцам.Пример для n = 5.Поскольку поле GF(5) изоморфно полю вычетов по модулю 5, складывать и умножатьчисла в обычной целочисленной арифметике, а в конце брать вместо результата его вычет помодулю 5.
Получаемый таким способом покрывающий набор представлен ниже.NN∞00000100123401012341201234230123434012344111122222333334444412340123401234012342340234013401240123340140123123403401240121234040123234010123340122340112340Пример для n = 4.В GF(4) сложение и умножение устроены иначе, чем по модулю 4. Поэтому сначалаприведем таблицы сложения и умножения в поле с 4-мя элементами.+012300123110322230133210*012300000101232023130312Получаемый для n = 4 по описанной конструкции покрывающий набор представлен ниже.NN∞000011112222333300123012301230123101231032230132102012323013210103230123321010322301Таким образом можно строить однородные наборы глубины 2 для (n+1) параметра с nзначениями при n = pk.
Этим показывается, что CAN(2; pk+1, pk) = p2k.Похожая конструкция существует для покрывающих наборов глубины t > 2 и n = pk > t.Для этого надо взять таблицу из n+1-го столбца и nt строк. Каждую строку ее можносопоставить набору a0, a1, …, at-1 элементов из поля GF(pk). Столбцы так же обозначаются∞, 0, 1, ..., n-1. Элемент в определенной строке и определенном столбце вычисляется последующим правилам.∞0xa0a1...at-1 a0 at-1 ΣaixiЗдесь снова используются сложение и умножение из поля GF(pk).Для глубины 3 и n = 2k > t можно расширить эту таблицу на еще один столбец — двапервых столбца обозначим ∞1 и ∞2, остальные, как раньше, — 0, 1, ..., n-1.∞0∞10xa0a1a2 a0 a1 a2 ΣaixiТаким образом, оказывается, что CAN(t; pk+1, pk) = ptk при t < pk, а также CAN(3; 2k+2, 2k)= 23k при k > 1.Пример для n = 3, t = 3.NN000001002010011012020021022100101102110111112120121122200201202210211212220221222∞000000000111111111222222222001201201201201201201201201210121202011202010122010121202012201120120012201201120012Представленные выше конструкции позволяют строить однородные покрывающиенаборы для небольшого числа параметров (<= n+1), принимающих n значений для nявляющегося степенью простого числа.Посмотрим теперь, как можно строить покрывающие наборы для числа значений, неявляющегося степенью простого числа.
Оказывается, есть общая конструкцияпокрывающего набора для числа значений, являющегося произведением чисел значений вуже построенных покрывающих наборов: покрывающие наборы с 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) = 500001110100101010011CAN(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.Строим новый набор в соответствии с приведенной ниже схемой — в ней первая ипоследняя строки, а также первый столбец, отмечают группировку элементов.nnnN0A11A11A11A12A12A12A1mA1mA1m0A21A21A21A22A22A22A2mA2mA2m…………………………0AN1 AN1AN2AN2ANm ANmAN1 AN2ANmB11 B12B12 B13B13B1(n+1)B1(n+1)………………Bz2 Bz3Bz3Bz(n+1)Bz(n+1)…Bz1 Bz2mmmПолучаем соотношение CAN(2; mpk+1, pk) <= CAN(2; m, pk) + p2k – pk.Пример для n = 3, m = 4 Исходный набор012345678001201201200011122210121202012012201120Получаемый набор размера 15 для 13 параметров выглядит так.01234567891011121314000000000111222000111222012012000111222012012000111222012012012012012012012012012012120201012012012120201012120201120201012120201120201012120201201120012201120201120012201120201120012201120201120Рекурсивная конструкция для покрывающих наборов глубины 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).