Ортогональный массив - Orthogonal array

В математике ортогональный массив представляет собой "таблицу" (массив), элементы которой происходят из фиксированного конечного набора символов (обычно {1,2, ...,п}), расположенные таким образом, что существует целое число т так что для каждого выбора т столбцы таблицы, все упорядочено т-кортежи символов, образованных путем взятия записей в каждой строке, ограниченной этими столбцами, появляются одинаковое количество раз. Номер т называется сила ортогонального массива. Вот простой пример ортогонального массива с набором символов {1,2} и степенью 2:

111
221
122
212

Обратите внимание, что четыре заказанные пары (2-кортежи), образованные строками, ограниченными первым и третьим столбцами, а именно (1,1), (2,1), (1,2) и (2,2), являются всеми возможными упорядоченными парами из двух набор элементов, и каждый появляется ровно один раз. Второй и третий столбцы будут содержать (1,1), (2,1), (2,2) и (1,2); опять же, все возможные упорядоченные пары появляются по одному разу. То же утверждение было бы, если бы использовались первый и второй столбцы. Таким образом, это ортогональный массив силы два.

Ортогональные массивы обобщают идею взаимно ортогональные латинские квадраты в табличной форме. Эти массивы имеют много связей с другими комбинаторными схемами и имеют приложения в статистической дизайн экспериментов, теория кодирования, криптография и различные виды тестирование программного обеспечения.

Определение

А т-(v,k, λ) ортогональный массив (т ≤ k) является λvт × k массив, записи которого выбираются из набора Икс с v такие точки, что в каждом подмножестве т столбцы массива, каждые т-набор точек Икс появляется ровно в λ строках.

В этом формальном определении предусмотрено повторение т-кортежи (λ - количество повторов), а количество строк определяется другими параметрами.

Во многих приложениях этим параметрам присвоены следующие названия:

v это количество уровни,
k это количество факторы,
λvт количество экспериментальных бежит,
т это сила, и
λ - это индекс.

Ортогональный массив просто если он не содержит повторяющихся строк.

Ортогональный массив линейный если Икс это конечное поле порядка q, Fq (q степень простого числа), а строки массива образуют подпространство векторное пространство (Fq)k.[1]

Каждый линейный ортогональный массив прост.

Примеры

Пример 2- (4, 5, 1) ортогонального массива; план силы 2, 4 уровня индекса 1 с 16 пробегами.

11111
12222
13333
14444
21423
22314
23241
24132
31234
32143
33412
34321
41342
42431
43124
44213

Пример ортогонального массива 2- (3,5,3) (записывается как его транспонировать для удобства просмотра):[2]

000000000111111111222222222
000111222000111222000111222
012012012012012012012012012
000111222222000111111222000
012120201012120201012120201

Тривиальные примеры

Любой т-(v, т, λ) ортогональный массив будет считаться банальный поскольку их легко построить, просто перечислив все т-наборы v-множество λ раз.

Взаимно ортогональные латинские квадраты

Основная статья: Взаимно ортогональные латинские квадраты

А 2- (v,k, 1) ортогональный массив эквивалентен набору k − 2 взаимно ортогональные латинские квадраты порядка v.

Ортогональные массивы с индексом один и степенью 2 также известны как Гипер-греко-латинский квадратный дизайн в статистической литературе.

Позволять А ортогональный массив с индексом 1 на v-множество элементов, отождествляемых с множеством натуральных чисел {1, ...,v}. Выберите и исправьте по порядку две колонки А, называется столбцы индексации. Все заказанные пары (я, j) с 1 ≤ я, j ≤ v появляются ровно один раз в строках столбцов индексации. Возьмите любой другой столбец А и создайте квадратный массив, запись которого в позиции (я,j) - это запись А в этом столбце в строке, содержащей (я, j) в столбцах индексации А. Полученный квадрат представляет собой Латинский квадрат порядка v. Например, рассмотрим ортогональный массив 2- (3,4,1):

1111
1222
1333
2123
2231
2312
3132
3213
3321

Выбирая столбцы 3 и 4 (в указанном порядке) в качестве столбцов индексации, первый столбец дает латинский квадрат,

123
312
231

а второй столбец дает латинский квадрат,

132
321
213

