Prueba grupal

Un procedimiento que divide la tarea de identificar ciertos objetos en pruebas sobre grupos de elementos.

Una ilustración del problema de las bombillas, donde se busca una bombilla rota entre seis bombillas. Aquí, los tres primeros están conectados a una fuente de alimentación y se iluminan (A). Esto indica que la bombilla rota debe ser una de las últimas tres (B). Si, en cambio, las bombillas no se encienden, se puede estar seguro de que la bombilla rota estaba entre las tres primeras. Continuar con este procedimiento puede localizar la bombilla rota en no más de tres pruebas, en comparación con un máximo de seis pruebas si las bombillas se comprueban individualmente.

En estadística y matemáticas combinatorias , la prueba de grupo es cualquier procedimiento que divide la tarea de identificar ciertos objetos en pruebas de grupos de elementos, en lugar de pruebas individuales. Estudiado por primera vez por Robert Dorfman en 1943, las pruebas grupales son un campo relativamente nuevo de matemáticas aplicadas que se puede aplicar a una amplia gama de aplicaciones prácticas y es un área activa de investigación en la actualidad.

Un ejemplo familiar de prueba grupal involucra una serie de bombillas conectadas en serie, donde se sabe que exactamente una de las bombillas está rota. El objetivo es encontrar la bombilla rota utilizando el menor número de pruebas (donde una prueba es cuando algunas de las bombillas están conectadas a una fuente de alimentación). Un enfoque simple es probar cada bombilla individualmente. Sin embargo, cuando hay una gran cantidad de bombillas, sería mucho más eficiente agrupar las bombillas. Por ejemplo, al conectar la primera mitad de las bombillas a la vez, se puede determinar en qué mitad de la bombilla rota se encuentra, descartando la mitad de las bombillas en una sola prueba.

Los esquemas para realizar pruebas grupales pueden ser simples o complejos y las pruebas involucradas en cada etapa pueden ser diferentes. Los esquemas en los que las pruebas para la siguiente etapa dependen de los resultados de las etapas anteriores se denominan procedimientos adaptativos , mientras que los esquemas diseñados para que todas las pruebas se conozcan de antemano se denominan procedimientos no adaptativos . La estructura del esquema de las pruebas involucradas en un procedimiento no adaptativo se conoce como diseño de agrupación .

Las pruebas grupales tienen muchas aplicaciones, incluidas estadísticas, biología, informática, medicina, ingeniería y ciberseguridad. El interés moderno en estos esquemas de prueba ha sido reavivado por el Proyecto Genoma Humano . ^[1]

Términos y descripción básicos

A diferencia de muchas áreas de las matemáticas, los orígenes de las pruebas grupales se remontan a un solo informe ^[2] escrito por una sola persona: Robert Dorfman . ^[3] La motivación surgió durante la Segunda Guerra Mundial cuando el Servicio de Salud Pública de los Estados Unidos y el Servicio Selectivo se embarcaron en un proyecto a gran escala para eliminar a todos los hombres sifilíticos llamados a la inducción. La prueba de sífilis en un individuo implica extraerle una muestra de sangre y luego analizar la muestra para determinar la presencia o ausencia de sífilis. En ese momento, realizar esta prueba era costoso y probar a cada soldado individualmente habría sido muy costoso e ineficiente. ^[3]

Suponiendo que haya soldados, este método de prueba conduce a${\displaystyle n}$${\displaystyle n}$pruebas separadas. Si una gran proporción de personas está infectada, este método sería razonable. Sin embargo, en el caso más probable de que solo una proporción muy pequeña de los hombres esté infectada, se puede lograr un esquema de pruebas mucho más eficiente. La viabilidad de un esquema de pruebas más eficaz depende de la siguiente propiedad: los soldados pueden agruparse en grupos y, en cada grupo, las muestras de sangre pueden combinarse. Luego, la muestra combinada puede analizarse para verificar si al menos un soldado del grupo tiene sífilis. Esta es la idea central detrás de las pruebas grupales. Si uno o más de los soldados de este grupo tiene sífilis, entonces una prueba se desperdicia (es necesario realizar más pruebas para determinar qué soldado (s) era). Por otro lado, si nadie en la piscina tiene sífilis, se guardan muchas pruebas,ya que todos los soldados de ese grupo pueden ser eliminados con una sola prueba.^[3]

Los elementos que hacen que un grupo dé positivo en la prueba se denominan generalmente elementos defectuosos (estos son las bombillas rotas, los hombres sifilíticos, etc.). A menudo, el número total de artículos se indica como y representa el número de defectuosos si se supone que es conocido. ^[3]${\displaystyle n}$${\displaystyle d}$

Clasificación de problemas de pruebas grupales

Hay dos clasificaciones independientes para problemas de pruebas grupales; cada problema de prueba de grupo es adaptativo o no adaptativo, y probabilístico o combinatorio. ^[3]

En los modelos probabilísticos, se supone que los artículos defectuosos siguen alguna distribución de probabilidad y el objetivo es minimizar el número esperado de pruebas necesarias para identificar el defecto de cada artículo. Por otro lado, con las pruebas grupales combinatorias, el objetivo es minimizar la cantidad de pruebas necesarias en el 'peor de los casos', es decir, crear un algoritmo minmax , y no se asume ningún conocimiento de la distribución de los defectuosos. ^[3]

La otra clasificación, la adaptabilidad, se refiere a qué información se puede usar al elegir qué elementos agrupar en una prueba. En general, la elección de qué elementos probar puede depender de los resultados de pruebas anteriores, como en el problema de la bombilla anterior. Un algoritmoque procede realizando una prueba, y luego usando el resultado (y todos los resultados anteriores) para decidir qué prueba siguiente realizar, se llama adaptativa. Por el contrario, en los algoritmos no adaptativos, todas las pruebas se deciden de antemano. Esta idea se puede generalizar a algoritmos de etapas múltiples, donde las pruebas se dividen en etapas, y cada prueba en la siguiente etapa debe decidirse de antemano, con solo el conocimiento de los resultados de las pruebas en etapas anteriores. Aunque los algoritmos adaptativos ofrecen mucha más libertad en el diseño, se sabe que los algoritmos adaptativos de pruebas grupales no mejoran los no adaptativos en más de un factor constante en el número de pruebas necesarias para identificar el conjunto de elementos defectuosos. ^{[4] [3]} Además de esto, los métodos no adaptativos suelen ser útiles en la práctica porque se pueden realizar pruebas sucesivas sin analizar primero los resultados de todas las pruebas anteriores, lo que permite la distribución eficaz del proceso de prueba.

Variaciones y extensiones

Hay muchas formas de ampliar el problema de las pruebas grupales. Uno de los más importantes se llama prueba de grupo ruidoso y se ocupa de una gran suposición del problema original: que la prueba está libre de errores. Un problema de prueba grupal se denomina ruidoso cuando existe la posibilidad de que el resultado de una prueba grupal sea erróneo (por ejemplo, sale positivo cuando la prueba no contiene defectos). El modelo de ruido de Bernoulli asume que esta probabilidad es constante, pero en general puede depender del número real de defectos en la prueba y del número de elementos probados. ^[5]${\displaystyle q}$Por ejemplo, el efecto de la dilución se puede modelar diciendo que un resultado positivo es más probable cuando hay más defectuosos (o más defectuosos como una fracción del número analizado), presentes en la prueba. ^[6] Un algoritmo ruidoso siempre tendrá una probabilidad distinta de cero de cometer un error (es decir, etiquetar incorrectamente un elemento).

Las pruebas grupales se pueden ampliar considerando escenarios en los que hay más de dos posibles resultados de una prueba. Por ejemplo, una prueba puede tener los resultados y , lo que corresponde a que no haya defectos, un solo defecto o un número desconocido de defectuosos mayor que uno. De manera más general, es posible considerar que el conjunto de resultados de una prueba es para algunos . ^[3]${\displaystyle 0,1}$${\displaystyle 2^{+}}$${\displaystyle {0,1,\ldots ,k^{+}}}$${\displaystyle k\in \mathbb {N} }$

