Matriz disyunta

En matemáticas, una matriz lógica puede describirse como d -disjunta 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 -disjuntas 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 superpuesta) 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 -disjunta si ningún conjunto de d columnas tiene una suma booleana que sea un superconjunto de cualquier otra columna.

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

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

Ejemplos concretos

La siguiente matriz es separable en 2, 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 de la matriz. ${\displaystyle 6\times 8}$ ${\displaystyle 110000\lor 001100=111100}$

Sin embargo, esta matriz no es separable en 3, 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 sola. De hecho, ninguna matriz con una columna de 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-disjunta) pero no 3-disjunta. ${\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 está disyunta en 3. ${\displaystyle 111111}$ ${\displaystyle 110000}$

Aplicación de d -separabilidad a pruebas grupales

El problema de las pruebas grupales no adaptativas postula que tenemos una prueba que puede decirnos, para cualquier conjunto de artículos, si ese conjunto contiene un artículo defectuoso . Se nos pide que elaboremos una serie de agrupaciones que puedan identificar exactamente todos los artículos defectuosos en un lote de n artículos en total, algunos d de los cuales son defectuosos.

Una matriz separable con filas y columnas describe de manera concisa cómo usar 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 disjunta (o, más generalmente, cualquier matriz separable) con filas y columnas describe de manera concisa cómo usar 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 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 -disjunta más pequeña , pero asintóticamente están dentro de una constante factor uno del otro. ^[3] Además, si la matriz se va a utilizar para pruebas prácticas, se necesita algún algoritmo que pueda "decodificar" el resultado de una prueba (es decir, una suma booleana como ) en los índices de los artículos defectuosos (es decir, el conjunto único de columnas que producen esa suma booleana). Para matrices d -disjuntas arbitrarias , se conocen algoritmos de decodificación en tiempo polinomial ; el algoritmo ingenuo es . ^[4] Para matrices arbitrarias d -separables pero no d -disjuntas, los algoritmos de decodificación más conocidos son los de tiempo exponencial. ^[3] ${\displaystyle t\times n}$ ${\displaystyle t\times n}$ ${\displaystyle 111100}$ ${\displaystyle O(nt)}$

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

Ver 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 múltiples canales de acceso". Informática Teórica . 306 (1–3): 223–243. doi :10.1016/S0304-3975(03)00281-0. SEÑOR  2000175.
2. Paul Erdős ; Peter Frankl ; Zoltán Furedi (1985). «Familias de conjuntos finitos en las que ningún conjunto está cubierto por la unión de otros» (PDF) . Revista Israelí de Matemáticas . 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ática Aplicada Discreta . 155 (5): 662–664. CiteSeerX 10.1.1.848.5161 . doi : 10.1016/j.dam.2006.10.009 . SEÑOR  2303978. 
4. Piotr Indyk ; Hung Q. Ngo; Atri Rudra (2010). "Pruebas grupales no adaptativas eficientemente decodificables". 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 pruebas de grupo combinatorios explícitos no adaptativos". Actas del 35º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP) : 748–759. arXiv : 0712.3876 . Código Bib : 2007arXiv0712.3876P.

Otras lecturas

• Libro de Atri Rudra sobre códigos de corrección de errores: combinatoria, algoritmos y aplicaciones (primavera de 201), 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 r-Cover". Revista de teoría combinatoria . Serie A. 73 (1): 172–173. doi : 10.1006/jcta.1996.0012 .