Латинские квадраты, полученные таким образом из ортогонального массива, будут ортогональными латинскими квадратами, поэтому k - 2 столбца, кроме столбцов индексации, создадут набор k − 2 взаимно ортогональные латинские квадраты.

Эта конструкция полностью обратима, поэтому ортогональные массивы с индексом 1 могут быть построены из наборов взаимно ортогональных латинских квадратов.[3]

Латинские квадраты, латинские кубы и латинские гиперкубы

Ортогональные массивы обеспечивают единообразный способ описания этих разнообразных объектов, представляющих интерес для статистической дизайн экспериментов.

Латинские квадраты

Как упоминалось в предыдущем разделе, латинский квадрат порядка п можно рассматривать как 2- (п, 3, 1) ортогональный массив. Фактически, ортогональный массив может привести к шести латинским квадратам, поскольку любую упорядоченную пару отдельных столбцов можно использовать в качестве столбцов индексации. Однако это все изотопический и считаются эквивалентными. Для конкретности мы всегда будем предполагать, что первые два столбца в их естественном порядке используются в качестве столбцов индексации.

Латинские кубики

В статистической литературе Латинский куб является п × п × п трехмерная матрица, состоящая из п слоев, каждый из которых имеет п ряды и п столбцы такие, что п отдельные элементы, которые появляются, повторяются п2 раз и расположены так, чтобы в каждом слое, параллельном каждой из трех пар противоположных граней куба, все п появляются отдельные элементы, и каждый в точности повторяется п раз в этом слое.[4]

Обратите внимание, что при таком определении слой латинского куба не обязательно должен быть латинским квадратом. Фактически, ни одна строка, столбец или файл (ячейки определенной позиции в разных слоях) не должны быть перестановка из п символы.[5]

Латинский куб порядка п эквивалентно 2- (п, 4, п) ортогональный массив.[2]

Два латинских кубика порядка п находятся ортогональный если среди п3 пары элементов, выбранных из соответствующих ячеек двух кубов, каждая отдельная упорядоченная пара элементов встречается точно п раз.

Набор k - 3 взаимно ортогональных латинских куба порядка п эквивалентно 2- (п, k, п) ортогональный массив.[2]

Пример пары взаимно ортогональных латинских кубов третьего порядка был дан как ортогональный массив 2- (3,5,3) в Примеры раздел выше.

В отличие от случая с латинскими квадратами, в котором нет ограничений, столбцы индексации ортогонального представления массива латинского куба должны быть выбраны так, чтобы сформировать 3- (п, 3,1) ортогональный массив.

Латинские гиперкубы

An м-размерный Латинский гиперкуб порядка п из рй класс п × п × ... ×п м-мерная матрица, имеющая пр отдельные элементы, каждый повторяется пм − р раз, и такой, что каждый элемент встречается точно п м − р − 1 раз в каждом из своих м наборы п параллельный (м - 1) -мерные линейные подпространства (или «слои»). Два таких латинских гиперкуба одного порядка п и класс р со свойством, что, когда один накладывается на другой, каждый элемент одного встречается точно пм − 2р раз с каждым элементом другого, как говорят, ортогональный.[6]

Набор k − м взаимно ортогональные м-мерные латинские гиперкубы порядка п эквивалентно 2- (п, k, пм − 2) ортогональный массив, в котором столбцы индексации образуют м-(п, м, 1) ортогональный массив.

История

Концепции Латинские квадраты и взаимно ортогональные латинские квадраты были обобщены на латинские кубы и гиперкубы, а ортогональные латинские кубы и гиперкубы Кишен (1942).[7] Рао (1946) обобщил эти результаты на прочность т. Настоящее понятие ортогонального массива как обобщение этих идей, обусловленное К. Р. Рао, появляется в Рао (1947).[8]

Прочие конструкции

Матрицы Адамара

Если существует Матрица Адамара порядка 4м, то существует 2- (2, 4м − 1, м) ортогональный массив.

Позволять ЧАС - матрица Адамара порядка 4м в стандартизированной форме (все записи в первой строке и столбце имеют +1). Удалите первую строку и возьмите транспонировать для получения желаемого ортогонального массива.[9]

Стандартизированная матрица Адамара 8-го порядка ниже (± 1 элемент обозначен только знаком),