Otra extensión es considerar las restricciones geométricas sobre qué conjuntos se pueden probar. El problema anterior de las bombillas es un ejemplo de este tipo de restricción: solo se pueden probar las bombillas que aparecen consecutivamente. Del mismo modo, los elementos se pueden organizar en un círculo o, en general, en una red, donde las pruebas son rutas disponibles en el gráfico. Otro tipo de restricción geométrica sería el número máximo de elementos que se pueden probar en un grupo, ^[a] o el tamaño del grupo podría tener que ser uniforme y así sucesivamente. De manera similar, puede ser útil considerar la restricción de que un elemento determinado solo puede aparecer en un cierto número de pruebas. ^[3]

Hay infinitas formas de seguir mezclando la fórmula básica de las pruebas grupales. Las siguientes elaboraciones darán una idea de algunas de las variantes más exóticas. En el modelo 'bueno-mediocre-malo', cada ítem es uno de 'bueno', 'mediocre' o 'malo', y el resultado de una prueba es el tipo de ítem 'peor' en el grupo. En las pruebas de grupo umbral, el resultado de una prueba es positivo si el número de artículos defectuosos en el grupo es mayor que algún valor umbral o proporción. ^[7] Las pruebas grupales con inhibidores son una variante con aplicaciones en biología molecular. Aquí, hay una tercera clase de elementos llamados inhibidores, y el resultado de una prueba es positivo si contiene al menos un inhibidor defectuoso y no contiene ningún inhibidor. ^[8]

Historia y desarrollo

Invención y progreso inicial

El concepto de prueba grupal fue introducido por primera vez por Robert Dorfman en 1943 en un breve informe ^[2] publicado en la sección Notas de Annals of Mathematical Statistics . ^{[3] [b]} El informe de Dorfman, como con todo el trabajo inicial sobre pruebas grupales, se centró en el problema probabilístico y tenía como objetivo utilizar la idea novedosa de las pruebas grupales para reducir el número esperado de pruebas necesarias para eliminar a todos los hombres sifilíticos en un grupo de soldados determinado. El método era simple: colocaba a los soldados en grupos de un tamaño determinado y usa pruebas individuales (prueba de elementos en grupos de tamaño uno) en los grupos positivos para encontrar cuáles estaban infectados. Dorfman tabuló los tamaños de grupo óptimos para esta estrategia frente a la tasa de prevalencia de defectos en la población. ^[2]

Después de 1943, las pruebas grupales permanecieron prácticamente intactas durante varios años. Luego, en 1957, Sterrett produjo una mejora en el procedimiento de Dorfman. ^[10] Este proceso más nuevo comienza realizando nuevamente pruebas individuales en los grupos positivos, pero se detiene tan pronto como se identifica un defecto. Luego, el resto de elementos del grupo se prueban juntos, ya que es muy probable que ninguno de ellos sea defectuoso.

Sobel y Groll dieron el primer tratamiento completo de las pruebas grupales en su artículo formativo de 1959 sobre el tema. ^[11] Describieron cinco procedimientos nuevos, además de generalizaciones para cuando se desconoce la tasa de prevalencia, y para el óptimo, proporcionaron una fórmula explícita para el número esperado de pruebas que utilizaría. El documento también hizo la conexión entre las pruebas grupales y la teoría de la información por primera vez, además de discutir varias generalizaciones del problema de las pruebas grupales y proporcionar algunas aplicaciones nuevas de la teoría.

Pruebas grupales combinatorias

Las pruebas grupales fueron estudiadas por primera vez en el contexto combinatorio por Li en 1962, ^[12] con la introducción del algoritmo de etapa de Li${\displaystyle s}$ . ^[3] Li propuso una extensión del "algoritmo de 2 etapas" de Dorfman a un número arbitrario de etapas que no requerían más que pruebas para garantizar la detección o menos defectos entre los elementos. La idea era eliminar todos los elementos de las pruebas negativas y dividir los elementos restantes en grupos como se hizo con el grupo inicial. Esto debía hacerse varias veces antes de realizar pruebas individuales.${\displaystyle t={\frac {e}{\log _{2}(e)}}d\log _{2}(n)}$${\displaystyle d}$${\displaystyle n}$${\displaystyle s-1}$

Las pruebas de grupo combinatorias en general fueron estudiadas más a fondo por Katona en 1973. ^[13] Katona introdujo la representación matricial de las pruebas de grupo no adaptativas y produjo un procedimiento para encontrar lo defectuoso en el caso 1-defectuoso no adaptativo en nada más. que las pruebas, que también demostró ser óptima.${\displaystyle t=\lceil \log _{2}(n)\rceil }$

En general, es difícil encontrar algoritmos óptimos para las pruebas grupales combinatorias adaptativas y, aunque no se ha determinado la complejidad computacional de las pruebas grupales, se sospecha que es difícil en alguna clase de complejidad. ^[3] Sin embargo, en 1972 se produjo un avance importante con la introducción del algoritmo generalizado de división binaria . ^[14] El algoritmo de división binaria generalizada funciona realizando una búsqueda binaria en los grupos que dan positivo, y es un algoritmo simple que encuentra un solo defectuoso en no más que el número de pruebas de límite inferior de información .

En escenarios donde hay dos o más defectuosos, el algoritmo de división binaria generalizada todavía produce resultados casi óptimos, requiriendo como máximo pruebas por encima del límite inferior de información donde está el número de defectuosos. ^[14] Allemann realizó mejoras considerables a esto en 2013, logrando que el número requerido de pruebas por debajo del límite inferior de la información cuando y . ^[15]${\displaystyle d-1}$${\displaystyle d}$${\displaystyle 0.187d+0.5\log _{2}(d)+5.5}$${\displaystyle n/d\geq 38}$${\displaystyle d\geq 10}$Esto se logró cambiando la búsqueda binaria en el algoritmo de división binaria a un conjunto complejo de subalgoritmos con grupos de prueba superpuestos. Como tal, el problema de las pruebas grupales combinatorias adaptativas, con un número conocido o límite superior en el número de defectuosos, se ha resuelto esencialmente, con poco margen de mejora.

Hay una pregunta abierta en cuanto a cuándo la prueba individual es minmax . Hu, Hwang y Wang demostraron en 1981 que la prueba individual es minmax cuando y que no es minmax cuando . ^[16] Actualmente se conjetura que este límite es agudo: es decir, la prueba individual es minmax si y solo si . ^{[17] [c]} Ricccio y Colbourn lograron algunos avances en 2000, quienes demostraron que para pruebas grandes , individuales es minmax cuando . ^[18]${\displaystyle n\leq \lfloor (5d+1)/2\rfloor }$${\displaystyle n>3d}$${\displaystyle n\leq 3d}$${\displaystyle n}$${\displaystyle d\geq n/\log _{3/2}(3)\approx 0.369n}$

Pruebas probabilísticas y no adaptativas

Una de las ideas clave en las pruebas grupales no adaptativas es que se pueden obtener ganancias significativas eliminando el requisito de que el procedimiento de prueba grupal tenga certeza de que tendrá éxito (el problema "combinatorio"), pero que permita que tenga algunos resultados bajos pero no -cero probabilidad de etiquetar incorrectamente cada elemento (el problema "probabilístico"). Se sabe que a medida que el número de artículos defectuosos se acerca al número total de artículos, las soluciones combinatorias exactas requieren significativamente más pruebas que las soluciones probabilísticas, incluso las soluciones probabilísticas que solo permiten una probabilidad de error asintóticamente pequeña . ^{[4] [d]}

