Matriz disyuntiva

En matemáticas, una matriz lógica puede describirse como d -disyuntiva y/o d -separable . Estos conceptos desempeñan un papel fundamental en el área matemática de las pruebas grupales no adaptativas .

En la literatura matemática, las matrices d -disyuntas también pueden denominarse códigos superpuestos ^[1] o familias d -libres de cobertura . ^[2]

Según Chen y Hwang (2006), ^[3]

• Se dice que una matriz es d -separable si no hay dos conjuntos de d columnas que tengan la misma suma booleana.
• Se dice que una matriz es -separable (es decir, d con una línea superior) si no hay dos conjuntos de d o menos columnas que tengan la misma suma booleana. ${\displaystyle {\overline {d}}}$
• Se dice que una matriz es d -disyunta si ningún conjunto de d columnas tiene una suma booleana que sea un superconjunto de cualquier otra columna individual.

Las siguientes relaciones son "bien conocidas": ^[3]

• Toda matriz -separable es también -disyunta. ^[3] ${\displaystyle {\overline {d+1}}}$ ${\displaystyle d}$
• Toda matriz -disyunta es también -separable. ^[3] ${\displaystyle d}$ ${\displaystyle {\overline {d}}}$
• Toda matriz -separable es también -separable (por definición). ${\displaystyle {\overline {d}}}$ ${\displaystyle d}$

Ejemplos concretos

La siguiente matriz es separable en dos, porque cada par de columnas tiene una suma distinta. Por ejemplo, la suma booleana (es decir, el OR bit a bit ) de las dos primeras columnas es ; esa suma no se puede obtener como la suma de ningún otro par de columnas en la matriz. ${\displaystyle 6\times 8}$ ${\displaystyle 110000\lor 001100=111100}$

Sin embargo, esta matriz no es 3-separable, porque la suma de las columnas 1, 2 y 3 (es decir , ) es igual a la suma de las columnas 1, 4 y 5. ${\displaystyle 111111}$

Esta matriz tampoco es -separable, porque la suma de las columnas 1 y 8 (es decir, ) es igual a la suma de la columna 1 solamente. De hecho, ninguna matriz con una columna de todos ceros puede ser -separable para ningún . ${\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]}$

La siguiente matriz es -separable (y por lo tanto 2-disyunta) pero no 3-disyunta. ${\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]}$

Hay 15 formas posibles de elegir 3 o menos columnas de esta matriz, y cada elección conduce a una suma booleana diferente:

Sin embargo, la suma de las columnas 2, 3 y 4 (es decir, ) es un superconjunto de la columna 1 (es decir, ), lo que significa que esta matriz no es 3-disyunta. ${\displaystyle 111111}$ ${\displaystyle 110000}$

Aplicación ded-Separabilidad para pruebas de grupo

El problema de la prueba de grupo no adaptativa postula que tenemos una prueba que puede decirnos, para cualquier conjunto de elementos, si ese conjunto contiene un elemento defectuoso . Se nos pide que elaboremos una serie de agrupaciones que puedan identificar exactamente todos los elementos defectuosos en un lote de n elementos en total, algunos de los cuales d son defectuosos.

Una matriz separable con filas y columnas describe de forma concisa cómo utilizar pruebas t para encontrar los artículos defectuosos en un lote de n , donde se sabe que el número de artículos defectuosos es exactamente d . ${\displaystyle d}$ ${\displaystyle t}$ ${\displaystyle n}$

Una matriz disyunta (o, más generalmente, cualquier matriz separable) con filas y columnas describe de manera concisa cómo utilizar pruebas t para encontrar los artículos defectuosos en un lote de n , donde se sabe que el número de artículos defectuosos no es mayor que d . ${\displaystyle d}$ ${\displaystyle {\overline {d}}}$ ${\displaystyle t}$ ${\displaystyle n}$

Preocupaciones prácticas y resultados publicados