++++++++
++++−−−−
++−−++−−
++−−−−++
+−+−+−+−
+−+−−+−+
+−−++−−+
+−−+−++−

создает ортогональный массив 2- (2,7,2):[10]

+++++++
+++−−−−
+−−++−−
+−−−−++
−+−+−+−
−+−−+−+
−−++−−+
−−+−++−

Используя столбцы 1, 2 и 4 в качестве столбцов индексации, оставшиеся столбцы создают четыре взаимно ортогональных латинских куба порядка 2.

Коды

Позволять C ⊆ (Fq)п, быть линейный код измерения м с минимальным расстоянием d. потом C⊥ (ортогональное дополнение векторного подпространства C) является (линейным) (d − 1)-(q, п, λ) ортогональный массив, где
λ =qп − м − d + 1.[11]

Приложения

Пороговые схемы

Основная статья: Обмен секретами

Обмен секретами (также называемый секретное разделение) состоит из методов распределения секрет среди группы участников, каждому из которых назначается Поделиться секрета. Секрет может быть восстановлен только тогда, когда достаточное количество долей, возможно, разных типов, объединены вместе; отдельные акции не используются сами по себе. Схема разделения секрета идеально если каждый набор участников, не отвечающий критериям получения секрета, не имеет дополнительных сведений о секрете, чем человек, не имеющий доли.

В одном типе схемы разделения секрета есть один дилер и п игроки. Дилер выдает доли секрета игрокам, но только при выполнении определенных условий игроки смогут восстановить секрет. Дилер достигает этого, давая каждому игроку долю таким образом, чтобы любая группа т (за порог) или несколько игроков могут вместе восстановить секрет, но ни одна группа из менее чем т игроки могут. Такая система называется (т, п) -пороговая схема.

А т-(v, п + 1, 1) ортогональный массив может быть использован для построения идеального (т, п) -пороговая схема.[12]

Позволять А - ортогональный массив. Первый п столбцы будут использоваться для предоставления акций игрокам, в то время как последний столбец представляет секрет, который будет опубликован. Если дилер желает поделиться секретом S, только ряды А чья последняя запись S используются в схеме. Дилер случайным образом выбирает один из этих рядов и раздает игроку я запись в этой строке в столбце я как акции.

Факторные дизайны

Основная статья: Факторный эксперимент

А факторный эксперимент представляет собой статистически структурированный эксперимент, в котором несколько факторы (уровни полива, антибиотики, удобрения и т. д.) вносятся в каждую экспериментальную единицу в разной (но общей) степени. уровни (высокий, низкий или различные промежуточные уровни).[13] В полный факторный эксперимент все комбинации уровней факторов должны быть протестированы, но чтобы минимизировать мешающие влияния, уровни должны варьироваться в рамках любого экспериментального цикла.

Ортогональный массив силы 2 можно использовать для разработки факторного эксперимента. Столбцы представляют различные факторы, а записи - уровни, на которых факторы могут применяться (при условии, что все факторы могут применяться на одном и том же количестве уровней). Экспериментальный прогон представляет собой строку ортогонального массива, то есть применяют соответствующие коэффициенты на уровнях, которые появляются в строке. При использовании одного из этих дизайнов лечебные единицы и порядок исследований должны быть рандомизированы, насколько это позволяет дизайн. Например, одна из рекомендаций состоит в том, что ортогональный массив подходящего размера выбирается случайным образом из имеющихся, а затем рандомизируется порядок выполнения.

Контроль качества

Ортогональные массивы сыграли центральную роль в развитии Методы Тагучи к Геничи Тагучи, который произошел во время его посещения Индийский статистический институт в начале 1950-х гг. Его методы были успешно применены и приняты промышленными предприятиями Японии и Индии, а затем были приняты промышленностью США, хотя и с некоторыми оговорками.

Тестирование