En este sentido, Chan et al. (2011) introdujeron COMP , un algoritmo probabilístico que no requiere más que pruebas para encontrar hasta defectuosos en artículos con una probabilidad de error no mayor a . ^[5] Esto está dentro de un factor constante del límite inferior. ^[4]${\displaystyle t=ed(1+\delta )\ln(n)}$${\displaystyle d}$${\displaystyle n}$${\displaystyle n^{-\delta }}$${\displaystyle t=O(d\log _{2}n)}$

Chan y col. (2011) también proporcionó una generalización de COMP a un modelo ruidoso simple, y de manera similar produjo un límite de desempeño explícito, que nuevamente era solo una constante (dependiente de la probabilidad de una prueba fallida) por encima del límite inferior correspondiente. ^{[4] [5]} En general, el número de pruebas requeridas en el caso del ruido de Bernoulli es un factor constante mayor que en el caso sin ruido. ^[5]

Aldridge, Baldassini y Johnson (2014) produjeron una extensión del algoritmo COMP que agregó pasos adicionales de posprocesamiento. ^[19] Demostraron que el rendimiento de este nuevo algoritmo, llamado DD , excede estrictamente al de COMP, y que DD es "esencialmente óptimo" en escenarios donde , al compararlo con un algoritmo hipotético que define un óptimo razonable. El rendimiento de este algoritmo hipotético sugiere que hay margen de mejora en el momento , además de sugerir cuánta mejora podría ser. ^[19]${\displaystyle d^{2}\geq n}$${\displaystyle d^{2}<n}$

Formalización de pruebas grupales combinatorias

Esta sección define formalmente las nociones y términos relacionados con las pruebas grupales.

• El vector de entrada , , se define para ser un vector binario de longitud (es decir, ), con el j -ésimo siendo llamado defectuoso si y sólo si . Además, cualquier artículo no defectuoso se denomina artículo "bueno".${\displaystyle \mathbf {x} =(x_{1},x_{2},\dots ,x_{n})}$${\displaystyle n}$${\displaystyle \mathbf {x} \in \{0,1\}^{n}}$${\displaystyle x_{j}=1}$

${\displaystyle \mathbf {x} }$pretende describir el conjunto (desconocido) de elementos defectuosos. La propiedad clave de es que es una entrada implícita . Es decir, no existe un conocimiento directo de lo que son las entradas de , aparte del que se puede inferir mediante alguna serie de "pruebas". Esto conduce a la siguiente definición.${\displaystyle \mathbf {x} }$${\displaystyle \mathbf {x} }$

• Sea un vector de entrada. Un conjunto se llama prueba . Cuando la prueba es silenciosa , el resultado de una prueba es positivo cuando existe tal que , y el resultado es negativo en caso contrario.${\displaystyle \mathbf {x} }$${\displaystyle S\subseteq \{1,2,\dots ,n\}}$${\displaystyle j\in S}$${\displaystyle x_{j}=1}$

Por lo tanto, el objetivo de las pruebas grupales es idear un método para elegir una serie 'corta' de pruebas que permitan ser determinadas, ya sea con exactitud o con un alto grado de certeza.${\displaystyle \mathbf {x} }$

• Se dice que un algoritmo de prueba grupal comete un error si etiqueta incorrectamente un artículo (es decir, etiqueta cualquier artículo defectuoso como no defectuoso o viceversa). Esto no es lo mismo que el resultado de una prueba grupal sea incorrecto. Un algoritmo se denomina error cero si la probabilidad de que cometa un error es cero. ^[mi]
• ${\displaystyle t(d,n)}$denota el número mínimo de pruebas necesarias para encontrar siempre defectuosos entre los elementos con cero probabilidad de error mediante cualquier algoritmo de prueba de grupo. Para la misma cantidad pero con la restricción de que el algoritmo no es adaptativo, se usa la notación .${\displaystyle d}$${\displaystyle n}$${\displaystyle {\bar {t}}(d,n)}$

Límites generales

Dado que siempre es posible recurrir a pruebas individuales estableciendo para cada uno , debe ser eso . También, ya que cualquier procedimiento de prueba no adaptativa se puede escribir como un algoritmo adaptativo simplemente realizando todas las pruebas sin tener en cuenta su resultado, . Finalmente, cuando , hay al menos un artículo cuya defectuosidad debe ser determinada (por al menos una prueba), y así .${\displaystyle S_{j}=\{j\}}$${\displaystyle 1\leq j\leq n}$${\displaystyle {\bar {t}}(d,n)\leq n}$${\displaystyle t(d,n)\leq {\bar {t}}(d,n)}$${\displaystyle 0\neq d\neq n}$${\displaystyle 1\leq t(d,n)}$

En resumen (al asumir ), . ^[F]${\displaystyle 0\neq d\neq n}$${\displaystyle 1\leq t(d,n)\leq {\bar {t}}(d,n)\leq n}$

Información límite inferior

Un límite inferior en el número de pruebas necesarias se puede describir utilizando la noción de espacio muestral , denotado , que es simplemente el conjunto de posibles ubicaciones de los defectuosos. Para cualquier problema de prueba de grupo con espacio muestral y cualquier algoritmo de prueba de grupo, se puede demostrar que , donde es el número mínimo de pruebas requeridas para identificar todos los defectuosos con una probabilidad de error cero. Esto se denomina límite inferior de información . ^[3] Este límite se deriva del hecho de que después de cada prueba, se divide en dos subconjuntos separados, cada uno correspondiente a uno de los dos posibles resultados de la prueba.${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle t\geq \lceil \log _{2}{|{\mathcal {S}}|}\rceil }$${\displaystyle t}$${\displaystyle {\mathcal {S}}}$

Sin embargo, el límite inferior de la información en sí mismo suele ser inalcanzable, incluso para problemas pequeños. ^[3] Esto se debe a que la división de no es arbitraria, ya que debe ser realizable mediante alguna prueba.${\displaystyle {\mathcal {S}}}$

De hecho, el límite inferior de la información se puede generalizar al caso en el que existe una probabilidad distinta de cero de que el algoritmo cometa un error. De esta forma, el teorema nos da un límite superior en la probabilidad de éxito basado en el número de pruebas. Para cualquier algoritmo de pruebas grupales que realice pruebas, la probabilidad de éxito`` satisface . Esto puede ser reforzada para: . ^{[5] [20]}${\displaystyle t}$${\displaystyle \mathbb {P} ({\textrm {success}})}$${\displaystyle \mathbb {P} ({\textrm {success}})\leq t/\log _{2}{n \choose d}}$${\displaystyle \mathbb {P} ({\textrm {success}})\leq {\frac {2^{t}}{n \choose d}}}$

Representación de algoritmos no adaptativos

Una configuración típica de prueba grupal. Un algoritmo no adaptativo primero elige la matriz y luego se le da el vector y . Entonces, el problema es encontrar una estimación de x .${\displaystyle M}$

Los algoritmos para pruebas grupales no adaptativas constan de dos fases distintas. Primero, se decide cuántas pruebas realizar y qué elementos incluir en cada prueba. En la segunda fase, a menudo denominada paso de decodificación, se analizan los resultados de cada prueba de grupo para determinar qué elementos probablemente sean defectuosos. La primera fase generalmente se codifica en una matriz de la siguiente manera. ^[5]

• Suponga que un procedimiento de prueba grupal no adaptativo para elementos consiste en las pruebas para algunos . La matriz de prueba para este esquema es la matriz binaria , donde si y solo si (y es cero en caso contrario).${\displaystyle n}$${\displaystyle S_{1},S_{2},\dots ,S_{t}}$${\displaystyle t\in \mathbb {N} _{\geq 0}}$${\displaystyle t\times n}$${\displaystyle M}$${\displaystyle (M)_{ij}=1}$${\displaystyle j\in S_{i}}$

Por lo tanto, cada columna de representa un elemento y cada fila representa una prueba, con una en la entrada que indica que la prueba incluyó el elemento y una que indica lo contrario.${\displaystyle M}$${\displaystyle 1}$${\displaystyle (i,j){\textrm {-th}}}$${\displaystyle i{\textrm {-th}}}$${\displaystyle j{\textrm {-th}}}$${\displaystyle 0}$

