Войти
В математике ортогональный массив является «таблицей» (массив), элементы которого берутся из фиксированного конечного набора символов (обычно {1,2,..., n}), организованных таким образом, что существует целое число t, так что для каждого выбора t столбцов В таблице все упорядоченные t- кортежи символов, сформированные путем взятия записей в каждой строке, ограниченной этими столбцами, появляются одинаковое количество раз. Число t называется силой ортогонального массива. Вот простой пример ортогонального массива с набором символов {1,2} и степенью 2:
| 1 | 1 | 1 |
| 2 | 2 | 1 |
| 1 | 2 | 2 |
| 2 | 1 | 2 |
Обратите внимание, что четыре упорядоченных пары (2-кортежи), образованные строками, ограниченными первой и третьи столбцы, а именно (1,1), (2,1), (1,2) и (2,2), представляют собой все возможные упорядоченные пары из двух наборов элементов, и каждый появляется ровно один раз. Второй и третий столбцы будут содержать (1,1), (2,1), (2,2) и (1,2); опять же, все возможные упорядоченные пары появляются по одному разу. То же утверждение было бы, если бы использовались первый и второй столбцы. Таким образом, это ортогональный массив силы два.
Ортогональные массивы обобщают идею взаимно ортогональных латинских квадратов в табличной форме. Эти массивы имеют много связей с другими комбинаторными схемами и находят применение в статистическом планировании экспериментов, теории кодирования, криптографии и различных типах тестирования программного обеспечения..
A t- (v, k, λ) ортогональный массив (t ≤ k) - это массив λv × k, элементы которого выбираются из множества X с v точками, так что в каждом подмножестве t столбцов массива каждый t-набор точек X появляется ровно в λ строках.
В этом формальном определении предусмотрено повторение t-кортежей (λ - количество повторов), а количество строк определяется другими параметрами.
Во многих приложениях этим параметрам присвоены следующие имена:
Ортогональный массив является простым, если он не содержит повторяющихся строк.
Ортогональный массив является линейным, если X является конечным полем порядка q, Fq(q - степень простого числа), а строки массива образуют подпространство вектора пробел (Fq).
Любой линейный ортогональный массив прост.
Пример ортогонального массива 2- (4, 5, 1); план силы 2, 4 уровня индекса 1 с 16 пробегами.
| 1 | 1 | 1 | 1 | 1 |
| 1 | 2 | 2 | 2 | 2 |
| 1 | 3 | 3 | 3 | 3 |
| 1 | 4 | 4 | 4 | 4 |
| 2 | 1 | 4 | 2 | 3 |
| 2 | 2 | 3 | 1 | 4 |
| 2 | 3 | 2 | 4 | 1 |
| 2 | 4 | 1 | 3 | 2 |
| 3 | 1 | 2 | 3 | 4 |
| 3 | 2 | 1 | 4 | 3 |
| 3 | 3 | 4 | 1 | 2 |
| 3 | 4 | 3 | 2 | 1 |
| 4 | 1 | 3 | 4 | 2 |
| 4 | 2 | 4 | 3 | 1 |
| 4 | 3 | 1 | 2 | 4 |
| 4 | 4 | 2 | 1 | 3 |
Пример ортогонального массива 2- (3,5,3) (записанный как его транспонировать для удобства просмотра):
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| 0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 |
| 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 |
| 0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 0 | 0 | 0 |
| 0 | 1 | 2 | 1 | 2 | 0 | 2 | 0 | 1 | 0 | 1 | 2 | 1 | 2 | 0 | 2 | 0 | 1 | 0 | 1 | 2 | 1 | 2 | 0 | 2 | 0 | 1 |
Любые t- ( v, t, λ) ортогональный массив будет считаться тривиальным, поскольку их легко построить, просто перечислив все t-наборы v-набора λ раз.
Ортогональный массив 2- (v, k, 1) эквивалентен набору k - 2 взаимно ортогональных латинских квадратов порядка v.
Ортогональные массивы с индексом 1 и степенью 2 также известны в статистической литературе как планы гипер-греко-латинского квадрата.
Пусть A будет ортогональным массивом степени 2, индекс 1 на v-множестве элементов, идентифицированных с помощью набора натуральных чисел {1,..., v}. Выберите и исправьте по порядку два столбца A, которые называются столбцами индексации. Все упорядоченные пары (i, j) с 1 ≤ i, j ≤ v появляются ровно один раз в строках столбцов индексации. Возьмите любой другой столбец A и создайте квадратный массив, запись которого в позиции (i, j) является записью A в этом столбце в строке, которая содержит (i, j) в столбцах индексации A. Полученный квадрат представляет собой Латинский квадрат порядка v. Например, рассмотрим ортогональный массив 2- (3,4,1):
| 1 | 1 | 1 | 1 |
| 1 | 2 | 2 | 2 |
| 1 | 3 | 3 | 3 |
| 2 | 1 | 2 | 3 |
| 2 | 2 | 3 | 1 |
| 2 | 3 | 1 | 2 |
| 3 | 1 | 3 | 2 |
| 3 | 2 | 1 | 3 |
| 3 | 3 | 2 | 1 |
Выбрав столбцы 3 и 4 (в указанном порядке) в качестве столбцов индексации, первый column производит латинский квадрат,
| 1 | 2 | 3 |
| 3 | 1 | 2 |
| 2 | 3 | 1 |
, тогда как второй столбец производит латинский квадрат,
| 1 | 3 | 2 |
| 3 | 2 | 1 |
| 2 | 1 | 3 |
Латинские квадраты, полученные таким образом из ортогонального массива, будут ортогональными латинскими квадратами, поэтому k - 2 столбца, кроме столбцов индексации, будут создать набор из k - 2 взаимно ортогональных латинских квадратов.
Эта конструкция полностью обратима, поэтому ортогональные массивы степени 2 и индекса 1 могут быть построены из наборов взаимно ортогональных латинских квадратов.
Ортогональные массивы обеспечивают единообразный способ описания этих разнообразных объектов, находящихся в интерес к статистическому плану экспериментов.
Как упоминалось в предыдущем разделе, латинский квадрат порядка n можно рассматривать как 2- (n, 3, 1) ортогональный массив. Фактически, ортогональный массив может привести к шести латинским квадратам, поскольку любую упорядоченную пару отдельных столбцов можно использовать в качестве столбцов индексации. Однако все они являются изотопными и считаются эквивалентными. Для конкретности мы всегда будем предполагать, что первые два столбца в их естественном порядке используются в качестве столбцов индексации.
В статистической литературе Латинский куб представляет собой трехмерную матрицу размером n × n × n, состоящую из n слоев, каждый из которых имеет n строк и n такие столбцы, что появившиеся n различных элементов повторяются n раз и располагаются так, что в каждом слое, параллельном каждой из трех пар противоположных граней куба, появляются все n различных элементов, и каждый из них повторяется ровно n раз в этом слое.
Обратите внимание, что с этим определением слой латинского куба не обязательно должен быть латинским квадратом. Фактически, ни одна строка, столбец или файл (ячейки определенной позиции в разных слоях) не должны быть перестановкой n символов.
Латинский куб порядка n эквивалентен в ортогональный массив 2- (n, 4, n).
Два латинских куба порядка n ортогональны, если среди n пар элементов, выбранных из соответствующих ячеек двух кубов, каждая отдельная упорядоченная пара элементы встречается ровно n раз.
Набор из k - 3 взаимно ортогональных латинских кубов порядка n эквивалентен ортогональному массиву 2- (n, k, n).
Пример пары взаимно ортогональных латинских кубов кубы третьего порядка были даны как 2- (3,5,3) ортогональный массив в разделе Примеры выше.
В отличие от случая с латинскими квадратами, в котором нет ограничений, столбцы индексации представления ортогонального массива латинского куба должны быть выбраны так, чтобы сформировать 3- (n, 3,1) ортогональный массив.
M-мерный Латинский гиперкуб порядка n r-го класса является m-мерной матрицей n × n ×... × n, имеющей n различные элементы, каждый из которых повторяется n раз, и такие, что каждый элемент встречается ровно n раз в каждом из своих m наборов n параллельных (m - 1) -мерных линейных подпространств (или «слоев»). Два таких латинских гиперкуба одного порядка n и класса r, обладающие тем свойством, что при наложении одного на другой каждый элемент одного встречается ровно n раз с каждым элементом другого, называются ортогональными.
Набор из k - m взаимно ортогональных m-мерных латинских гиперкубов порядка n эквивалентен ортогональному массиву 2- (n, k, n), где столбцы индексации образуют m- (n, m, 1) ортогональный массив.
Понятия латинских квадратов и взаимно ортогональных латинских квадратов были обобщены на латинские кубы и гиперкубы, а также на ортогональные латинские кубы и гиперкубы Кишен (1942). Рао (1946) обобщил эти результаты на силу t. Настоящее понятие ортогонального массива как обобщение этих идей, созданное С. Р. Рао, появляется в Рао (1947).
Если существует матрица Адамара порядка 4m, то существует 2- (2, 4m - 1, m) ортогональный массив.
Пусть H - матрица Адамара порядка 4m в стандартизированной форме (все элементы первой строки и столбца равны +1). Удалите первую строку и возьмите транспонирование, чтобы получить желаемый ортогональный массив.
Стандартизированная матрица Адамара порядка 8 ниже (± 1 элемент обозначен только знаком),
| + | + | + | + | + | + | + | + |
| + | + | + | + | − | − | − | − |
| + | + | − | − | + | + | − | − |
| + | + | − | − | − | − | + | + |
| + | − | + | − | + | − | + | − |
| + | − | + | − | − | + | − | + |
| + | − | − | + | + | − | − | + |
| + | − | − | + | − | + | + | − |
дает 2 - (2,7,2) ортогональный массив:
| + | + | + | + | + | + | + |
| + | + | + | − | − | − | − |
| + | − | − | + | + | − | − |
| + | − | − | − | − | + | + |
| − | + | − | + | − | + | − |
| − | + | − | − | + | − | + |
| − | − | + | + | − | − | + |
| − | − | + | − | + | + | − |
Используя столбцы 1, 2 и 4 в качестве столбцов индексации, оставшиеся столбцы создают четыре взаимно ортогональных латинских куба порядка 2.
Пусть C ⊆ (Fq), будет линейным кодом размерности m с минимальным расстоянием d. Тогда C (ортогональное дополнение к векторному подпространству C) является (линейным) (d - 1) - (q, n, λ) ортогональным массивом, где. λ = q.
Совместное использование секрета (также называемое разделением секрета ) состоит из методов распределения секрета среди группы участников, каждому из которых выделяется доля секрета. Секрет может быть восстановлен только тогда, когда достаточное количество долей, возможно, разных типов, объединены вместе; отдельные акции не используются сами по себе. Схема разделения секрета идеальна, если каждая группа участников, которая не соответствует критериям для получения секрета, не имеет дополнительных знаний о том, что такое секрет, чем человек без доли.
В одном типе схемы разделения секрета есть один дилер и n игроков. Дилер выдает доли секрета игрокам, но только при выполнении определенных условий игроки смогут восстановить секрет. Дилер выполняет это, давая каждому игроку долю таким образом, что любая группа из t (для порога) или более игроков может вместе восстановить секрет, но никакая группа из менее чем t игроков не может. Такая система называется (t, n) -пороговой схемой.
Ортогональный массив t- (v, n + 1, 1) может использоваться для построения идеальной (t, n) -пороговой схемы.
A факторный эксперимент - это статистически структурированный эксперимент, в котором несколько факторов (полив уровни, антибиотики, удобрения и т. д.) применяются к каждой экспериментальной единице на разных (но интегральных) уровнях (высокий, низкий или различные промежуточные уровни). В полном факторном эксперименте необходимо протестировать все комбинации уровней факторов, но для минимизации мешающих влияний уровни должны варьироваться в рамках любого экспериментального цикла.
Ортогональный массив степени 2 можно использовать для разработки факторного эксперимента. Столбцы представляют различные факторы, а записи - уровни, на которых факторы могут применяться (при условии, что все факторы могут применяться на одном и том же количестве уровней). Экспериментальный прогон представляет собой строку ортогонального массива, то есть применяют соответствующие коэффициенты на уровнях, которые появляются в строке. При использовании одного из этих дизайнов лечебные единицы и порядок исследований должны быть рандомизированы, насколько это позволяет дизайн. Например, одна из рекомендаций состоит в том, что ортогональный массив подходящего размера выбирается случайным образом из имеющихся, а затем рандомизируется порядок выполнения.
Ортогональные массивы сыграли центральную роль в разработке методов Тагучи Геничи Тагучи, которые имели место во время его посещения Индийский статистический институт в начале 1950-х годов. Его методы были успешно применены и приняты промышленными предприятиями Японии и Индии, а затем были приняты промышленностью США, хотя и с некоторыми оговорками.
Тестирование ортогонального массива - это метод тестирования черного ящика, который представляет собой систематический, статистический способ тестирования программного обеспечения. Он используется, когда количество входов в систему относительно невелико, но слишком велико, чтобы можно было провести исчерпывающее тестирование каждого возможного входа в системы. Это особенно эффективно при обнаружении ошибок, связанных с неисправной логикой в компьютере программных системах. Ортогональные массивы могут применяться в пользовательском интерфейсе тестировании, тестировании системы, регрессионном тестировании и тестировании производительности. Перестановки уровней факторов, составляющие одно лечение, выбираются таким образом, чтобы их ответы не коррелировали, и, следовательно, каждое лечение дает уникальный фрагмент информации. Чистый эффект от организации эксперимента при таком лечении состоит в том, что та же самая часть информации собирается в минимальном количестве экспериментов.
В эту статью включены материалы общественного достояния с веб-сайта Национального института стандартов и технологий https: / /www.nist.gov.