Проверка ортогональных массивов это тестирование черного ящика техника, которая является систематической, статистический способ тестирование программного обеспечения.[14][15] Он используется, когда количество входов в систему относительно невелико, но слишком велико для проведения исчерпывающего тестирования всех возможных входов в систему. системы.[14] Это особенно эффективно при поиске ошибок, связанных с неисправным логика в компьютер программные системы.[14] Ортогональные массивы можно применять в пользовательский интерфейс тестирование системное тестирование, регресс тестирование и тестирование производительности. перестановки уровней факторов, составляющих одно лечение, выбраны таким образом, чтобы их ответы не коррелировали, и, следовательно, каждое лечение дает уникальный фрагмент Информация. Чистый эффект от организации эксперимента при таком лечении состоит в том, что одна и та же информация собирается за минимальное количество эксперименты.

Смотрите также

Примечания

  1. ^ Стинсон 2003, стр. 225
  2. ^ а б c Денес и Кидуэлл 1974, стр. 191
  3. ^ Стинсон 2003, стр. 140–141, раздел 6.5.1
  4. ^ Денес и Кидуэлл 1974, стр. 187 приписывают определение Кишен (1950 г., стр. 21)
  5. ^ В предпочтительном определении комбинаторов каждая строка, столбец и файл будет содержать перестановку символов, но это только особый тип латинского куба, называемый перестановочный куб.
  6. ^ Денес и Кидуэлл 1974, стр. 189
  7. ^ Рагхаварао 1988, стр. 9
  8. ^ Рагхаварао 1988, стр. 10
  9. ^ Стинсон 2003, стр. 225, теорема 10.2
  10. ^ Стинсон 2003, стр. 226, Пример 10.3
  11. ^ Стинсон 2003, стр. 231, теорема 10.17
  12. ^ Стинсон 2003, стр. 262, теорема 11.5
  13. ^ Улица и улица 1987, стр. 194, Раздел 9.2
  14. ^ а б c Прессман, Роджер S (2005). Программная инженерия: подход практикующего специалиста (6-е изд.). Макгроу – Хилл. ISBN  0-07-285318-2.
  15. ^ Пхадке, Мадхав С. «Планирование эффективных тестов программного обеспечения». Phadke Associates, Inc. Многочисленные статьи об использовании ортогональных массивов для тестирования программного обеспечения и систем.

Рекомендации

  • Box, G.E.P .; Хантер, W. G .; Хантер, Дж. С. (1978). Статистика для экспериментаторов: введение в проектирование, анализ данных и построение моделей. Джон Уайли и сыновья.
  • Dénes, J .; Кидвелл, А. Д. (1974), Латинские квадраты и их приложения, Нью-Йорк-Лондон: Academic Press, ISBN  0-12-209350-X, МИСТЕР  0351850
  • Hedayat, A.S .; Sloane, штат Нью-Джерси; Штуфкен, Дж. (1999), Ортогональные массивы, теория и приложения, Нью-Йорк: Springer
  • Кишен, К. (1942), "О латинских и гипер-греческих кубах и гиперкубах", Текущая наука, 11: 98–99
  • Кишен, К. (1950), "О построении латинских и гипер-греко-латинских кубов и гиперкубов", J. Indian Soc. Agric. Статистика, 2: 20–48
  • Рагхаварао, Дамараджу (1988). Конструкции и комбинаторные задачи при планировании экспериментов. (исправленное переиздание изд. Wiley 1971 г.). Нью-Йорк: Дувр.CS1 maint: ref = harv (связь)
  • Рагхаварао, Дамараджу и Пэджетт, Л. (2005). Блочные конструкции: анализ, комбинаторика и приложения. World Scientific.CS1 maint: несколько имен: список авторов (связь)
  • Рао, C.R. (1946), «Гиперкубы силы d, приводящие к ошибочным планам факторных экспериментов», Бюллетень Калькуттского математического общества, 38: 67–78
  • Рао, C.R. (1947), "Факторные эксперименты, производные от комбинаторного расположения массивов", Приложение к Журналу Королевского статистического общества, 9: 128–139, JSTOR  2983576
  • Стинсон, Дуглас Р. (2003), Комбинаторные конструкции: конструкции и анализ, Нью-Йорк: Springer, ISBN  0-387-95487-2
  • Улица, Энн Пенфолд & Улица, Дебора Дж. (1987). Комбинаторика экспериментального дизайна. Оксфорд У. П. [Кларендон]. ISBN  0-19-853256-3.

внешняя ссылка

Эта статья включаетматериалы общественного достояния от Национальный институт стандартов и технологий интернет сайт https://www.nist.gov.