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

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

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

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

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

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

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

Конкретные примеры

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

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

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

$\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]$

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

$\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 или меньше столбцов из этой матрицы, и каждый выбор приводит к различной логической сумме:

столбцы	булева сумма	столбцы	булева сумма
никто	000000	2,3	011110
1	110000	2,4	101101
2	001100	3,4	111011
3	011010	1,2,3	111110
4	100001	1,2,4	111101
1,2	111100	1,3,4	111011
1,3	111010	2,3,4	111111
1,4	110001

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

Применение d -сепарабельности к групповому тестированию

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

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

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

Практические проблемы и опубликованные результаты

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

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

См. также

Ссылки

^ Де Бонис, Анналиса; Ваккаро, Уго (2003). «Конструкции обобщенных наложенных кодов с приложениями для группового тестирования и разрешения конфликтов в каналах множественного доступа». Теоретическая информатика . 306 (1–3): 223–243. дои : 10.1016/S0304-3975(03)00281-0 . МР 2000175 .
^ Пол Эрдеш ; Питер Франкл ; Золтан Фюреди (1985). «Семейства конечных множеств, в которых ни одно множество не покрывается объединением r других» (PDF) . Израильский математический журнал . 51 (1–2): 79–89. дои : 10.1007/BF02772959 . ISSN 0021-2172 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж Хун-Бин Чен; Фрэнк Хван (21 декабря 2006 г.). «Исследование недостающего звена между d -разделимыми, d -разделимыми и d -дизъюнктными матрицами» . Дискретная прикладная математика . 155 (5): 662–664. CiteSeerX 10.1.1.848.5161 . дои : 10.1016/j.dam.2006.10.009 . МР 2303978 .
^ Петр Индик ; Хунг К. Нго; Атри Рудра (2010). «Эффективно декодируемое неадаптивное групповое тестирование». Материалы 21-го симпозиума ACM-SIAM по дискретным алгоритмам (SODA) . hdl : 1721.1/63167 . ISSN 1071-9040 .
^ Эли Порат; Амир Ротшильд (2008). «Явные неадаптивные схемы комбинаторного группового тестирования». Материалы 35-го Международного коллоквиума по автоматам, языкам и программированию (ICALP) : 748–759. arXiv : 0712.3876 . Бибкод : 2007arXiv0712.3876P .

Дальнейшее чтение

Книга Атри Рудры «Коды, исправляющие ошибки: комбинаторика, алгоритмы и приложения» (весна 201 г.), глава 17. Архивировано 2 апреля 2015 г. в Wayback Machine.
Dýachkov, A. G., & Rykov, V. V. (1982). Bounds on the length of disjunctive codes. Problemy Peredachi Informatsii [Problems of Information Transmission], 18(3), 7–13.
Dýachkov, A. G., Rashad, A. M., & Rykov, V. V. (1989). Superimposed distance codes. Problemy Upravlenija i Teorii Informacii [Problems of Control and Information Theory], 18(4), 237–250.
Фюреди, Золтан (1996). «О семьях без прикрытия» . Журнал комбинаторной теории . Серия А. 73 (1): 172–173. дои : 10.1006/jcta.1996.0012 .

[DeBonisVaccaro2003-1] Де Бонис, Анналиса; Ваккаро, Уго (2003). «Конструкции обобщенных наложенных кодов с приложениями для группового тестирования и разрешения конфликтов в каналах множественного доступа». Теоретическая информатика . 306 (1–3): 223–243. дои : 10.1016/S0304-3975(03)00281-0 . МР 2000175 .

[ErdoesEtAl1985-2] Пол Эрдеш ; Питер Франкл ; Золтан Фюреди (1985). «Семейства конечных множеств, в которых ни одно множество не покрывается объединением r других» (PDF) . Израильский математический журнал . 51 (1–2): 79–89. дои : 10.1007/BF02772959 . ISSN 0021-2172 .

[ChenHwang2006-3] Jump up to: ^а ^б ^с ^д ^и ^ж Хун-Бин Чен; Фрэнк Хван (21 декабря 2006 г.). «Исследование недостающего звена между d -разделимыми, d -разделимыми и d -дизъюнктными матрицами» . Дискретная прикладная математика . 155 (5): 662–664. CiteSeerX 10.1.1.848.5161 . дои : 10.1016/j.dam.2006.10.009 . МР 2303978 .

[Indyk2010-4] Петр Индик ; Хунг К. Нго; Атри Рудра (2010). «Эффективно декодируемое неадаптивное групповое тестирование». Материалы 21-го симпозиума ACM-SIAM по дискретным алгоритмам (SODA) . hdl : 1721.1/63167 . ISSN 1071-9040 .

[Porat2008-5] Эли Порат; Амир Ротшильд (2008). «Явные неадаптивные схемы комбинаторного группового тестирования». Материалы 35-го Международного коллоквиума по автоматам, языкам и программированию (ICALP) : 748–759. arXiv : 0712.3876 . Бибкод : 2007arXiv0712.3876P .

[1]

[2]

[3]

[4]

[5]