Para un n y d dados , el número de filas t en la matriz d -separable más pequeña puede (según el conocimiento actual) ser menor que el número de filas t en la matriz d -disyunta más pequeña , pero en asintóticamente están dentro de un factor constante entre sí. ^[3] Además, si la matriz se va a utilizar para pruebas prácticas, se necesita algún algoritmo que pueda "decodificar" un resultado de prueba (es decir, una suma booleana como ) en los índices de los elementos defectuosos (es decir, el conjunto único de columnas que producen esa suma booleana). Para matrices d -disyuntas arbitrarias, se conocen algoritmos de decodificación de tiempo polinomial ; el algoritmo ingenuo es . ^{[4] Para matrices} d -separables arbitrarias pero no d -disyuntas, los algoritmos de decodificación más conocidos son el tiempo exponencial. ^[3] ${\displaystyle t\times n}$ ${\displaystyle t\times n}$ ${\displaystyle 111100}$ ${\displaystyle O(nt)}$

Porat y Rothschild (2008) presentan un algoritmo de tiempo determinista para construir una matriz d -disjunta con n columnas y filas. ^[5] ${\displaystyle O(nt)}$ ${\displaystyle \Theta (d^{2}\ln n)}$

Véase también

• Pruebas grupales
• Código concatenado
• Detección comprimida

Referencias

1. De Bonis, Annalisa; Vaccaro, Ugo (2003). "Construcciones de códigos superpuestos generalizados con aplicaciones a pruebas grupales y resolución de conflictos en canales de acceso múltiple". Ciencias de la Computación Teórica . 306 (1–3): 223–243. doi :10.1016/S0304-3975(03)00281-0. MR  2000175.
2. Paul Erdős ; Péter Frankl ; Zoltán Füredi (1985). "Familias de conjuntos finitos en las que ningún conjunto está cubierto por la unión de otros r" (PDF) . Israel Journal of Mathematics . 51 (1–2): 79–89. doi : 10.1007/BF02772959 . ISSN  0021-2172.
3. Hong-Bin Chen; Frank Hwang (21 de diciembre de 2006). "Explorando el eslabón perdido entre matrices d-separables, d-separables y d-disjuntas". Matemáticas Aplicadas Discretas . 155 (5): 662–664. CiteSeerX 10.1.1.848.5161 . doi : 10.1016/j.dam.2006.10.009 . MR  2303978. 
4. Piotr Indyk ; Hung Q. Ngo; Atri Rudra (2010). "Pruebas grupales no adaptativas decodificables de manera eficiente". Actas del 21.º Simposio ACM-SIAM sobre algoritmos discretos (SODA) . hdl :1721.1/63167. ISSN  1071-9040.
5. Ely Porat; Amir Rothschild (2008). "Esquemas de prueba de grupos combinatorios no adaptativos explícitos". Actas del 35.º Coloquio internacional sobre autómatas, lenguajes y programación (ICALP) : 748–759. arXiv : 0712.3876 . Código Bibliográfico :2007arXiv0712.3876P.

Lectura adicional

• Libro de Atri Rudra sobre códigos de corrección de errores: combinatoria, algoritmos y aplicaciones (primavera de 2011), capítulo 17 Archivado el 2 de abril de 2015 en Wayback Machine.
• Dýachkov, AG y Rykov, VV (1982). Límites de la longitud de los códigos disyuntivos. Problemy Peredachi Informatsii [Problemas de transmisión de información], 18(3), 7–13.
• Dýachkov, AG, Rashad, AM y Rykov, VV (1989). Códigos de distancia superpuestos. Problemy Upravlenija i Teorii Informacii [Problemas de control y teoría de la información], 18(4), 237–250.
• Füredi, Zoltán (1996). "Sobre familias sin cobertura r". Journal of Combinatorial Theory . Serie A. 73 (1): 172–173. doi : 10.1006/jcta.1996.0012 .