Дизъюнктная матрица

В математике логическая матрица может быть описана как d -дизъюнктная и/или d -разделимая . Эти концепции играют ключевую роль в математической области неадаптивного группового тестирования .

В математической литературе d -дизъюнктные матрицы могут также называться суперпозиционными кодами ^[1] или d -бесконечными семействами ^[2] .

По словам Чена и Хванга (2006), ^[3]

• Матрица называется d -разделимой, если никакие два набора из d столбцов не имеют одинаковой логической суммы.
• Матрица называется -разделимой (то есть d с чертой сверху), если никакие два набора из d или менее столбцов не имеют одинаковой логической суммы.${\displaystyle {\overline {d}}}$
• Матрица называется d -дизъюнктной, если ни один набор из d столбцов не имеет булевой суммы, которая является надмножеством любого другого отдельного столбца.

Следующие отношения являются «общеизвестными»: ^[3]

• Каждая -разделимая матрица также -дизъюнктна. ^[3]${\displaystyle {\overline {d+1}}}$${\displaystyle д}$
• Каждая -дизъюнктная матрица также -разделима. ^[3]${\displaystyle д}$${\displaystyle {\overline {d}}}$
• Каждая -разделимая матрица также -разделима (по определению).${\displaystyle {\overline {d}}}$${\displaystyle д}$

Следующая матрица является 2-разделимой, поскольку каждая пара столбцов имеет отдельную сумму. Например, булева сумма (то есть побитовое ИЛИ ) первых двух столбцов равна ; эта сумма не достижима как сумма любой другой пары столбцов в матрице.${\displaystyle 6\times 8}$${\displaystyle 110000\lor 001100=111100}$

Однако эта матрица не является 3-разделимой, поскольку сумма столбцов 1, 2 и 3 (а именно ) равна сумме столбцов 1, 4 и 5.${\displaystyle 111111}$

Эта матрица также не является -разделимой, поскольку сумма столбцов 1 и 8 (а именно ) равна сумме одного столбца 1. Фактически, ни одна матрица со столбцом, состоящим из одних нулей, не может быть -разделимой для любого .${\displaystyle {\overline {2}}}$${\displaystyle 110000}$${\displaystyle {\overline {d}}}$${\displaystyle d\geq 1}$

${\displaystyle \quad \left[{\begin{array}{cccccccc}1&0&0&1&1&0&0&0\\1&0&0&0&0&1&1&0\\0&1&0&1&0&1&0&0\\0&1&0&0&1&0&1&0\\0&0&1&0&1&1&0&0\\0&0&1&1&0&0&1&0\\\end{array}}\right]}$

Следующая матрица является -разделимой (и, следовательно, 2-дизъюнктной), но не 3-дизъюнктной.${\displaystyle 6\times 4}$${\displaystyle {\overline {3}}}$

${\displaystyle \quad \left[{\begin{array}{cccc}1&0&0&1\\1&0&1&0\\0&1&1&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\\end{array}}\right]}$

Существует 15 возможных способов выбрать 3 или менее столбцов из этой матрицы, и каждый выбор приводит к различной булевой сумме:

Однако сумма столбцов 2, 3 и 4 (а именно ) является надмножеством столбца 1 (а именно ), что означает, что эта матрица не является 3-дизъюнктной.${\displaystyle 111111}$${\displaystyle 110000}$

Проблема неадаптивного группового тестирования постулирует, что у нас есть тест, который может сказать нам, для любого набора элементов, содержит ли этот набор дефектный элемент. Нас просят придумать ряд группировок, которые могут точно идентифицировать все дефектные элементы в партии из n элементов, некоторые d из которых дефектные.

-разделимая матрица со строками и столбцами кратко описывает, как использовать t- тесты для поиска дефектных изделий в партии из n , где известно, что количество дефектных изделий равно точно d .${\displaystyle d}$${\displaystyle t}$${\displaystyle n}$

-дизъюнктная матрица (или, в более общем смысле, любая -разделимая матрица) со строками и столбцами кратко описывает, как использовать t- тесты для поиска дефектных изделий в партии из n , где известно, что количество дефектных изделий не превышает d .${\displaystyle d}$${\displaystyle {\overline {d}}}$${\displaystyle t}$${\displaystyle n}$

Для заданных n и d число строк t в наименьшей d -разделимой матрице может (согласно современным знаниям) быть меньше числа строк t в наименьшей d -дизъюнктной матрице, но асимптотически они находятся в пределах постоянного множителя друг от друга. ^[3] Кроме того, если матрица должна использоваться для практического тестирования, необходим некоторый алгоритм, который может «декодировать» результат теста (то есть булеву сумму, такую ​​как ) в индексы дефектных элементов (то есть уникальный набор столбцов, которые производят эту булеву сумму). Для произвольных d -дизъюнктных матриц известны алгоритмы декодирования с полиномиальным временем ; наивный алгоритм — . ^[4] Для произвольных d -разделимых, но не d -дизъюнктных матриц наиболее известные алгоритмы декодирования — экспоненциальные по времени. ^[3]${\displaystyle t\times n}$${\displaystyle t\times n}$${\displaystyle 111100}$${\displaystyle O(nt)}$

Порат и Ротшильд (2008) представляют детерминированный алгоритм для построения d -непересекающейся матрицы с n столбцами и строками. ^[5]${\displaystyle O(nt)}$${\displaystyle \Theta (d^{2}\ln n)}$

• Групповое тестирование
• Связанный код
• Сжатое зондирование

• Книга Атри Рудры «Коды с исправлением ошибок: комбинаторика, алгоритмы и приложения» (весна 2011 г.), глава 17. Архивировано 2 апреля 2015 г. на Wayback Machine
• Дьячков А.Г., Рыков В.В. (1982). Границы длины дизъюнктивных кодов. Проблемы передачи информации, 18(3), 7–13.
• Дьячков А.Г., Рашад А.М., Рыков В.В. (1989). Наложенные коды расстояний. Проблемы управления и теории информации, 18(4), 237–250.
• Фюреди, Золтан (1996). «О семействах без r-покрытий». Журнал комбинаторной теории . Серия A. 73 (1): 172– 173. doi : 10.1006/jcta.1996.0012 .