Además del vector (de longitud ) que describe el conjunto defectuoso desconocido, es común introducir el vector de resultado, que describe los resultados de cada prueba.${\displaystyle \mathbf {x} }$${\displaystyle n}$

• Sea el número de pruebas realizadas por un algoritmo no adaptativo. El vector resultado , es un vector binario de longitud (es decir, ) tal que si y sólo si el resultado de la prueba fue positiva (es decir, contenían al menos un defectuoso). ^[gramo]${\displaystyle t}$${\displaystyle \mathbf {y} =(y_{1},y_{2},\dots ,y_{t})}$${\displaystyle t}$${\displaystyle \mathbf {y} \in \{0,1\}^{t}}$${\displaystyle y_{i}=1}$${\displaystyle i{\textrm {-th}}}$

Con estas definiciones, el problema no adaptativo se puede reformular de la siguiente manera: primero se elige una matriz de prueba , después de lo cual se devuelve el vector . Entonces el problema es analizar para encontrar una estimación .${\displaystyle M}$${\displaystyle \mathbf {y} }$${\displaystyle \mathbf {y} }$${\displaystyle \mathbf {x} }$

En el caso más simple y ruidoso, donde hay una probabilidad constante , de que una prueba de grupo tenga un resultado erróneo, se considera un vector binario aleatorio , donde cada entrada tiene una probabilidad de ser , y es lo contrario. El vector que se devuelve es entonces , con la adición habitual (de forma equivalente, esta es la operación XOR por elementos ). Un algoritmo ruidoso debe estimar el uso (es decir, sin conocimiento directo de ). ^[5]${\displaystyle q}$${\displaystyle \mathbf {v} }$${\displaystyle q}$${\displaystyle 1}$${\displaystyle 0}$${\displaystyle {\hat {\mathbf {y} }}=\mathbf {y} +\mathbf {v} }$${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$${\displaystyle \mathbf {x} }$${\displaystyle {\hat {\mathbf {y} }}}$${\displaystyle \mathbf {y} }$

Límites para algoritmos no adaptativos

La representación matricial permite probar algunos límites en las pruebas grupales no adaptativas. El enfoque refleja el de muchos diseños deterministas, donde se consideran matrices separables, como se define a continuación. ^[3]${\displaystyle d}$

• Una matriz binaria ,, se llama separable si cada suma booleana (OR lógico) de cualquiera de sus columnas es distinta. Además, la notación -separable indica que cada suma de cualquiera de hasta de columnas 's es distinta. (Esto no es lo mismo que ser separables para todos ).${\displaystyle M}$${\displaystyle d}$${\displaystyle d}$${\displaystyle {\bar {d}}}$ ${\displaystyle d}$${\displaystyle M}$${\displaystyle M}$${\displaystyle k}$${\displaystyle k\leq d}$

Cuando es una matriz de prueba, la propiedad de ser -separable ( -separable) es equivalente a poder distinguir entre (hasta) defectuosos. Sin embargo, no garantiza que esto sea sencillo. Lo hace una propiedad más fuerte, llamada -disjunctness .${\displaystyle M}$${\displaystyle d}$${\displaystyle {\bar {d}}}$${\displaystyle d}$${\displaystyle d}$

• Una matriz binaria, se llama -disjunct si la suma booleana de cualquier columna no contiene ninguna otra columna. (En este contexto, se dice que una columna A contiene una columna B si por cada índice donde B tiene un 1, A también tiene un 1.)${\displaystyle M}$${\displaystyle d}$${\displaystyle d}$

Una propiedad útil de las matrices de prueba -disjuntas es que, hasta con defectuosos, todos los elementos no defectuosos aparecerán en al menos una prueba cuyo resultado sea negativo. Esto significa que hay un procedimiento simple para encontrar los defectuosos: simplemente retire todos los elementos que aparezcan en una prueba negativa.${\displaystyle d}$${\displaystyle d}$

Usando las propiedades de matrices separables y disyuntivas, se puede mostrar lo siguiente para el problema de identificar defectuosos entre el total de artículos. ^[4]${\displaystyle d}$${\displaystyle d}$${\displaystyle d}$${\displaystyle n}$

1. El número de pruebas necesarias para una probabilidad media de error asintóticamente pequeña escala como .${\displaystyle O(d\log _{2}n)}$
2. El número de pruebas necesarias para una probabilidad máxima de error asintóticamente pequeña escala como .${\displaystyle O(d^{2}\log _{2}n)}$
3. El número de pruebas necesarias para una probabilidad cero de error se escala como .${\displaystyle O\left({\frac {d^{2}\log _{2}n}{\log _{2}d}}\right)}$

Algoritmo de división binaria generalizado

Una ilustración del algoritmo de división binaria generalizado donde hay 8 defectuosos y 135 artículos en total. Aquí, y la primera prueba da un resultado negativo, por lo que todos los artículos se declaran no defectuosos. Por lo tanto, quedan 119 elementos . Este segundo grupo da un resultado positivo, por lo que se utiliza una búsqueda binaria para encontrar un defecto. Una vez hecho esto, se repite todo el proceso, calculando un nuevo utilizando solo aquellos artículos cuya defectuosidad no se ha determinado.${\displaystyle 2^{\alpha _{1}}=16}$${\displaystyle 2^{\alpha _{2}}=8}$${\displaystyle \alpha }$

El algoritmo de división binaria generalizada es un algoritmo de prueba de grupo adaptativo esencialmente óptimo que encuentra o menos defectos entre los elementos de la siguiente manera: ^{[3] [14]}${\displaystyle d}$${\displaystyle n}$

1. Si , pruebe los elementos individualmente. De lo contrario, configure y .${\displaystyle n\leq 2d-2}$${\displaystyle n}$${\displaystyle l=n-d+1}$${\displaystyle \alpha =\lfloor \log _{2}{l/d}\rfloor }$
2. Pruebe un grupo de tamaño . Si el resultado es negativo, todos los artículos del grupo se declaran no defectuosos; configure y vaya al paso 1. De lo contrario, utilice una búsqueda binaria para identificar un número defectuoso y un número no especificado, llamado , de artículos no defectuosos; establecer y . Vaya al paso 1.${\displaystyle 2^{\alpha }}$${\displaystyle n:=n-2^{\alpha }}$${\displaystyle x}$${\displaystyle n:=n-1-x}$${\displaystyle d:=d-1}$

El algoritmo de división binaria generalizado no requiere más que pruebas donde . ^[3]${\displaystyle T}$${\displaystyle T={\begin{cases}n&n\leq 2d-2\\(\alpha +2)d+p-1&n\geq 2d-1\end{cases}}}$

Para grandes, se puede demostrar que , ^[3] que se compara favorablemente con las pruebas requeridas para el algoritmo de etapa de Li . De hecho, el algoritmo de división binaria generalizado está cerca del óptimo en el siguiente sentido. Cuando se puede demostrar eso , ¿dónde está el límite inferior de la información? ^{[3] [14]}${\displaystyle n/d}$${\displaystyle T\rightarrow d\log _{2}(n/d)}$${\displaystyle t={\frac {e}{\log _{2}e}}d\log _{2}\left({\frac {n}{d}}\right)}$${\displaystyle s}$${\displaystyle d\geq 2}$${\displaystyle T-B_{I}(d,n)\leq (d-1)}$${\displaystyle B_{I}(d,n)=\left\lceil \log _{2}\sum _{i=0}^{d}{n \choose i}\right\rceil }$

Algoritmos no adaptativos

Los algoritmos de prueba de grupo no adaptativos tienden a asumir que se conoce el número de defectuosos, o al menos un buen límite superior para ellos. ^[5] Esta cantidad se indica en esta sección. Si no se conocen límites, existen algoritmos no adaptables con baja complejidad de consulta que pueden ayudar a estimar . ^[21]${\displaystyle d}$${\displaystyle d}$

Búsqueda combinatoria de emparejamiento ortogonal (COMP)

Una ilustración del algoritmo COMP. COMP identifica el artículo a como defectuoso y el artículo b como no defectuoso. Sin embargo, etiqueta incorrectamente c como defectuoso, ya que está "oculto" por elementos defectuosos en todas las pruebas en las que aparece.

La búsqueda combinatoria ortogonal de emparejamiento, o COMP, es un algoritmo simple de prueba de grupo no adaptativo que forma la base de los algoritmos más complicados que siguen en esta sección.

Primero, cada entrada de la matriz de prueba se elige iid para que sea con probabilidad y de otra manera.${\displaystyle 1}$${\displaystyle 1/d}$${\displaystyle 0}$

El paso de decodificación prosigue en columnas (es decir, por artículo). Si cada prueba en la que aparece un artículo es positiva, entonces el artículo se declara defectuoso; de lo contrario, se supone que el artículo no está defectuoso. O de manera equivalente, si un artículo aparece en cualquier prueba cuyo resultado es negativo, el artículo se declara no defectuoso; de lo contrario, se supone que el artículo está defectuoso. Una propiedad importante de este algoritmo es que nunca crea falsos negativos , aunque se produce un falso positivo cuando todas las ubicaciones con unos en la j -ésima columna de (correspondiente a un elemento j no defectuoso ) están "ocultas" por las de otros columnas correspondientes a artículos defectuosos.${\displaystyle M}$

El algoritmo COMP no requiere más que pruebas para tener una probabilidad de error menor o igual a . ^[5] Esto está dentro de un factor constante del límite inferior de la probabilidad media de error anterior.${\displaystyle ed(1+\delta )\ln(n)}$${\displaystyle n^{-\delta }}$

En el caso ruidoso, se relaja el requisito en el algoritmo COMP original de que el conjunto de ubicaciones de unos en cualquier columna correspondiente a un elemento positivo esté completamente contenido en el conjunto de ubicaciones de unos en el vector de resultado. En su lugar, uno permite que durante un cierto número de “desajustes” - este número de desajustes depende tanto del número de unos en cada columna, y también el parámetro de ruido, . Este ruidoso algoritmo COMP no requiere más que pruebas para lograr una probabilidad de error como máximo . ^[5]${\displaystyle M}$${\displaystyle q}$${\displaystyle 4.36({\sqrt {\delta }}+{\sqrt {1+\delta }})^{2}(1-2q)^{-2}d\log _{2}{n}}$${\displaystyle n^{-\delta }}$

Definitivamente defectuosos (DD)

El método de defectos definidos (DD) es una extensión del algoritmo COMP que intenta eliminar los falsos positivos. Se ha demostrado que las garantías de rendimiento de DD superan estrictamente las de COMP. ^[19]

El paso de decodificación utiliza una propiedad útil del algoritmo COMP: que cada elemento que COMP declara no defectuoso es ciertamente no defectuoso (es decir, no hay falsos negativos). Procede de la siguiente manera.

1. Primero se ejecuta el algoritmo COMP y se eliminan los no defectuosos que detecta. Todos los elementos restantes están ahora "posiblemente defectuosos".
2. A continuación, el algoritmo analiza todas las pruebas positivas. Si un artículo aparece como el único "posible defectuoso" en una prueba, entonces debe estar defectuoso, por lo que el algoritmo lo declara defectuoso.
3. Se supone que todos los demás elementos no tienen defectos. La justificación de este último paso proviene del supuesto de que el número de artículos defectuosos es mucho menor que el número total de artículos.

Tenga en cuenta que los pasos 1 y 2 nunca cometen un error, por lo que el algoritmo solo puede cometer un error si declara que un artículo defectuoso no es defectuoso. Por lo tanto, el algoritmo DD solo puede crear falsos negativos.

COMP secuencial (SCOMP)

SCOMP (Sequential COMP) es un algoritmo que hace uso del hecho de que DD no comete errores hasta el último paso, donde se asume que los elementos restantes no están defectuosos. Sea el conjunto de defectuosos declarados . Una prueba positiva se llama explicada por si contiene al menos un elemento en . La observación clave con SCOMP es que el conjunto de defectos encontrados por DD puede no explicar todas las pruebas positivas y que todas las pruebas inexplicables deben contener un defecto oculto.${\displaystyle K}$${\displaystyle K}$${\displaystyle K}$

El algoritmo procede como sigue.

1. Realice los pasos 1 y 2 del algoritmo DD para obtener una estimación inicial para el conjunto de defectuosos.${\displaystyle K}$
2. Si explica cada prueba positiva, termine el algoritmo: es la estimación final para el conjunto de defectuosos.${\displaystyle K}$${\displaystyle K}$
3. Si hay pruebas inexplicables, busque el "posible defectuoso" que aparezca en el mayor número de pruebas inexplicables y declare que es defectuoso (es decir, agréguelo al conjunto ). Vaya al paso 2.${\displaystyle K}$

En simulaciones, se ha demostrado que SCOMP funciona casi de manera óptima. ^[19]

Aplicaciones de ejemplo

La generalidad de la teoría de las pruebas grupales la presta a muchas aplicaciones diversas, incluida la detección de clones, la localización de cortocircuitos eléctricos; ^[3] redes informáticas de alta velocidad; ^[22] examen médico, búsqueda de cantidades, estadísticas; ^[16] aprendizaje automático, secuenciación de ADN; ^[23] criptografía; ^{[24] [25]} y análisis forense de datos. ^[26] Esta sección ofrece una breve descripción de una pequeña selección de estas aplicaciones.

Canales de acceso múltiple

Una ilustración de un canal de accesos múltiples que muestra un mensaje exitoso y una colisión de mensajes.

Un canal de accesos múltiples es un canal de comunicación que conecta a muchos usuarios a la vez. Cada usuario puede escuchar y transmitir en el canal, pero si más de un usuario transmite al mismo tiempo, las señales chocan y se reducen a un ruido ininteligible. Los canales de accesos múltiples son importantes para diversas aplicaciones del mundo real, en particular, las redes informáticas inalámbricas y las redes telefónicas. ^[27]

Un problema destacado de los canales de accesos múltiples es cómo asignar tiempos de transmisión a los usuarios para que sus mensajes no colisionen. Un método simple es dar a cada usuario su propio intervalo de tiempo en el que transmitir, lo que requiere intervalos. (Esto se llama multiplexación por división de tiempo , o TDM). Sin embargo, esto es muy ineficiente, ya que asignará ranuras de transmisión a los usuarios que pueden no tener un mensaje, y generalmente se supone que solo unos pocos usuarios querrán transmitir en cualquier momento. determinado tiempo; de lo contrario, un canal de acceso múltiple no es práctico en primer lugar.${\displaystyle n}$

En el contexto de las pruebas grupales, este problema generalmente se aborda dividiendo el tiempo en 'épocas' de la siguiente manera. ^[3] Un usuario se llama "activo" si tiene un mensaje al comienzo de una época. (Si se genera un mensaje durante una época, el usuario solo se activa al comienzo de la siguiente). Una época termina cuando cada usuario activo ha transmitido con éxito su mensaje. El problema es entonces encontrar a todos los usuarios activos en una época determinada y programar un tiempo para que transmitan (si aún no lo han hecho con éxito). Aquí, una prueba en un conjunto de usuarios corresponde a aquellos usuarios que intentan una transmisión. Los resultados de la prueba son el número de usuarios que intentaron transmitir y${\displaystyle 0,1,}$${\displaystyle 2^{+}}$, correspondientes respectivamente a ningún usuario activo, exactamente un usuario activo (mensaje exitoso) o más de un usuario activo (colisión de mensajes). Por lo tanto, utilizando un algoritmo de prueba de grupo adaptativo con resultados , se puede determinar qué usuarios desean transmitir en la época. Entonces, a cualquier usuario que aún no haya realizado una transmisión exitosa, ahora se le puede asignar una ranura para transmitir, sin desperdiciar tiempos de asignación a los usuarios inactivos.${\displaystyle \{0,1,2^{+}\}}$

Aprendizaje automático y detección comprimida

El aprendizaje automático es un campo de la informática que tiene muchas aplicaciones de software, como clasificación de ADN, detección de fraude y publicidad dirigida. Uno de los principales subcampos del aprendizaje automático es el problema de "aprendizaje mediante ejemplos", donde la tarea es aproximar alguna función desconocida cuando se le da su valor en varios puntos específicos. ^[3] Como se describe en esta sección, este problema de aprendizaje de funciones se puede abordar con un enfoque de prueba grupal.

En una versión simple del problema, hay alguna función desconocida, donde , y (usando aritmética lógica: la suma es lógica O y la multiplicación es lógica Y). Aquí es ' escasa', lo que significa que la mayoría de sus entradas son . El objetivo es construir una aproximación al uso de evaluaciones puntuales, donde sea ​​lo más pequeña posible. ^[4] (La recuperación exacta corresponde a algoritmos de error cero, mientras que se aproxima mediante algoritmos que tienen una probabilidad de error distinta de cero).${\displaystyle f:\{0,1\}^{N}\to \{0,1\}}$${\displaystyle f({\textbf {x}})={\textbf {a}}\cdot {\textbf {x}}}$${\displaystyle {\textbf {a}}\in \{0,1\}^{N}}$${\displaystyle {\textbf {a}}}$${\displaystyle d}$${\displaystyle d\ll N}$${\displaystyle 1}$${\displaystyle f}$${\displaystyle t}$${\displaystyle t}$${\displaystyle f}$${\displaystyle f}$

En este problema, recuperar es equivalente a encontrar . Además, si y solo si hay algún índice , dónde . Por tanto, este problema es análogo a un problema de prueba de grupo con artículos defectuosos y totales. Las entradas de son los elementos, que son defectuosos si lo son , especifica una prueba, y una prueba es positiva si y solo si . ^[4]${\displaystyle f}$${\displaystyle {\textbf {a}}}$${\displaystyle f({\textbf {p}})=1}$${\displaystyle n}$${\displaystyle {\textbf {a}}_{n}={\textbf {p}}_{n}=1}$${\displaystyle d}$${\displaystyle n}$${\displaystyle {\textbf {a}}}$${\displaystyle 1}$${\displaystyle {\textbf {p}}}$${\displaystyle f({\textbf {p}})=1}$

En realidad, a menudo uno estará interesado en funciones que son más complicadas, como , de nuevo dónde . La detección comprimida , que está estrechamente relacionada con las pruebas grupales, se puede utilizar para resolver este problema. ^[4]${\displaystyle f:\mathbb {C} ^{N}\to \mathbb {C} }$${\displaystyle f({\textbf {x}})={\textbf {a}}\cdot {\textbf {x}}}$

En la detección comprimida, el objetivo es reconstruir una señal, tomando una serie de medidas. Estas medidas se modelan tomando el producto escalar de con un vector elegido. ^[h] El objetivo es utilizar una pequeña cantidad de mediciones, aunque normalmente esto no es posible a menos que se asuma algo sobre la señal. Una de esas suposiciones (que es común ^{[30] [31]} ) es que solo una pequeña cantidad de entradas de son significativas , lo que significa que tienen una gran magnitud. Dado que las medidas son productos escalares de , la ecuación es válida, donde es una matriz que describe el conjunto de medidas que se han elegido y${\displaystyle {\textbf {v}}\in \mathbb {C} ^{N}}$${\displaystyle {\textbf {v}}}$${\displaystyle {\textbf {v}}}$${\displaystyle {\textbf {v}}}$${\displaystyle M{\textbf {v}}={\textbf {q}}}$${\displaystyle M}$${\displaystyle t\times N}$${\displaystyle \mathbf {q} }$es el conjunto de resultados de la medición. Esta construcción muestra que la detección comprimida es una especie de prueba de grupo "continua".

La principal dificultad en la detección comprimida es identificar qué entradas son significativas. ^[30] Una vez hecho esto, hay una variedad de métodos para estimar los valores reales de las entradas. ^[32] Esta tarea de identificación se puede abordar con una simple aplicación de pruebas grupales. Aquí, una prueba de grupo produce un número complejo: la suma de las entradas que se prueban. El resultado de una prueba se llama positivo si produce un número complejo con una gran magnitud, que, dado el supuesto de que las entradas significativas son escasas, indica que la prueba contiene al menos una entrada significativa.

Existen construcciones deterministas explícitas para este tipo de algoritmo de búsqueda combinatoria, que requieren mediciones. ^[33] Sin embargo, al igual que con las pruebas de grupo, estas son subóptimas y las construcciones aleatorias (como COMP) a menudo pueden recuperarse de forma sublineal en . ^[32]${\displaystyle d2^{(\log _{2}\log _{2}N)^{O(1)}}}$${\displaystyle f}$${\displaystyle N}$

Diseño de ensayo multiplex para pruebas COVID19

Durante una pandemia como el brote de COVID-19 en 2020, los ensayos de detección de virus a veces se realizan utilizando diseños de pruebas grupales no adaptativas. ^{[34] [35]} Un ejemplo lo proporcionó el proyecto Origami Assays, que lanzó diseños de pruebas grupales de código abierto para ejecutar en una placa de laboratorio estándar de 96 pocillos. ^[36]

Plantilla de papel Origami Assay para diseño de pruebas grupales

En un entorno de laboratorio, un desafío de las pruebas grupales es que la construcción de las mezclas puede llevar mucho tiempo y ser difícil de realizar con precisión a mano. Los ensayos de Origami proporcionaron una solución para este problema de construcción al proporcionar plantillas de papel para guiar al técnico sobre cómo distribuir las muestras de los pacientes en los pocillos de prueba. ^[37]

Utilizando los diseños de pruebas de grupos más grandes (XL3) fue posible analizar 1120 muestras de pacientes en 94 pocillos de ensayo. Si la tasa de verdaderos positivos era lo suficientemente baja, no se requerían pruebas adicionales.

Ver también: Lista de países que implementan la estrategia de pruebas de piscinas contra COVID-19 .

Análisis forense de datos

La ciencia forense de datos es un campo dedicado a encontrar métodos para recopilar pruebas digitales de un delito. Dichos delitos generalmente involucran a un adversario que modifica los datos, documentos o bases de datos de una víctima, con ejemplos que incluyen la alteración de registros fiscales, un virus que oculta su presencia o un ladrón de identidad que modifica datos personales. ^[26]

Una herramienta común en el análisis forense de datos es el hash criptográfico unidireccional . Esta es una función que toma los datos y, a través de un procedimiento difícil de revertir, produce un número único llamado hash. ^{[i] Los} hash, que a menudo son mucho más cortos que los datos, nos permiten verificar si los datos se han modificado sin tener que almacenar copias completas de la información de forma inútil: el hash de los datos actuales se puede comparar con un hash anterior para determinar si ha ocurrido algún cambio. Una propiedad desafortunada de este método es que, aunque es fácil saber si los datos se han modificado, no hay forma de determinar cómo: es decir, es imposible recuperar qué parte de los datos ha cambiado. ^[26]

Una forma de sortear esta limitación es almacenar más hashes, ahora de subconjuntos de la estructura de datos, para delimitar dónde se ha producido el ataque. Sin embargo, para encontrar la ubicación exacta del ataque con un enfoque ingenuo, sería necesario almacenar un hash para cada dato en la estructura, lo que anularía el punto de los hash en primer lugar. (También se puede almacenar una copia regular de los datos). Las pruebas grupales se pueden utilizar para reducir drásticamente la cantidad de hashes que deben almacenarse. Una prueba se convierte en una comparación entre los valores hash almacenados y actuales, que es positiva cuando hay una falta de coincidencia. Esto indica que al menos un dato editado (que se toma como defectuoso en este modelo) está contenido en el grupo que generó el hash actual. ^[26]

De hecho, la cantidad de hashes necesarios es tan baja que, junto con la matriz de prueba a la que hacen referencia, incluso se pueden almacenar dentro de la estructura organizativa de los datos en sí. Esto significa que, en lo que respecta a la memoria, la prueba se puede realizar "gratis". (Esto es cierto con la excepción de una clave maestra / contraseña que se utiliza para determinar en secreto la función hash). ^[26]

Notas

1. El problema original que estudió Dorfman fue de esta naturaleza (aunque no lo tuvo en cuenta), ya que en la práctica, solo se podía combinar un cierto número de sueros sanguíneos antes de que el procedimiento de prueba dejara de ser confiable. Esta fue la razón principal por la que el procedimiento de Dorfman no se aplicó en ese momento. ^[3]
2. Sin embargo, como suele ser el caso en matemáticas, las pruebas grupales se han reinventado posteriormente varias veces desde entonces, a menudo en el contexto de aplicaciones. Por ejemplo, a Hayes se le ocurrió de forma independiente la idea de consultar grupos de usuarios en el contexto de protocolos de comunicación de accesos múltiples en 1978. ^[9]
3. Esto a veces se conoce como la conjetura de Hu-Hwang-Wang.
4. El número de pruebas,, debe escalar comopara diseños deterministas, en comparación condiseños que permiten probabilidades de error arbitrariamente pequeñas (comoy). ^[4]${\displaystyle t}$${\displaystyle t=O\left(d^{2}\log _{d}n\right)}$${\displaystyle t=O(d\log _{2}n)}$${\displaystyle d\to \infty }$${\displaystyle n\to \infty }$
5. Se debe tener cuidado de distinguir entre cuando una prueba reporta un resultado falso y cuando el procedimiento de prueba grupal falla en su totalidad. Es posible cometer un error sin pruebas incorrectas y no cometer un error con algunas pruebas incorrectas. La mayoría de los algoritmos combinatorios modernos tienen una probabilidad de error distinta de cero (incluso sin pruebas erróneas), ya que esto reduce significativamente el número de pruebas necesarias.
6. De hecho, es posible hacerlo mucho mejor. Por ejemplo, elalgoritmo -stagede Lida una construcción explícita were.${\displaystyle s}$${\displaystyle t\leq {\frac {e}{\log _{2}e}}d\log _{2}{(n/d)}}$
7. Alternativamente,se puede definir mediante la ecuación, donde la multiplicación es lógica Y () y la suma es lógica O (). Aquí,tendrá unpuesto en posiciónsi y solo siyambos sonpara alguno. Es decir, si y solo si se incluyó al menos un artículo defectuoso en laprueba.${\displaystyle \mathbf {y} }$${\displaystyle \mathbf {y} :=M\mathbf {x} }$${\displaystyle \wedge }$${\displaystyle \vee }$${\displaystyle \mathbf {y} }$${\displaystyle 1}$${\displaystyle i}$${\displaystyle (M)_{i,j}}$${\displaystyle \mathbf {x} _{j}}$${\displaystyle 1}$${\displaystyle j}$${\displaystyle i{\textrm {-th}}}$
8. Este tipo de medición surge en muchas aplicaciones. Por ejemplo, ciertos tipos de cámaras digitales ^[28] o máquinas de resonancia magnética ^[29], donde las limitaciones de tiempo requieren que se tomen sólo un pequeño número de mediciones.
9. Más formalmente, los hash tienen una propiedad llamada resistencia a colisiones, que es que la probabilidad de que el mismo hash resulte de diferentes entradas es muy baja para datos de un tamaño apropiado. En la práctica, a menudo se ignora la posibilidad de que dos entradas diferentes produzcan el mismo hash.

Referencias

Citas

1. Colbourn, Charles J .; Dinitz, Jeffrey H. (2007), Manual de diseños combinatorios (2ª ed.), Boca Raton: Chapman & Hall / CRC, p. 574, Sección 46: Diseños de agrupación , ISBN 978-1-58488-506-1
2. Dorfman, Robert (diciembre de 1943), "La detección de miembros defectuosos de grandes poblaciones", The Annals of Mathematical Statistics , 14 (4): 436–440, doi : 10.1214 / aoms / 1177731363 , JSTOR 2235930 
3. Ding-Zhu, Du; Hwang, Frank K. (1993). Ensayos grupales combinatorios y sus aplicaciones . Singapur: World Scientific. ISBN 978-9810212933.
4. Atia, George Kamal; Saligrama, Venkatesh (marzo de 2012). "Prueba de grupo ruidoso y detección comprimida booleana". Transacciones IEEE sobre teoría de la información . 58 (3): 1880-1901. arXiv : 0907.1061 . doi : 10.1109 / TIT.2011.2178156 .
5. Chun Lam Chan; Pak Hou Che; Jaggi, Sidharth; Saligrama, Venkatesh (1 de septiembre de 2011), "2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton)", 49th Annual Allerton Conference on Communication, Control, and Computing , págs. 1832-1839, arXiv : 1107.4540 , doi : 10.1109 / Allerton.2011.6120391 , ISBN 978-1-4577-1817-5
6. Hung, M .; Swallow, William H. (marzo de 1999). "Robustez de las pruebas grupales en la estimación de proporciones". Biometría . 55 (1): 231–237. doi : 10.1111 / j.0006-341X.1999.00231.x . PMID 11318160 . 
7. Chen, Hong-Bin; Fu, Hung-Lin (abril de 2009). "Algoritmos no adaptativos para pruebas de grupo umbral". Matemáticas aplicadas discretas . 157 (7): 1581-1585. doi : 10.1016 / j.dam.2008.06.003 .
8. De Bonis, Annalisa (20 de julio de 2007). "Nuevas estructuras combinatorias con aplicaciones para ensayos grupales eficientes con inhibidores". Revista de optimización combinatoria . 15 (1): 77–94. doi : 10.1007 / s10878-007-9085-1 .
9. Hayes, J. (agosto de 1978). "Una técnica adaptativa para la distribución local". Transacciones IEEE sobre comunicaciones . 26 (8): 1178-1186. doi : 10.1109 / TCOM.1978.1094204 .
10. Sterrett, Andrew (diciembre de 1957). "Sobre la detección de miembros defectuosos de grandes poblaciones" . Los Anales de Estadística Matemática . 28 (4): 1033–1036. doi : 10.1214 / aoms / 1177706807 .
11. Sobel, Milton; Groll, Phyllis A. (septiembre de 1959). "Pruebas grupales para eliminar de manera eficiente todos los defectos en una muestra binomial". Revista técnica de Bell System . 38 (5): 1179-1252. doi : 10.1002 / j.1538-7305.1959.tb03914.x .
12. Li, Chou Hsiung (junio de 1962). "Un método secuencial para el cribado de variables experimentales". Revista de la Asociación Estadounidense de Estadística . 57 (298): 455–477. doi : 10.1080 / 01621459.1962.10480672 .
13. Katona, Gyula OH (1973). "Un estudio de la teoría combinatoria". Problemas de búsqueda combinatoria . Holanda Septentrional, Amsterdam: 285–308.
14. Hwang, Frank K. (septiembre de 1972). "Un método para detectar todos los miembros defectuosos en una población mediante pruebas de grupo". Revista de la Asociación Estadounidense de Estadística . 67 (339): 605–608. doi : 10.2307 / 2284447 . JSTOR 2284447 . 
15. Allemann, Andreas (2013). "Un algoritmo eficiente para pruebas de grupo combinatorias". Teoría de la información, combinatoria y teoría de la búsqueda : 569–596.
16. Hu, MC; Hwang, FK; Wang, Ju Kwei (junio de 1981). "Un problema de límites para pruebas grupales". Revista SIAM de Métodos Algebraicos y Discretos . 2 (2): 81–87. doi : 10.1137 / 0602011 .
17. Leu, Ming-Guang (28 de octubre de 2008). "Una nota sobre la conjetura de Hu-Hwang-Wang para pruebas grupales" . El diario ANZIAM . 49 (4): 561. doi : 10.1017 / S1446181108000175 .
18. Riccio, Laura; Colbourn, Charles J. (1 de enero de 2000). "Límites más definidos en las pruebas de grupo adaptativo" . Revista taiwanesa de matemáticas . 4 (4): 669–673. doi : 10.11650 / twjm / 1500407300 .
19. Aldridge, Matthew; Baldassini, Leonardo; Johnson, Oliver (junio de 2014). "Grupo de algoritmos de prueba: límites y simulaciones". Transacciones IEEE sobre teoría de la información . 60 (6): 3671–3687. arXiv : 1306.6438 . doi : 10.1109 / TIT.2014.2314472 .
20. Baldassini, L .; Johnson, O .; Aldridge, M. (1 de julio de 2013), "2013 IEEE International Symposium on Information Theory", IEEE International Symposium on Information Theory , págs. 2676–2680, arXiv : 1301.7023 , CiteSeerX 10.1.1.768.8924 , doi : 10.1109 / ISIT. 2013.6620712 , ISBN  978-1-4799-0446-4
21. Sobel, Milton; Elashoff, RM (1975). "Pruebas grupales con un nuevo objetivo, estimación". Biometrika . 62 (1): 181-193. doi : 10.1093 / biomet / 62.1.181 . hdl : 11299/199154 .
22. Bar-Noy, A .; Hwang, FK; Kessler, I .; Kutten, S. (1 de mayo de 1992). Un nuevo algoritmo competitivo para pruebas grupales . Undécima Conferencia Conjunta Anual de las Sociedades de Computación y Comunicaciones del IEEE . 2 . págs. 786–793. doi : 10.1109 / INFCOM.1992.263516 . ISBN 978-0-7803-0602-8.
23. Damaschke, Peter (2000). "Aprendizaje eficiente de atributos adaptativo versus no adaptativo" . Aprendizaje automático . 41 (2): 197–215. doi : 10.1023 / A: 1007616604496 .
24. Stinson, DR; van Trung, Tran; Wei, R (mayo de 2000). "Códigos seguros a prueba de marcos, patrones de distribución de claves, algoritmos de prueba de grupo y estructuras relacionadas". Revista de Planificación e Inferencia Estadística . 86 (2): 595–617. CiteSeerX 10.1.1.54.6212 . doi : 10.1016 / S0378-3758 (99) 00131-7 . 
25. Colbourn, CJ; Dinitz, JH; Stinson, DR (1999). "Comunicaciones, criptografía y redes". Encuestas en Combinatoria . 3 (267): 37–41. doi : 10.1007 / BF01609873 .
26. Goodrich, Michael T .; Atallah, Mikhail J .; Tamassia, Roberto (7 de junio de 2005). Indexación de información para análisis forense de datos . Criptografía aplicada y seguridad de la red . Apuntes de conferencias en informática. 3531 . págs. 206–221. CiteSeerX 10.1.1.158.6036 . doi : 10.1007 / 11496137_15 . ISBN  978-3-540-26223-7.
27. Chlebus, BS (2001). "Comunicación aleatoria en redes de radio". En: Pardalos, PM; Rajasekaran, S .; Reif, J .; Rolim, JDP (Eds.), Manual de Computación Aleatoria , Vol. I, p.401–456. Editores académicos Kluwer, Dordrecht.
28. Takhar, D .; Laska, JN; Wakin, MB; Duarte, MF; Baron, D .; Sarvotham, S .; Kelly, KF; Baraniuk, RG (febrero de 2006). "Una nueva arquitectura de cámara de imágenes por compresión que utiliza compresión de dominio óptico". Imágenes electrónicas . Imagen computacional IV. 6065 : 606509–606509–10. Código Bibliográfico : 2006SPIE.6065 ... 43T . CiteSeerX 10.1.1.114.7872 . doi : 10.1117 / 12.659602 . 
29. Candès, EJ (2014). "Matemáticas de la escasez (y algunas otras cosas)". Actas del Congreso Internacional de Matemáticos. Seúl, Corea del Sur.
30. Gilbert, AC; Iwen, MA; Strauss, MJ (octubre de 2008). "Prueba de grupo y recuperación de señal escasa". 42ª Conferencia de Asilomar sobre señales, sistemas y ordenadores: 1059–1063. Instituto de Ingenieros Eléctricos y Electrónicos.
31. Wright, SJ; Nowak, RD; Figueiredo, MAT (julio de 2009). "Reconstrucción escasa por aproximación separable". Transacciones IEEE sobre procesamiento de señales . 57 (7): 2479–2493. Código Bibliográfico : 2009ITSP ... 57.2479W . CiteSeerX 10.1.1.142.749 . doi : 10.1109 / TSP.2009.2016892 . 
32. Berinde, R .; Gilbert, AC; Indyk, P .; Karloff, H .; Strauss, MJ (septiembre de 2008). Combinando geometría y combinatoria: un enfoque unificado para la recuperación de señales dispersas . 46ª Conferencia Anual de Allerton sobre Comunicación, Control y Computación . págs. 798–805. arXiv : 0804.4666 . doi : 10.1109 / ALLERTON.2008.4797639 . ISBN 978-1-4244-2925-7.
33. Indyk, Piotr (1 de enero de 2008). "Construcciones explícitas para la detección comprimida de señales dispersas". Actas del XIX Simposio anual ACM-SIAM sobre algoritmos discretos : 30–33.
34. Austin, David. "Columna de características AMS - estrategias de agrupación para pruebas COVID-19" . Sociedad Matemática Estadounidense . Consultado el 3 de octubre de 2020 .
35. Prasanna, Dheeraj. "Combinación de tapices" . tapestry-pooling.herokuapp.com . Consultado el 3 de octubre de 2020 .
36. "Ensayos de origami" . Ensayos de origami. 2 de abril de 2020 . Consultado el 7 de abril de 2020 .
37. "Ensayos de origami" . Ensayos de origami. 2 de abril de 2020 . Consultado el 7 de abril de 2020 .

Referencias generales

• Ding-Zhu, Du; Hwang, Frank K. (1993). Ensayos grupales combinatorios y sus aplicaciones . Singapur: World Scientific. ISBN 978-9810212933.
• Curso de Atri Rudra sobre códigos de corrección de errores: combinatoria, algoritmos y aplicaciones (primavera de 2007), conferencias 7 .
• Curso de Atri Rudra sobre códigos de corrección de errores: combinatoria, algoritmos y aplicaciones (primavera de 2010), conferencias 10 , 11 , 28 , 29
• Du, D. y Hwang, F. (2006). Diseños de agrupación y pruebas grupales no adaptativas. Boston: Editores de Twayne.
• Aldridge, M., Johnson, O. y Scarlett, J. (2019), Pruebas grupales: una perspectiva de la teoría de la información , fundamentos y tendencias® en las comunicaciones y la teoría de la información: vol. 15: núm. 3-4, págs. 196-392. doi : 10.1561 / 0100000099
• Ely Porat, Amir Rothschild: Esquemas de prueba grupales combinatorios no adaptativos explícitos. ICALP (1) 2008: 748–759
• Kagan, Eugene; Ben-gal, Irad (2014), "Un algoritmo de prueba grupal con aprendizaje informativo en línea", IIE Transactions , 46 (2): 164–184, doi : 10.1080 / 0740817X.2013.803639 , ISSN  0740-817X

Ver también

• Equilibrio rompecabezas