समूह परीक्षण: Difference between revisions

Latest revision as of 18:04, 18 May 2023

प्रकाश बल्ब समस्या का एक उदाहरण, जहां कोई छह प्रकाश बल्बों के मध्य एक टूटे हुए बल्ब को खोज रहा है। यहां, पहले तीन एक बिजली की आपूर्ति से जुड़े हैं और वे प्रकाश (A) करते हैं। यह इंगित करता है कि टूटा हुआ बल्ब अंतिम तीन (B) में से एक होना चाहिए। यदि इसके बजाय बल्ब नहीं जलते, तो यह सुनिश्चित किया जा सकता था कि टूटा हुआ बल्ब पहले तीन में से एक था। इस प्रक्रिया को जारी रखने से तीन से अधिक परीक्षणों में टूटे हुए बल्ब का पता लगाया जा सकता है, जबकि बल्बों को व्यक्तिगत रूप से जांचने पर अधिकतम छह परीक्षण किए जा सकते हैं।

सांख्यिकी और संयोजी गणित में, समूह परीक्षण कोई भी प्रक्रिया है जो कुछ वस्तुओं की पहचान करने के कार्य को अलग-अलग वस्तुओं के बजाय वस्तुओं के समूहों पर परीक्षणों में विभाजित करती है। पहली बार 1943 में, रॉबर्ट डॉर्फमैन द्वारा अध्ययन किया गया, समूह परीक्षण अनुप्रयुक्त गणित का एक अपेक्षाकृत नया क्षेत्र है जिसे व्यावहारिक अनुप्रयोगों की एक विस्तृत श्रृंखला पर अनुप्रयुक्त किया जा सकता है और आज अनुसंधान का एक सक्रिय क्षेत्र है।

समूह परीक्षण के एक परिचित उदाहरण में श्रृंखला में जुड़े प्रकाश बल्बों की एक श्रृंखला सम्मिलित होती है, जहां बल्बों में से एक को टूटा हुआ जाना जाता है। इसका उद्देश्य सबसे कम संख्या में परीक्षणों का उपयोग करके टूटे हुए बल्बों को ढूंढना है (जहां एक परीक्षण तब होता है जब कुछ बल्ब बिजली की आपूर्ति से जुड़े होते हैं)। प्रत्येक बल्बों का व्यक्तिगत रूप से परीक्षण करना एक सरल पद्धति है। हालाँकि, जब बड़ी संख्या में बल्ब होते हैं तो बल्बों को समूहों में संग्रहित करना अधिक कुशल होगा। उदाहरण के लिए, बल्बों के पहले अर्ध भाग को एक साथ जोड़कर, यह निर्धारित किया जा सकता है कि कौन सा आधा बल्ब टूटा हुआ है, केवल एक परीक्षण में आधे बल्बों को खारिज कर दिया गया है।

समूह परीक्षण करने की योजनाएँ सरल या जटिल हो सकती हैं और प्रत्येक चरण में सम्मिलित परीक्षण भिन्न हो सकते हैं। जिन योजनाओं में अगले चरण के लिए परीक्षण पूर्व चरणों के परिणामों पर निर्भर करते हैं, उन्हें अनुकूली प्रक्रियाएँ कहा जाता है, जबकि योजनाएँ इस तरह से परिकल्पित की जाती हैं कि सभी परीक्षण पूर्व से ज्ञात हों, जिन्हें गैर-अनुकूली प्रक्रियाएँ कहा जाता है। एक गैर-अनुकूली प्रक्रिया में सम्मिलित परीक्षणों की योजनाओं की संरचना को संयोजन प्रारुप के रूप में जाना जाता है।

समूह परीक्षण में सांख्यिकी, जीव विज्ञान, अभिकलित्र विज्ञान, चिकित्सा, अभियांत्रिकी और साइबर सुरक्षा सहित कई अनुप्रयोग हैं। मानव संजीन परियोजना द्वारा इन परीक्षण योजनाओं में आधुनिक रुचि को पुनः जागृत किया गया है।^[1]

मूल विवरण और सीमाएँ

गणित के कई क्षेत्रों के विपरीत, समूह परीक्षण की उत्पत्ति एक ही व्यक्ति द्वारा लिखित: रॉबर्ट डोर्फ़मैन^[2]में देखी जा सकती है।^[3]द्वितीय विश्व युद्ध के पर्यंत प्रेरणा उत्पन्न हुई, जब संयुक्त राज्य अमेरिका की सार्वजनिक स्वास्थ्य सेवा और चयनात्मक सेवा प्रणाली ने बड़े पैमाने पर परियोजना प्रारंभ की, जिसमें सभी सिफिलिसजन्य पुरुषों को सम्मिलित करने के लिए कहा गया। रोग के लिए किसी व्यक्ति के परीक्षण में रक्त का नमूना लेना और फिर रोग की उपस्थिति या अनुपस्थिति का निर्धारण करने के लिए नमूने का विश्लेषण करना सम्मिलित है। उस समय, यह परीक्षण करना बहुमूल्य था और प्रत्येक सैनिक का व्यक्तिगत रूप से परीक्षण करना बहुत बहुमूल्य और अक्षम होता है।^[3]

मान लीजिए कि सैनिक $n$ हैं, भिन्न $n$ परीक्षण की इस पद्धति की ओर जाता है। यदि लोगों का एक बड़ा भाग संक्रमित है तो यह पद्धति उचित होगी। हालांकि, अधिक संभाव्यता वाली स्थिति में पुरुषों का केवल एक बहुत ही छोटा भाग संक्रमित होता है, एक अधिक कुशल परीक्षण योजना प्राप्त की जा सकती है। एक अधिक प्रभावी परीक्षण योजना की व्यवहार्यता निम्नलिखित गुणों पर निर्भर करती है: सैनिकों को समूहों में बांटा जा सकता है और प्रत्येक समूहों में रक्त के नमूनों को एक साथ जोड़ा जा सकता है। संयुक्त नमूनों का परीक्षण यह जांचने के लिए किया जा सकता है कि समूह में कम-से-कम एक सैनिक संक्रमित है या नहीं। समूह परीक्षण के पीछे यह केंद्रीय विचार है। यदि इस समूह के एक या अधिक सैनिकों को रोग है, तो एक परीक्षण व्यर्थ है (यह कौन सा सैनिक था यह जानने के लिए और परीक्षण किए जाने की आवश्यकता है)। दूसरी ओर, यदि समूहों में किसी को रोग नहीं है, तो कई परीक्षण बच जाते हैं, क्योंकि उस समूह के प्रत्येक सैनिकों को केवल एक परीक्षण से समाप्त किया जा सकता है।^[3]

जिन वस्तुओं के कारण एक समूह सकारात्मक परीक्षण करता है, उन्हें सामान्यतः दोषपूर्ण वस्तुएँ कहा जाता है (ये टूटे हुए प्रकाश बल्ब, सिफिलिसजन्य पुरुष, आदि हैं)। प्रायः,वस्तुओं की कुल संख्याओं को $n$ और $d$ के रूप में दर्शाया जाता है, जो दोषों की संख्याओं का प्रतिनिधित्व करता है यदि इसे ज्ञात माना जाता है।^[3]

समूह-परीक्षण समस्याओं का वर्गीकरण

समूह-परीक्षण समस्याओं के लिए दो स्वतंत्र वर्गीकरण हैं; प्रत्येक समूह-परीक्षण समस्या या तो अनुकूली या गैर-अनुकूली होती है और या तो संभाव्य या मिश्रित होती है।^[3]

संभाव्य प्रतिरूप में, दोषपूर्ण वस्तुओं को कुछ संभाव्यता वितरण का पालन करने के लिए माना जाता है और इसका उद्देश्य प्रत्येक वस्तु की दोषपूर्णता की पहचान करने के लिए आवश्यक परीक्षणों की प्रत्याशित संख्याओं को कम करना है। दूसरी ओर, संयोजी समूह परीक्षण के साथ, लक्ष्य 'सबसे खराब स्थिति' में आवश्यक परीक्षणों की संख्या को कम करना है - अर्थात, एक मिनमैक्स कलन विधि बनाएं - और दोषों के वितरण का कोई ज्ञान नहीं माना जाता है।^[3]

अन्य वर्गीकरण, अनुकूलता, इस तथ्य से संबंधित है कि परीक्षण में किन वस्तुओं को समूहित करने के लिए चयन करते समय कौन सी सूचना का उपयोग किया जा सकता है। सामान्यतः, परीक्षण करने के लिए किन वस्तुओं का चुनाव पूर्व परीक्षणों के परिणामों पर निर्भर कर सकता है, जैसा कि उपरोक्त प्रकाश बल्ब समस्या में है। एक कलन विधि जो एक परीक्षण करके आगे बढ़ता है और फिर परिणाम (और सभी पूर्व परिणाम) का उपयोग करके यह तय करता है कि कौन सा अगला परीक्षण करना है, जिसे अनुकूली कहा जाता है। इसके विपरीत, गैर-अनुकूली कलन विधि में, सभी परीक्षण पूर्व से तय किए जाते हैं। इस विचार को बहुस्तरीय कलन विधि के लिए सामान्यीकृत किया जा सकता है, जहां परीक्षणों को चरणों में विभाजित किया जाता है और केवल पूर्व चरणों में परीक्षणों के परिणामों के ज्ञान के साथ अगले चरण में प्रत्येक परीक्षण को पूर्व से तय किया जाना चाहिए। हालांकि, अनुकूली कलन विधि प्रारुप में बहुत अधिक स्वतंत्रता प्रदान करते हैं, यह ज्ञात है कि अनुकूली समूह-परीक्षण कलन विधि दोषपूर्ण वस्तुओं के समुच्चय की पहचान करने के लिए आवश्यक परीक्षणों की संख्या में एक स्थिर कारक से अधिक गैर-अनुकूली पर सुधार नहीं करते हैं।^[4]^[3] इसके अतिरिक्त, गैर-अनुकूली विधियां प्रायः व्यवहार में उपयोगी होती हैं क्योंकि परीक्षण प्रक्रिया के प्रभावी वितरण की अनुमति प्रदान करते हुए, पूर्व सभी परीक्षणों के परिणामों का पहले विश्लेषण किए बिना क्रमिक परीक्षणों के साथ आगे बढ़ सकते हैं।

विविधताएं और विस्तारण

समूह परीक्षण की समस्या को बढ़ाने के कई तरीके हैं। सबसे महत्वपूर्ण में से एक को कोलाहलयुक्त समूह परीक्षण कहा जाता है और मूल समस्या की एक बड़ी धारणा से संबंधित है: यह परीक्षण त्रुटि रहित है। एक समूह-परीक्षण समस्या को कोलाहलयुक्त कहा जाता है जब कुछ संभाव्यता होती है कि समूह परीक्षण का परिणाम अवास्तविक होता है (उदाहरण के लिए सकारात्मक आता है जब परीक्षण में कोई दोष नहीं होता है)। बर्नौली रव प्रतिरूप मानता है कि यह संभाव्यता कुछ स्थिरांक $q$ है, परन्तु सामान्यतः यह परीक्षण में दोषों की वास्तविक संख्याओं और परीक्षण की गई वस्तुओं की संख्या पर निर्भर कर सकता है।^[5]उदाहरण के लिए, तनुकरण के प्रभाव को यह कहकर प्रतिरूपित किया जा सकता है कि परीक्षण में अधिक दोषपूर्ण (या परीक्षण की संख्या के एक अंश के रूप में अधिक दोषपूर्ण) होने पर सकारात्मक परिणाम की संभाव्यता अधिक होती है।^[6] एक कोलाहलयुक्त कलन विधि में सदैव एक त्रुटि करने की गैर-शून्य संभाव्यता होगी (अर्थात, किसी वस्तु को अनुचित तरीके से लेबल करना है)।

समूह परीक्षण को उन परिदृश्यों पर विचार करके बढ़ाया जा सकता है जिनमें एक परीक्षण के दो से अधिक संभावित परिणाम हैं। उदाहरण के लिए, एक परीक्षण के परिणाम $0,1$ और $2^{+}$ हो सकते हैं, कोई दोष न होने, दोषपूर्ण, दोष या एक से बड़ी अज्ञात संख्या होने के अनुरूप है। सामान्यतः, परीक्षण के परिणाम-समूह ${0,1,\ldots ,k^{+}}$ पर कुछ $k\in \mathbb {N}$ के लिए विचार करना संभव है।^[3]

एक और विस्तार ज्यामितीय प्रतिबंधों पर विचार करना है, जिन पर समूह का परीक्षण किया जा सकता है। उपरोक्त प्रकाश बल्ब समस्या इस प्रकार के प्रतिबंध का एक उदाहरण है: केवल यथाक्रम दिखाई देने वाले बल्बों का परीक्षण किया जा सकता है। इसी तरह, वस्तुओं को एक वृत्त में व्यवस्थित किया जा सकता है, या सामान्यतः, एक शैली, जहां आलेख पर परीक्षण उपलब्ध पथ हैं। एक अन्य प्रकार का ज्यामितीय प्रतिबंध उन वस्तुओं की अधिकतम संख्याओं पर होगा जिनका एक समूह में परीक्षण किया जा सकता है,^{[lower-alpha 1]} या समूह के आकार को समान होना पड़ सकता है। इसी तरह, यह प्रतिबंध पर विचार करने के लिए उपयोगी हो सकता है कि कोई भी वस्तु केवल कुछ निश्चित परीक्षणों में ही प्रदर्शित हो सकती है।^[3]

समूह परीक्षण के मूल सूत्र को पुनर्मिश्रित करना जारी रखने के अंतहीन तरीके हैं। निम्नलिखित विस्तार से कुछ अधिक विदेशी रूपों का विचार प्राप्त होगा। उचित-औसत-अशीष्ट प्रतिरूप में, प्रत्येक वस्तु अच्छे साधारण या अशीष्ट में से एक है और एक परीक्षण का परिणाम समूह में 'सबसे खराब' वस्तु का प्रकार है। सीमा समूह परीक्षण में, परीक्षण का परिणाम सकारात्मक होता है यदि समूह में दोषपूर्ण वस्तुओं की संख्या कुछ सीमा मान या अनुपात से अधिक है।^[7] अवरोधकों के साथ समूह परीक्षण आण्विक जीवविज्ञान में अनुप्रयोगों के साथ एक प्रकार है। यहां, अवरोधक नामक वस्तुओं की एक तीसरी श्रेणी है और एक परीक्षण का परिणाम सकारात्मक होता है यदि इसमें कम-से-कम एक दोषपूर्ण और कोई अवरोधक नहीं होता है।^[8]

इतिहास और विकास

आविष्कार और प्रारंभिक प्रगति

समूह परीक्षण की अवधारणा को पहली बार 1943 में रॉबर्ट डॉर्फमैन द्वारा एक छोटे विवरण में प्रस्तुत किया गया था^[2] गणितीय सांख्यिकी के इतिहास के टिप्पणी अनुभाग में प्रकाशित हुआ था।^[3]^{[lower-alpha 2]} डोर्फ़मैन का विवरण - जैसा कि समूह परीक्षण पर सभी प्रारंभिक कार्य के साथ - संभाव्य समस्या पर ध्यान केंद्रित किया और सैनिकों के दिए गए समुच्चयों में सभी सिफिलिसजन्य पुरुषों को बाहर निकालने के लिए आवश्यक परीक्षणों की अपेक्षित संख्याओं को कम करने के लिए समूह परीक्षण के उपन्यास विचार का उपयोग करने का लक्ष्य रखा। विधि सरल थी: सैनिकों को एक दिए गए आकार के समूहों में रखें और सकारात्मक समूहों पर अलग-अलग परीक्षणों (आकार एक के समूहों में परीक्षण वस्तु) का उपयोग करके पता लगाएं कि कौन से संक्रमित थे। डोर्फ़मैन ने जनसंख्या में दोषपूर्णता की व्यापकता दर के विरुद्ध इस रणनीति के लिए इष्टतम समूह आकार सारणीबद्ध किया।^[2]स्टीफन सैमुअल्स^[10]व्यापकता दर के एक फलन के रूप में इष्टतम समूह आकार के लिए एक संवृत-रूप समाधान प्राप्त किया।

1943 के पश्चात, कई वर्षों तक समूह परीक्षण व्यापक रूप से अछूता रहा। फिर 1957 में, स्टेरेट ने डॉर्फ़मैन की प्रक्रिया में सुधार किया।^[11] यह नई प्रक्रिया पुनः सकारात्मक समूहों पर अलग-अलग परीक्षण करके प्रारंभ होती है, परन्तु जैसे ही दोष की पहचान होती है, रुक जाती है। फिर, समूह में शेष वस्तुओं का एक साथ परीक्षण किया जाता है, क्योंकि यह बहुत संभाव्यता है कि उनमें से कोई भी दोषपूर्ण नहीं है।

सोबेल और ग्रॉल ने इस विषय पर अपने 1959 के रचनात्मक लेख में समूह परीक्षण का पहला संपूर्ण विवेचन दिया था।^[12] उन्होंने पांच नई प्रक्रियाओं का वर्णन किया - व्यापकता दर अज्ञात होने पर सामान्यीकरण के अतिरिक्त - और इष्टतम के लिए, उन्होंने परीक्षणों की अपेक्षित संख्या के लिए एक स्पष्ट सूत्र प्रदान किया जो इसका उपयोग करेगा। लेख ने पहली बार समूह परीक्षण और सूचना सिद्धांत के मध्य संबंध भी बनाया, साथ ही समूह-परीक्षण समस्या के कई सामान्यीकरणों पर चर्चा की और सिद्धांत के कुछ नए अनुप्रयोग प्रदान किए।

1960 में पीटर उंगर द्वारा मौलिक परिणाम से पता चलता है कि यदि व्यापकता दर $p>p_{u}=(3-{\sqrt {5}})/2\approx 0.38$ है, तो व्यक्तिगत परीक्षणों की अपेक्षित संख्याओं के संबंध में इष्टतम समूह परीक्षण प्रक्रिया है और यदि $p<p_{u}$ है, तो यह इष्टतम नहीं है। हालांकि, यह ध्यान रखना महत्वपूर्ण है कि 80 वर्षों के शोध प्रयासों के बावजूद इष्टतम प्रक्रिया अभी तक $p<p_{u}$ और एक सामान्य जनसंख्या के आकार $n>2$ के लिए अज्ञात है।^[13]

मिश्रित समूह परीक्षण

समूह परीक्षण का अध्ययन पहली बार 1962 में ली द्वारा मिश्रित संदर्भ में किया गया था,^[14] ली के परिचय के साथ $s$ -स्तर कलन विधि है।^[3]ली ने डॉर्फ़मैन के '2-स्तर कलन विधि' की एक स्वेच्छ संख्याओं में चरणों के विस्तार का प्रस्ताव रखा। जिसके लिए इससे अधिक की आवश्यकता नहीं थी, $t={\frac {e}{\log _{2}(e)}}d\log _{2}(n)$ परीक्षण खोजने की प्रत्याभूति $d$ या कम दोषपूर्ण वस्तुएँ $n$ होगी। विचार यह था कि नकारात्मक परीक्षणों में सभी वस्तुओं को पदच्युत कर दिया जाए और शेष वस्तुओं को समूहों में विभाजित कर दिया जाए जैसा कि प्रारंभिक समुच्चय के साथ किया गया था। यह $s-1$ के व्यक्तिगत परीक्षण करने से पहले कई बार किया जाना था।

संयुक्त समूह परीक्षण सामान्य रूप से बाद में 1973 में कैटोना द्वारा पूर्णतया से अध्ययन किया गया था।^[15] कैटोना ने गैर-अनुकूली समूह-परीक्षण का आव्यूह प्रतिनिधित्व प्रस्तुत किया और गैर-अनुकूली 1-दोषपूर्ण स्थिति $t=\lceil \log _{2}(n)\rceil$ परीक्षण में, दोषपूर्ण खोजने के लिए एक प्रक्रिया का उत्पादन किया, जिसे उन्होंने इष्टतम भी सिद्ध किया।

सामान्यतः, अनुकूल संयोजन समूह परीक्षण के लिए इष्टतम कलन विधि खोजना कठिन है और हालांकि समूह परीक्षण के अभिकलनात्मक जटिलता नहीं की गई है, यह कुछ जटिलता वर्ग में कठिन होने का संदेह है।^[3]हालांकि, 1972 में सामान्यीकृत द्विचर-विभाजन कलन विधि के प्रारंभ के साथ एक महत्वपूर्ण सफलता प्राप्त की।^[16]सामान्यीकृत द्विचर-विभाजन कलन विधि सकारात्मक परीक्षण करने वाले समूहों पर एक द्विचर खोज करके कार्य करता है और एक सरल कलन विधि है जो सूचना-निम्न-परिबंध परीक्षणों की संख्याओं से अधिक में दोष नहीं पाता है।

ऐसे परिदृश्यों में जहां दो या दो से अधिक दोष हैं, सामान्यीकृत द्विचर-विभाजन कलन विधि अभी भी निकट-इष्टतम परिणाम उत्पन्न करती है, जिसके लिए अधिकतम $d-1$ की आवश्यकता होती है, सूचना के ऊपर परीक्षण निम्न परिबंध जहाँ $d$ दोषों की संख्या है।^[16]2013 में अल्लेमैन द्वारा इसमें काफी सुधार किए गए थे, जिससे परीक्षणों की आवश्यक संख्या $0.187d+0.5\log _{2}(d)+5.5$ कम हो गई थी। सूचना के ऊपर निम्न परिबंध जब, $n/d\geq 38$ और $d\geq 10$ है।^[17] यह द्विचर-विभाजन कलन विधि में द्विचर खोज को अतिव्यापी परीक्षण समूहों के साथ उप-कलन विधि के एक जटिल समूहों में परिवर्तित कर प्राप्त किया गया था। जैसे, अनुकूली संयोजी समूह परीक्षण की समस्या - दोषों की संख्या पर एक ज्ञात संख्या या उपरिपरिबंध के साथ - आगे सुधार के लिए बहुत कम स्थान के साथ अनिवार्य रूप से हल किया गया है।

एक अनिर्णीत प्रश्न है कि व्यक्तिगत परीक्षण न्यूनतम कब होता है। हू, ह्वांग और वैंग ने 1981 में दर्शाया कि व्यक्तिगत परीक्षण जब, $n\leq \lfloor (5d+1)/2\rfloor$ न्यूनतम और अधिकतम होता है और यह कि जब, $n>3d$ न्यूनतम और अधिकतम नहीं है।^[18] वर्तमान में यह अनुमान लगाया गया है कि यह सीमा तीक्ष्ण है: अर्थात, व्यक्तिगत परीक्षण न्यूनतम है यदि और केवल यदि, $n\leq 3d$ है।^[19]^{[lower-alpha 3]} 2000 में रिकसियो और कोलबर्न द्वारा कुछ प्रगति की गई, जिन्होंने बड़े पैमाने पर $n$ दर्शाया, व्यक्तिगत परीक्षण न्यूनतम है जब, $d\geq n/\log _{3/2}(3)\approx 0.369n$ है।^[20]

गैर-अनुकूली और संभाव्य परीक्षण

गैर-अनुकूली समूह परीक्षण में प्रमुख अंतर्दृष्टि में से एक यह है कि आवश्यकता को समाप्त करके महत्वपूर्ण लाभ प्राप्त किया जा सकता है कि समूह-परीक्षण प्रक्रिया सफल होने के लिए निश्चित है (संयोजन समस्या), बल्कि इसके बजाय प्रत्येक वस्तु को अवास्तविक लेबल करने की कुछ कम, परन्तु गैर-शून्य संभाव्यता ("संभाव्य" समस्या) की अनुमति प्रदान करें। यह ज्ञात है कि जैसे-जैसे दोषपूर्ण वस्तुओं की संख्या वस्तुओं की कुल संख्या तक पहुँचती है, सटीक संयोजी समाधानों के लिए संभाव्य समाधानों की तुलना में काफी अधिक परीक्षणों की आवश्यकता होती है - यहाँ तक कि संभाव्य समाधान भी त्रुटि के केवल असममित रूप से इष्टतम कलन विधि की अनुमति प्रदान करते हैं।^[4]^{[lower-alpha 4]}

इस शैली में, चैन एट अल (2011) ने सीओएमपी प्रस्तुत किया, एक संभाव्य कलन विधि जिसके लिए इससे अधिक की आवश्यकता नहीं है, $t=ed(1+\delta )\ln(n)$ तक पता लगाने के लिए परीक्षण $d$ में त्रुटि है। त्रुटि की संभाव्यता वाले वस्तु $n$ से अधिक $n^{-\delta }$ नहीं है।^[5]यह के एक स्थिर कारक $t=O(d\log _{2}n)$ निम्न परिबंध के भीतर है।^[4]

चान एट अल (2011) ने एक साधारण कोलाहलयुक्त प्रतिरूप के लिए सीओएमपी का एक सामान्यीकरण भी प्रदान किया और इसी तरह एक स्पष्ट प्रदर्शन बाध्यता का उत्पादन किया, जो पुनः केवल एक स्थिर (असफल परीक्षण की संभाव्यता पर निर्भर) संबंधित निम्न परिबंध से ऊपर था।^[4]^[5]सामान्यतः, बर्नौली रव स्थिति में आवश्यक परीक्षणों की संख्या नीरव स्थिति की तुलना में एक बड़ा कारक है।^[5]

एल्ड्रिज, बलदासिनी और जॉनसन (2014) ने सीओएमपी कलन विधि का एक विस्तार तैयार किया जिसमें अतिरिक्त पश्च-प्रसंस्करण चरण जोड़े गए।^[21]उन्होंने दर्शाया कि इस नए कलन विधि का प्रदर्शन, जिसे डीडी कहा जाता है, सीओएमपी के प्रदर्शन से बहुत अधिक है और यह कि डीडी उन परिदृश्यों में 'अनिवार्य रूप से इष्टतम' है, जहां $d^{2}\geq n$ है, इसे एक काल्पनिक कलन विधि से तुलना करके जो एक उचित इष्टतम को परिभाषित करता है। इस काल्पनिक कलन विधि के प्रदर्शन से पता चलता है कि जब, $d^{2}<n$ सुधार की सम्भावना है, साथ ही यह सुझाव दे रहे है कि इसमें कितना सुधार हो सकता है।^[21]

संयोजक समूह परीक्षण का औपचारीकरण

यह खंड समूह परीक्षण से संबंधित धारणाओं और प्रतिबंधों को औपचारिक रूप से परिभाषित करता है।

निविष्ट सदिश, $\mathbf {x} =(x_{1},x_{2},\dots ,x_{n})$ , को लंबाई $n$ (अर्थात, $\mathbf {x} \in \{0,1\}^{n}$ ) के द्विचर सदिश के रूप में परिभाषित किया गया है, जे-वें वस्तु को दोषपूर्ण कहा जा रहा है यदि और केवल यदि $x_{j}=1$ है। इसके अतिरिक्त, किसी भी गैर-दोषपूर्ण वस्तु को 'उचित' वस्तु कहा जाता है।

$\mathbf {x}$ का उद्देश्य दोषपूर्ण वस्तुओं के (अज्ञात) समूहों का वर्णन करना है। $\mathbf {x}$ की प्रमुख विशेषता यह है कि यह एक निहित निविष्ट है। कहने का तात्पर्य यह है कि $\mathbf {x}$ की प्रविष्टियाँ क्या हैं, इसका कोई प्रत्यक्ष ज्ञान नहीं है। इसके अतिरिक्त, जो 'परीक्षणों' की कुछ श्रृंखलाओं के माध्यम से अनुमान लगाया जा सकता है। यह अगली परिभाषा की ओर जाता है।

मान लीजिए कि $\mathbf {x}$ एक निविष्ट सदिश है। एक समुच्चय, $S\subseteq \{1,2,\dots ,n\}$ को परीक्षण कहा जाता है। जब परीक्षण नीरव होता है, तो $j\in S$ उपस्थित होने पर परीक्षण का परिणाम सकारात्मक होता है।

इसलिए, समूह परीक्षण का लक्ष्य अनुमति प्रदान करने वाले परीक्षणों की 'लघु' श्रृंखला चयन करने के लिए एक विधि के साथ आना है, या तो बिल्कुल या उच्च स्तर की निश्चितता के साथ $\mathbf {x}$ निर्धारित किया जाना है।

एक समूह-परीक्षण कलन विधि को एक त्रुटि करने के लिए कहा जाता है यदि यह किसी वस्तु को भ्रामक तरीके से लेबल करता है (अर्थात, किसी भी दोषपूर्ण वस्तु को गैर-दोषपूर्ण या इसके विपरीत के रूप में लेबल करता है)। यह एक समूह परीक्षण के भ्रामक होने के परिणाम के समान नहीं है। एक कलन विधि को शून्य-त्रुटि कहा जाता है यदि त्रुटि होने की संभाव्यता शून्य है।^{[lower-alpha 5]}
$t(d,n)$ सदैव $d$ के मध्य त्रुटिपूर्ण $n$ किसी भी समूह-परीक्षण कलन विधि द्वारा त्रुटि की शून्य संभाव्यता वाले वस्तु को खोजने के लिए आवश्यक परीक्षणों की न्यूनतम संख्या को दर्शाता है। समान मात्रा के लिए, परन्तु प्रतिबंध के साथ कि कलन विधि गैर-अनुकूली है, अंकन ${\bar {t}}(d,n)$ प्रयोग किया जाता है।

सामान्य सीमा

चूंकि समायोजन $S_{j}=\{j\}$ द्वारा प्रत्येक $1\leq j\leq n$ के लिए व्यक्तिगत परीक्षण का प्रयोग करना सदैव संभव होता है, यह ${\bar {t}}(d,n)\leq n$ होना चाहिए। इसके अतिरिक्त, चूंकि किसी भी गैर-अनुकूली परीक्षण प्रक्रिया को एक अनुकूली कलन विधि के रूप में लिखा जा सकता है, केवल उनके परिणामों, $t(d,n)\leq {\bar {t}}(d,n)$ की परवाह किए बिना सभी परीक्षण करके है। अंत में, जब $0\neq d\neq n$ , कम-से-कम एक वस्तु है जिसकी त्रुटि का निर्धारण किया जाना चाहिए (कम-से-कम एक परीक्षण द्वारा) और इसी तरह $1\leq t(d,n)$ है।

संक्षेप में (मानते समय $0\neq d\neq n$ ), $1\leq t(d,n)\leq {\bar {t}}(d,n)\leq n$ है।^{[lower-alpha 6]}

सूचना निम्न परिबंध

निरूपित ${\mathcal {S}}$ प्रतिदर्श समष्टि की धारणा का उपयोग करके आवश्यक परीक्षणों की संख्या पर एक निम्न परिबंध का वर्णन किया जा सकता है, जो केवल दोषों के संभावित नियोजन का समुच्चय है। प्रतिदर्श समष्टि ${\mathcal {S}}$ के साथ किसी भी समूह परीक्षण समस्या के लिए और कोई भी समूह-परीक्षण कलन विधि, यह $t\geq \lceil \log _{2}{|{\mathcal {S}}|}\rceil$ द्वारा दर्शाया जा सकता है, जहाँ $t$ त्रुटि की शून्य संभाव्यता के साथ सभी दोषों की पहचान करने के लिए आवश्यक परीक्षणों की न्यूनतम संख्या है। इसे सूचना निम्न परिबंध कहा जाता है।^[3]यह सीमा इस तथ्य से ली गई है कि प्रत्येक परीक्षण के पश्चात, ${\mathcal {S}}$ दो अलग-अलग उपसमुच्चयों में विभाजित है, प्रत्येक परीक्षण के दो संभावित परिणामों में से एक के अनुरूप है।

हालाँकि, छोटी-छोटी समस्याओं के लिए भी, निम्न परिबंध वाली सूचनाएँ सामान्यतः अप्राप्य होती हैं।^[3]इसका विभाजक ${\mathcal {S}}$ यादृच्छिक नहीं है, क्योंकि यह कुछ परीक्षण द्वारा प्रत्यक्ष करने योग्य होना चाहिए।

वास्तव में, निम्न परिबंध की सूचना को उस स्थिति में सामान्यीकृत किया जा सकता है जहां गैर-शून्य संभाव्यता है कि कलन विधि त्रुटि करता है। इस रूप में, प्रमेय हमें परीक्षणों की संख्या के आधार पर सफलता की संभाव्यता पर उपरिपरिबंध देता है। प्रदर्शन करने वाले किसी भी समूह-परीक्षण कलन विधि के लिए $t$ परीक्षण, सफलता की संभाव्यता, $\mathbb {P} ({\textrm {success}})$ , $\mathbb {P} ({\textrm {success}})\leq t/\log _{2}{n \choose d}$ संतुष्ट करता है तथा $\mathbb {P} ({\textrm {success}})\leq {\frac {2^{t}}{n \choose d}}$ को प्रबल किया जा सकता है।^[5]^[22]

गैर-अनुकूली कलन विधि का प्रतिनिधित्व

एक विशिष्ट समूह परीक्षण व्यवस्थापन है। एक गैर-अनुकूली कलन विधि पहले आव्यूह

M

का चयन करता है और फिर सदिश y दिया जाता है। समस्या तब x के लिए एक अनुमान खोजने की है।

गैर-अनुकूली समूह परीक्षण के कलन विधि में दो अलग-अलग चरण होते हैं। सर्वप्रथम, यह तय किया जाता है कि कितने परीक्षण करने हैं और प्रत्येक परीक्षण में कौन से वस्तु सम्मिलित करने हैं। दूसरे चरण में, जिसे प्रायः विकूटन चरण कहा जाता है, प्रत्येक समूह परीक्षण के परिणामों का विश्लेषण यह निर्धारित करने के लिए किया जाता है कि किन वस्तुओं के दोषपूर्ण होने की संभाव्यता है। पहले चरण को सामान्यतः आव्यूह में निम्नानुसार कूटबद्‍ध किया जाता है।^[5]

मान लीजिए कि एक गैर-अनुकूली समूह परीक्षण प्रक्रिया है, वस्तु $n$ में $S_{1},S_{2},\dots ,S_{t}$ , कुछ $t\in \mathbb {N} _{\geq 0}$ के लिए परीक्षण सम्मिलित हैं। इस योजना परीक्षण आव्यूह $t\times n$ द्विचर आव्यूह $M$ है, जहाँ $(M)_{ij}=1$ यदि और केवल यदि $j\in S_{i}$ (और शून्य है अन्यथा) है।

इस प्रकार प्रत्येक स्तंभ $M$ एक वस्तु का प्रतिनिधित्व करता है और प्रत्येक पंक्ति एक के साथ एक परीक्षण का प्रतिनिधित्व करती है। $1$ में $(i,j){\textrm {-th}}$ इंगित करती है कि $i{\textrm {-th}}$ परीक्षण में सम्मिलित $j{\textrm {-th}}$ वस्तु है और $0$ अन्यथा इंगित करती है।

साथ ही सदिश $\mathbf {x}$ ( $n$ लंबाई का) जो अज्ञात दोषपूर्ण समुच्चय का वर्णन करता है, परिणाम सदिश प्रस्तुत करना सामान्य है, जो प्रत्येक परीक्षण के परिणामों का वर्णन करता है।

मान लीजिए कि $t$ एक गैर-अनुकूली कलन विधि द्वारा किए गए परीक्षणों की संख्या है। परिणाम सदिश, $\mathbf {y} =(y_{1},y_{2},\dots ,y_{t})$ , लंबाई $t$ (अर्थात, $\mathbf {y} \in \{0,1\}^{t}$ ) का एक द्विचर सदिश ऐसा है कि $y_{i}=1$ यदि और केवल यदि $i{\textrm {-th}}$ का परिणाम परीक्षण सकारात्मक था (अर्थात, कम-से-कम एक दोषपूर्ण था)।^{[lower-alpha 7]}

इन परिभाषाओं के साथ, गैर-अनुकूली समस्या को निम्नानुसार फिर से तैयार किया जा सकता है: पहले एक परीक्षण आव्यूह $M$ का चयन किया है। जिसके पश्चात सदिश $\mathbf {y}$ वापस आ गया है।

सरलतम कोलाहलयुक्त वाले स्थिति में, जहां एक निरंतर संभाव्यता $q$ होती है। एक समूह परीक्षण का एक भ्रामक परिणाम होगा, एक यादृच्छिक द्विचर सदिश $\mathbf {v}$ पर विचार करता है, जहां प्रत्येक प्रविष्टि की संभाव्यता $q$ की $1$ और $0$ अन्यथा है। लौटाया गया सदिश तब ${\hat {\mathbf {y} }}=\mathbf {y} +\mathbf {v}$ है, सामान्य जोड़ के साथ $(\mathbb {Z} /2\mathbb {Z} )^{n}$ (समान रूप से यह तत्व-वार एक्सओआर संक्रिया है)।^[5]

गैर-अनुकूली कलन विधि के लिए सीमाएं

आव्यूह प्रतिनिधित्व गैर-अनुकूली समूह परीक्षण पर कुछ सीमाएं सिद्ध करना संभव बनाता है। दृष्टिकोण कई नियतात्मक प्रारूपों का दर्पण है, जहां $d$ - वियोज्य मैट्रिक्स पर विचार किया जाता है, जैसा कि नीचे परिभाषित किया गया है।^[3]

एक द्विचर आव्यूह $M$ कहा जाता है, $d$ - वियोज्य यदि प्रत्येक बूलियन योग (तार्किक ओआर) है, $d$ इसके स्तंभ भिन्न हैं। इसके अतिरिक्त, अंकन ${\bar {d}}$ - वियोज्य इंगित करता है कि किसी भी तक का प्रत्येक योग $d$ का $M$ स्तंभ भिन्न है।

जब $M$ एक परीक्षण आव्यूह है, $d$ - वियोज्य ( ${\bar {d}}$ -पृथक्करणीय) के मध्य अंतर करने $d$ दोषपूर्ण में सक्षम होने के समान है। हालांकि, यह प्रत्याभूति नहीं प्रदान करता है कि यह सीधा होगा। एक प्रबल गुणधर्म कहा जाता है, $d$ -विच्छेदन करता है।

एक द्विचर आव्यूह $M$ कहा जाता है, $d$ -वियोज्य यदि किसी का बूलियन योग $d$ स्तंभ में कोई अन्य स्तंभ नहीं है। (इस संदर्भ में, एक स्तंभ A में एक स्तंभ B होता है, यदि प्रत्येक तालिका के लिए जहां B में 1 है, A में भी 1 है)।

$d$ -वियोजित का उपयोगी गुण है, परीक्षण मैट्रिक्स वह है, जिसके साथ $d$ दोषपूर्ण, प्रत्येक गैर-दोषपूर्ण वस्तु कम-से-कम एक परीक्षण में दिखाई देगी जिसका परिणाम नकारात्मक है। इसका अर्थ है कि दोषों को खोजने के लिए एक सरल प्रक्रिया है: नकारात्मक परीक्षण में दिखाई देने वाली प्रत्येक वस्तु को पदच्युत कर दें।

$d$ - वियोज्य के गुणों का उपयोग करना और $d$ -वियोजित मैट्रिक्स को पहचानने की समस्या के लिए निम्नलिखित $d$ मध्य में त्रुटिपूर्ण $n$ कुल वस्तु दर्शाया जा सकता है।^[4]

त्रुटि पैमानों की विषमता से छोटी औसत संभाव्यता के लिए आवश्यक परीक्षणों की संख्या $O(d\log _{2}n)$ है।
त्रुटि पैमानों की असम्बद्ध रूप से छोटी अधिकतम संभाव्यता के लिए आवश्यक परीक्षणों की संख्या $O(d^{2}\log _{2}n)$ है।
त्रुटि पैमानों की शून्य संभाव्यता के लिए आवश्यक परीक्षणों की संख्या $O\left({\frac {d^{2}\log _{2}n}{\log _{2}d}}\right)$ है।

सामान्यीकृत द्विचर-विभाजन कलन विधि

File:Generalised binary splitting.svg

सामान्यीकृत द्विचर-विभाजन कलन विधि का एक उदाहरण, जहां 8 दोषपूर्ण और कुल 135 वस्तुएँ हैं। यहाँ,

2^{\alpha _{1}}=16

, और पहला परीक्षण एक ऋणात्मक परिणाम देता है इसलिए प्रत्येक वस्तु को गैर-दोषपूर्ण घोषित किया जाता है। अतः 119 वस्तुएँ

2^{\alpha _{2}}=8

शेष हैं। यह दूसरा समूह एक धनात्मक परिणाम प्रदान करता है, इसलिए दोषपूर्ण खोजने के लिए एक द्विआधारी खोज का उपयोग किया जाता है। एक बार ऐसा करने के पश्चात, पूर्ण प्रक्रिया दोहराई जाती है, एक नई गणना

\alpha

की जाती है, केवल उन्हीं वस्तुओं का उपयोग करना जिनकी त्रुटिपूर्ण का निर्धारण नहीं किया गया है।

सामान्यीकृत द्विचर-विभाजन कलन विधि एक अनिवार्य रूप से इष्टतम अनुकूली समूह-परीक्षण कलन विधि है जो पाता है कि $d$ या कम दोषपूर्ण $n$ वस्तु इस प्रकार है:^[3]^[16]

यदि $n\leq 2d-2$ , $n$ वस्तु का व्यक्तिगत रूप से परीक्षण करें। अन्यथा समुच्चय $l=n-d+1$ और $\alpha =\lfloor \log _{2}{l/d}\rfloor$ है।
आकृति $2^{\alpha }$ के समूह का परीक्षण करें यदि परिणाम ऋणात्मक है, तो समूह की प्रत्येक वस्तु को गैर-दोषपूर्ण घोषित किया जाता है; समुच्चय $n:=n-2^{\alpha }$ और चरण 1 पर जाएं। अन्यथा, एक दोषपूर्ण और एक अनिर्दिष्ट संख्या की पहचान करने के लिए एक द्विआधारी खोज का उपयोग करें, जिसे $x$ कहा जाता है, गैर-दोषपूर्ण वस्तुओं का; समुच्चय $n:=n-1-x$ और $d:=d-1$ है। चरण 1 पर जाएँ।

सामान्यीकृत द्विचर-विभाजन कलन विधि से अधिक जहां $T$ परीक्षण की आवश्यकता नहीं है;

$T={\begin{cases}n&n\leq 2d-2\\(\alpha +2)d+p-1&n\geq 2d-1\end{cases}}$ है।^[3]

$n/d$ बड़े के लिए, $T\rightarrow d\log _{2}(n/d)$ के द्वारा दर्शाया जा सकता है,^[3]जो $t={\frac {e}{\log _{2}e}}d\log _{2}\left({\frac {n}{d}}\right)$ के अनुकूल तुलना करता है, ली के लिए आवश्यक परीक्षण $s$ -स्तर कलन विधि है। वास्तव में, सामान्यीकृत द्विचर-विभाजन कलन विधि निम्नलिखित अर्थों में इष्टतम के समीप है। जब $d\geq 2$ को $T-B_{I}(d,n)\leq (d-1)$ के द्वारा दर्शाया जा सकता है, जहाँ $B_{I}(d,n)=\left\lceil \log _{2}\sum _{i=0}^{d}{n \choose i}\right\rceil$ सूचना निम्न परिबंध है।^[3]^[16]

गैर-अनुकूली कलन विधि

गैर-अनुकूली समूह-परीक्षण कलन विधि यह मानते हैं कि दोषों की संख्या, या कम-से-कम उन पर एक अच्छी उपरिपरिबंध ज्ञात है।^[5] यह मात्रा बताई गई $d$ इस खंड में है। यदि कोई सीमा ज्ञात नहीं है, तो कम परिप्रश्न जटिलता वाले गैर-अनुकूली कलन विधि हैं जो $d$ अनुमान लगाने में सहायता कर सकते हैं।^[23]

संयोजी लांबिक सुमेलन अनुधावन (सीओएमपी)

File:COMP Algorithm.svg

सीओएमपी कलन विधि का एक उदाहरण है। सीओएमपी वस्तु a को दोषपूर्ण और वस्तु b को गैर-दोषपूर्ण होने के रूप में पहचानता है। हालाँकि, यह अनुचित तरीके से c को दोषपूर्ण के रूप में लेबल करता है, क्योंकि यह प्रत्येक परीक्षण में दोषपूर्ण वस्तुओं द्वारा "गुप्त" होता है जिसमें यह प्रकट होता है।

संयोजी लांबिक सुमेलन अनुधावन, या सीओएमपी, एक सरल गैर-अनुकूली समूह-परीक्षण कलन विधि है जो इस खंड में आने वाले अधिक सम्मिश्र कलन विधि के लिए आधार बनाता है।

सर्वप्रथम, परीक्षण आव्यूह की प्रत्येक प्रविष्टि आई.आई.डी. को संभाव्यता के साथ $1/d$ और $0$ अन्यथा चयनित किया जाता है।

विकूटन चरण स्तंभ-वार (अर्थात, वस्तु द्वारा) आगे बढ़ता है। यदि प्रत्येक परीक्षण जिसमें कोई वस्तु दिखाई देती है, सकारात्मक है, तो वस्तु को दोषपूर्ण घोषित किया जाता है; अन्यथा वस्तु को गैर-दोषपूर्ण माना जाता है या समकक्ष रूप से, यदि कोई वस्तु किसी परीक्षण में दिखाई देता है जिसका परिणाम ऋणात्मक है, तो वस्तु को गैर-दोषपूर्ण घोषित किया जाता है; अन्यथा वस्तु को दोषपूर्ण माना जाता है। इस कलन विधि की एक महत्वपूर्ण विशेषता यह है कि यह कभी भी मिथ्या अपवर्जित नहीं बनाता है, हालांकि मिथ्या सकारात्मकता तब होती है जब सभी स्थान जे-वें स्तंभ में $M$ होते हैं (एक गैर-दोषपूर्ण वस्तु जे के अनुरूप) दोषपूर्ण वस्तुओं के अनुरूप अन्य स्तंभों के द्वारा "गुप्त" हैं।

सीओएमपी कलन विधि को $ed(1+\delta )\ln(n)$ से अधिक की आवश्यकता नहीं है, त्रुटि संभाव्यता से कम या समान होने के लिए परीक्षण $n^{-\delta }$ है।^[5]यह उपरोक्त त्रुटि की औसत संभाव्यता के लिए निम्न परिबंध के एक स्थिर कारक के भीतर है।

कोलाहलयुक्त के स्थिति में, मूल सीओएमपी कलन विधि में आवश्यकता को शिथिल किया जाता है जो कि किसी भी स्तंभ में किसी के स्थान का समुच्चय होता है, एक सकारात्मक वस्तु $M$ के अनुरूप पूर्णतया से परिणाम सदिश में उनके स्थानों के समुच्चय में समाहित होना चाहिए। इसके बजाय, कोई एक निश्चित संख्या में "बेमेल" की अनुमति प्रदान करता है - बेमेल की यह संख्या प्रत्येक स्तंभ में दोनों की संख्या और कोलाहलयुक्त मापदण्ड $q$ दोनों पर निर्भर करती है। इस कोलाहलयुक्त सीओएमपी कलन विधि $4.36({\sqrt {\delta }}+{\sqrt {1+\delta }})^{2}(1-2q)^{-2}d\log _{2}{n}$ से अधिक की आवश्यकता नहीं है, अधिकतम त्रुटि संभाव्यता प्राप्त करने के लिए परीक्षण $n^{-\delta }$ है।^[5]

निश्चित दोष (डीडी)

निश्चित दोषपूर्ण विधि (DD) सीओएमपी कलन विधि का एक विस्तार है जो किसी भी मिथ्या सकारात्मकता को पदच्युत करने का प्रयास करता है। डीडी के लिए निष्पादन प्रत्याभूतियों को सीओएमपी से दृढ़ता से अधिक दर्शाया गया है।^[21] विकूटन चरण सीओएमपी कलन विधि की एक उपयोगी गुणधर्म का उपयोग करता है: प्रत्येक वस्तु जो सीओएमपी गैर-दोषपूर्ण घोषित करता है, निश्चित रूप से गैर-दोषपूर्ण है (अर्थात, कोई मिथ्या अपवर्जित नहीं है)। यह निम्नानुसार आगे बढ़ता है।

सर्वप्रथम सीओएमपी कलन विधि चलायी जाती है और कोई भी गैर-दोष जिसका पता चलता है उसे पदच्युत कर दिया जाता है। शेष सभी वस्तु अब "संभवतः दोषपूर्ण" हैं।
अगला कलन विधि सभी सकारात्मक परीक्षणों को देखता है। यदि कोई वस्तु किसी परीक्षण में एकमात्र संभव दोषों के रूप में दिखाई देती है, तो उसे दोषपूर्ण होना चाहिए, इसलिए कलन विधि उसे दोषपूर्ण घोषित करता है।
अन्य सभी वस्तुओं को गैर-दोषपूर्ण माना जाता है। इस अंतिम चरण का औचित्य इस धारणा से आता है कि दोषों की संख्या कुल वस्तुओं की संख्या से बहुत कम है।

ध्यान दें कि चरण 1 और 2 में कभी त्रुटि नहीं होती है, इसलिए कलन विधि केवल तभी त्रुटि कर सकता है जब वह किसी दोषपूर्ण वस्तु को गैर-दोषपूर्ण घोषित करता है। इस प्रकार डीडी कलन विधि केवल मिथ्या अपवर्जित बना सकता है।

अनुक्रमिक सीओएमपी (एससीओएमपी)

एससीओएमपी (अनुक्रमिक सीओएमपी) एक कलन विधि है जो इस तथ्य का उपयोग करता है कि डीडी अंतिम चरण तक कोई त्रुटि नहीं करता है, जहां यह माना जाता है कि शेष वस्तु गैर-दोषपूर्ण हैं। बता दें कि घोषित दोषों का समुच्चय $K$ है। एक सकारात्मक परीक्षण $K$ द्वारा समझाया गया कहा जाता है, यदि $K$ में कम-से-कम एक वस्तु है। एससीओएमपी के साथ मुख्य अवलोकन यह है कि डीडी द्वारा पाए गए दोषों का समुच्चय प्रत्येक सकारात्मक परीक्षण की व्याख्या नहीं कर सकता है और यह कि प्रत्येक अस्पष्टीकृत परीक्षण में एक छिपी हुई त्रुटि होनी चाहिए।

कलन विधि निम्नानुसार आगे बढ़ता है।

$K$ प्राप्त करने के लिए डीडी कलन विधि के चरण 1 और 2 को पूर्ण करें, दोषों के समुच्चय के लिए एक प्रारंभिक अनुमान है।
यदि $K$ प्रत्येक सकारात्मक परीक्षण की व्याख्या करता है, कलन विधि को समाप्त करता है: $K$ दोषों के समुच्चय के लिए अंतिम अनुमान है।
यदि कोई अस्पष्टीकृत परीक्षण हैं, तो संभावित दोष खोजें जो अस्पष्टीकृत परीक्षणों की सबसे बड़ी संख्या में प्रकट होता है और इसे दोषपूर्ण घोषित करें (अर्थात, इसे समुच्चय $K$ में जोड़ें) चरण 2 पर जाएँ।

अनुरूपण में, एससीओएमपी को उन्नत प्रदर्शन के समीप दर्शाया गया है।^[21]

बहुपद समुच्चय (पीपी)

एक नियतात्मक कलन विधि जो सटीक रूप से $d$ सकारात्मक बहुपद समुच्चय (पीपी) तक की प्रतिभूति प्रदान करता।^[24]कलन विधि संयोजन आव्यूह $M$ के निर्माण के लिए है, जिसका सीधा उपयोग y में टिप्पणियों को कूट वाचन करने के लिए किया जा सकता है। सीओएमपी के समान, संबंध: $x_{i}=1~~{\text{ if }}~~M(:,i)~.*~y=M(:,i)$ के अनुसार एक प्रतिरूप कूट वाचन किया गया है, जहाँ $.*$ तत्व वार गुणन का प्रतिनिधित्व करता है और $M(:,i)$ $i$ वें का $M$ स्तम्भ है। चूंकि विकूटन चरण कठिन नहीं है, पीपी उत्पन्न करने के लिए विशिष्ट $M$ है।

समूह प्ररूपण

File:Design k3 p3 n1 d3 l1S.svg

प्रारुप

q^{c-1}=9

के साथ एक समूह प्रतिरूप (नीला) के एक समुच्चय से

n=q^{c}=27

बहुपद समुच्चय कलन विधि का उपयोग करके कुल प्रतिरूप है।

एक समूह / समुच्चय $\ell$ एक बहुपद संबंध का उपयोग करके उत्पन्न किया जाता है जो प्रत्येक समुच्चय में निहित प्रतिरूपों के सूचकांकों को निर्दिष्ट करता है। निविष्ट मापदण्ड का एक समुच्चय कलन विधि निर्धारित करता है। एक प्रमुख संख्या $p>1$ के लिए और एक पूर्णांक $n\geq 1$ किसी भी प्रमुख घात $q=p^{n}$ द्वारा परिभाषित किया गया है। एक आयामी मापदण्ड $c\geq 2$ के लिए प्रतिरूपों की कुल संख्या $n=q^{c}$ है और प्रति समुच्चय प्रतिरूपों की संख्या $q^{c-1}$ है। इसके अतिरिक्त, क्रम $q$ का परिमित क्षेत्र $\mathbb {F} _{q}$ द्वारा निरूपित किया जाता है, (अर्थात, पूर्णांक $\{0,1,2,\ldots ,q-1\}$ विशेष अंकगणितीय परिचालनों द्वारा परिभाषित किया गया है जो यह सुनिश्चित करता है कि जोड़ और गुणा में $\mathbb {F} _{q}$ में $\mathbb {F} _{q}$ नियत रहता है)। विधि प्रत्येक प्रतिरूप को संजाल में व्यवस्थित करती है और निर्देशांक $x=(u,v)$ द्वारा इसका प्रतिनिधित्व करती है। निर्देशांकों की गणना पूर्णांकों $1\leq l\leq c-1$ , $0\leq u_{i_{l}}\leq q-1$ का उपयोग करके एक बहुपद संबंध के अनुसार की जाती है।

 $v~=~a^{c-1}~u_{i_{c-1}}+\cdots +a~u_{i_{1}}+b,\quad a,b,u_{i_{l}}\in \mathbb {F} _{q}$

$u_{i_{l}}$ के माध्यम से विपाशन के संयोजन मानों को एक समुच्चय $q^{c-1}$ अनुक्रम के तत्व, पूर्णांक $d-1$ द्वारा दर्शाया जाता है, अर्थात, $u_{i_{1}}\times \cdots \times u_{i_{c-1}}=\{(i_{1},\ldots ,i_{c-1})\}$ , जहाँ $0\leq i_{l}\leq q-1$ है। व्यापकता के हानि के बिना, संयोजन ऐसा है कि $i_{d-1}$ चक्र प्रत्येक $q$ समय, $i_{d-2}$ चक्र प्रत्येक $q^{2}$ समय, $i_{1}$ चक्र तक केवल एक बार है। सूत्र जो निश्चित के लिए प्रतिरूप सूचकांकों की गणना करते हैं और इस प्रकार संबंधित समुच्चय $a$ और $b$ द्वारा दिया गया है।

${\begin{aligned}u_{i}&=\sum _{l=1}^{c-1}~q^{d-1-l}~i_{l}\\v_{u_{i}}&=\sum _{l=1}^{c-1}~a^{l}~i_{l}+b\quad ({\text{computed in }}\mathbb {F} _{q})\\x_{qu_{i}+v_{u_{i}}}&=(u_{i},v_{u_{i}})\end{aligned}}$

$\mathbb {F} _{q}$ में गणनाएँ परिमित क्षेत्रों के लिए सार्वजनिक रूप से उपलब्ध सॉफ्टवेयर पुस्तकालयों के साथ कार्यान्वित किया जा सकता है, जब $q$ प्रमुख घात है। जब एक अभाज्य संख्या $q$ है, फिर इसमें संगणना $\mathbb {F} _{q}$ मापांक अंकगणित को सरल करें, अर्थात, $v_{u_{i}}=(\sum _{l=1}^{c-1}a^{l}i_{l}+b)~{\text{mod}}~q$ है। कैसे एक समुच्चय $\ell$ उत्पन्न करने का एक उदाहरण, $a=1,b=0,c=2$ नीचे दी गई तालिका में प्रदर्शित किया गया है, जबकि प्रतिरूपों का संबंधित चयन ऊपर की आकृति में दर्शाया गया है।

एक समुच्चय $\ell$ की गणना पीपी के साथ $c=3$ , $q=3$ , $a=1$ , $b=0$ का उपयोग करना
$i_{1}$	$i_{2}$	$u_{i}$	$v_{u_{i}}$	$qu_{i}+v_{u_{i}}$	$\ell$
$0$	$0$	$0$	$0$	$0$	$x_{0}$
$0$	$1$	$1$	$1$	$4$	$x_{4}$
$0$	$2$	$2$	$2$	$8$	$x_{8}$
$1$	$0$	$3$	$1$	$10$	$x_{10}$
$1$	$1$	$4$	$2$	$14$	$x_{14}$
$1$	$2$	$5$	$0$	$15$	$x_{15}$
$2$	$0$	$6$	$2$	$20$	$x_{20}$
$2$	$1$	$7$	$0$	$21$	$x_{21}$
$2$	$2$	$8$	$1$	$25$	$x_{25}$

यह पद्धति $q(c-1)(d+1)$ सटीक पहचान करने के लिए परीक्षण $d$ सकारात्मक के मध्य $n=q^{c}$ प्रतिरूप का उपयोग करती है। इसके कारण से पीपी बड़े प्रतिरूप आकारों के लिए विशेष रूप से प्रभावी है, क्योंकि परीक्षणों की संख्या केवल रैखिक रूप से बढ़ती है, जबकि प्रतिरूप $c$ इस मापदण्ड के साथ तीव्रता से बढ़ते हैं। हालांकि पीपी छोटे प्रतिरूप आकार के लिए भी प्रभावी हो सकता है।^[24]

उदाहरण अनुप्रयोग

समूह परीक्षण के सिद्धांत की व्यापकता इसे कई विविध अनुप्रयोगों के लिए ऋण प्रदान करती है, जिसमें प्रतिरूप पृथक्करण, विद्युत शॉर्ट का पता लगाना;^[3]उच्च गति परिकलक संजाल;^[25] चिकित्सा परीक्षा, मात्रा खोज, सांख्यिकी;^[18]यंत्र अधिगम, डीएनए अनुक्रमण;^[26] कूटलेखन;^[27]^[28] और विधि न्यायालयिक आंकड़े सम्मिलित है।^[29] यह खंड इन अनुप्रयोगों के एक छोटे से चयन का एक संक्षिप्त अवलोकन प्रदान करता है।

बहु-अभिगम माध्यम

Error creating thumbnail:

एक सफल संदेश और एक संदेश संघट्टन वाले बहु-अभिगम माध्यम का एक उदाहरण।

एक बहु-अभिगम विधि एक संचार माध्यम है जो कई उपयोगकर्ताओं को एक साथ जोड़ता है। प्रत्येक उपयोगकर्ता माध्यम पर सुन सकता है और प्रसारित कर सकता है, परन्तु यदि एक से अधिक उपयोगकर्ता एक ही समय में प्रसारित करते हैं, तो संकेत टकराते हैं और अस्पष्ट कोलाहलयुक्त में कम हो जाते हैं। विभिन्न वास्तविक दुनिया के अनुप्रयोगों, विशेष रूप से तार रहित परिकलक संजाल और दूरभाष संजाल के लिए बहु-अभिगम माध्यम महत्वपूर्ण हैं।^[30]

बहु-अभिगम माध्यमों के साथ एक प्रमुख समस्या यह है कि उपयोगकर्ताओं को संचरण समय कैसे आवंटित किया जाए ताकि उनके संदेश आपस में न टकराएं। एक सरल तरीका यह है कि प्रत्येक उपयोगकर्ता को अपना स्वयं का समय प्रखाँच दिया जाए, जिसमें आवश्यकता पड़ने पर $n$ प्रखाँच प्रसारित किया जा सके (इसे समय विभाजन बहुसंकेतन, या टीडीएम कहा जाता है)। हालांकि, यह बहुत ही अक्षम है, क्योंकि यह उन उपयोगकर्ताओं को संचरण प्रखाँच प्रदान करेगा जिनके पास संदेश नहीं हो सकता है और सामान्यतः यह माना जाता है कि केवल कुछ उपयोगकर्ता ही किसी भी समय संचारित करना चाहेंगे। दिया गया समय - अन्यथा एक बहु-अभिगम माध्यम पहले स्थान पर व्यावहारिक नहीं है।

समूह परीक्षण के संदर्भ में, इस समस्या का समाधान सामान्यतः समय को 'युगों' में निम्न प्रकार से विभाजित करके किया जाता है।^[3]एक उपयोगकर्ता को 'सक्रिय' कहा जाता है यदि उसके पास युग की प्रारंभ में कोई संदेश है (यदि एक युग के पर्यंत एक संदेश उत्पन्न होता है, तो उपयोगकर्ता केवल अगले एक की प्रारंभ में सक्रिय हो जाता है)। एक युग समाप्त हो जाता है जब प्रत्येक सक्रिय उपयोगकर्ता ने अपना संदेश सफलतापूर्वक प्रेषित कर दिया हो। समस्या यह है कि किसी दिए गए युग में सभी सक्रिय उपयोगकर्ताओं को ढूंढना है और उनके लिए संचारित करने के लिए एक समय निर्धारित करना है (यदि वे पूर्व से ही सफलतापूर्वक ऐसा नहीं कर पाए हैं)। यहां, उपयोगकर्ताओं के एक समुच्चय पर एक परीक्षण उन उपयोगकर्ताओं से सुमेलन है जो संचरण का प्रयास कर रहे हैं। परीक्षण के परिणाम उन उपयोगकर्ताओं की संख्या हैं जिन्होंने $0,1,$ और $2^{+}$ संचारित करने का प्रयास किया, क्रमशः कोई सक्रिय उपयोगकर्ता नहीं है, वास्तव में एक सक्रिय उपयोगकर्ता (संदेश सफल) या एक से अधिक सक्रिय उपयोगकर्ता (संदेश संघट्टन) के अनुरूप है। इसलिए, परिणामों $\{0,1,2^{+}\}$ के साथ अनुकूली समूह परीक्षण कलन विधि का उपयोग करना है, यह निर्धारित किया जा सकता है कि कौन से उपयोगकर्ता युग में प्रसारित करना चाहते हैं। फिर, कोई भी उपयोगकर्ता जिसने अभी तक एक सफल प्रसारण नहीं किया है, अब निष्क्रिय उपयोगकर्ताओं को समय व्यर्थ किए बिना, संचारित करने के लिए एक प्रखाँच सौंपा जा सकता है।

यंत्र अधिगम और संकुचित संवेदन

यंत्र अधिगम परिकलक विज्ञान का एक क्षेत्र है जिसमें डीएनए वर्गीकरण, कपट का पता लगाने और लक्षित विज्ञापन जैसे कई सॉफ्टवेयर अनुप्रयोग हैं। यंत्र अधिगम के मुख्य उपक्षेत्रों में से एक 'उदाहरणों द्वारा सीखना' समस्या है, जहाँ प्रकार्य कुछ विशिष्ट बिंदुओं पर इसके मान दिए जाने पर कुछ अज्ञात फलन का अनुमान लगाना है।^[3]जैसा कि इस खंड में रेखांकित किया गया है, इस प्रकार्य सीखने की समस्या को समूह-परीक्षण दृष्टिकोण से हल किया जा सकता है।

समस्या के एक साधारण संस्करण में, कुछ अज्ञात फलन, $f:\{0,1\}^{N}\to \{0,1\}$ है, जहाँ $f({\textbf {x}})={\textbf {a}}\cdot {\textbf {x}}$ , और ${\textbf {a}}\in \{0,1\}^{N}$ है (तार्किक अंकगणित का उपयोग करना: जोड़ तार्किक है या और गुणा तार्किक है)। यहाँ ${\textbf {a}}$ ' $d$ विरल' है, जिसका अर्थ है कि अधिकतम $d\ll N$ की प्रविष्टियाँ $1$ हैं। इसका उद्देश्य एक सन्निकटन $f$ का उपयोग करते हुए $t$ बिंदु मूल्यांकनका निर्माण करना है, जहां $t$ जितना संभव हो उतना छोटा है।^[4](यथार्थत:, $f$ शून्य-त्रुटि कलन विधि से मेल खाती है, जबकि $f$ कलन विधि द्वारा अनुमानित है जिसमें त्रुटि की गैर-शून्य संभाव्यता है)।

इस समस्या में पुनरुत्थान $f$ खोजने के समान ${\textbf {a}}$ है। इसके अतिरिक्त, $f({\textbf {p}})=1$ यदि और केवल यदि वहाँ कुछ सूचकांक $n$ है, जहाँ ${\textbf {a}}_{n}={\textbf {p}}_{n}=1$ हैं। इस प्रकार यह समस्या समूह-परीक्षण समस्या $d$ दोषपूर्ण और $n$ कुल वस्तु के समान है। ${\textbf {a}}$ की प्रविष्टियाँ वे वस्तुएँ हैं, जो दोषपूर्ण हैं, यदि वे $1$ , ${\textbf {p}}$ एक परीक्षण निर्दिष्ट करते है और एक परीक्षण सकारात्मक है यदि और केवल यदि $f({\textbf {p}})=1$ है।^[4]

वास्तव में, प्रायः उन फलनों में रुचि होगी जो अधिक जटिल, जैसे $f:\mathbb {C} ^{N}\to \mathbb {C}$ हैं,, फिर जहाँ $f({\textbf {x}})={\textbf {a}}\cdot {\textbf {x}}$ है। संकुचित संवेदन, जो समूह परीक्षण से निकटता से संबंधित है, इस समस्या को हल करने के लिए उपयोग किया जा सकता है।^[4]

संकुचित संवेदन में, लक्ष्य एक संकेत ${\textbf {v}}\in \mathbb {C} ^{N}$ को कई माप लेकर पुनर्निर्माण करना है। इन मापों को अदिश गुणनफल ${\textbf {v}}$ लेने के रूप में एक चयनित सदिश के साथ तैयार किया गया है।^{[lower-alpha 8]} उद्देश्य कम संख्या में मापन का उपयोग करना है, हालांकि यह सामान्यतः तब तक संभव नहीं है जब तक कि संकेत के विषय में कुछ अनुमान न लगाया जाए। ऐसी ही एक धारणा (जो सामान्य है^[33]^[34]) यह है कि प्रविष्टियों की केवल एक छोटी संख्या ${\textbf {v}}$ महत्वपूर्ण हैं, जिसका अर्थ है कि उनके पास एक बड़ा परिमाण है। चूंकि माप के अदिश गुणनफल ${\textbf {v}}$ हैं, समीकरण $M{\textbf {v}}={\textbf {q}}$ धारण करता है, जहाँ $M$ एक $t\times N$ आव्यूह है, जो चयनित माप के समुच्चय का वर्णन करता है और माप $\mathbf {q}$ परिणामों का समुच्चय है। इस निर्माण से पता चलता है कि संकुचित संवेदन एक तरह का 'निरंतर' समूह परीक्षण है।

संकुचित संवेदन में प्राथमिक कठिनाई यह पहचानना है कि कौन सी प्रविष्टियाँ महत्वपूर्ण हैं।^[33]एक बार यह हो जाने के पश्चात, प्रविष्टियों के वास्तविक मानो का अनुमान लगाने के लिए कई विधियाँ हैं।^[35] समूह परीक्षण के एक सरल अनुप्रयोग के साथ पहचान के इस कार्य तक पहुँचा जा सकता है। यहां एक समूह परीक्षण एक सम्मिश्र संख्या उत्पन्न करता है: परीक्षण की जाने वाली प्रविष्टियों का योग है। एक परीक्षण के परिणाम को सकारात्मक कहा जाता है यदि यह एक बड़े परिमाण के साथ एक सम्मिश्र संख्याओं का उत्पादन करता है, जो यह मानते हुए कि महत्वपूर्ण प्रविष्टियाँ विरल हैं, यह दर्शाता है कि परीक्षण में कम-से-कम एक महत्वपूर्ण प्रविष्टि निहित है।

इस प्रकार के संयोजी खोज कलन विधि के लिए स्पष्ट नियतात्मक निर्माण हैं, जिनके लिए $d2^{(\log _{2}\log _{2}N)^{O(1)}}$ की माप आवश्यकता होती है।^[36] हालांकि, समूह-परीक्षण के साथ, ये उप-इष्टतम हैं और यादृच्छिक निर्माण (जैसे सीओएमपी) को प्रायः $f$ उप-रैखिक रूप से $N$ पुनः प्राप्त किया जा सकता हैं।^[35]

कोविड-19 परीक्षण के लिए बहुरूपी जाँच प्रारुप

2020 में कोविड-19 के प्रकोप जैसी महामारी के पर्यंत, विषाणु का पता लगाने वाले परीक्षण कभी-कभी गैर-अनुकूली समूह परीक्षण प्रारूपों का उपयोग करके चलाए जाते हैं।^[37]^[38] ^[39] एक उदाहरण ओरिगेमी जाँच परियोजना द्वारा प्रदान किया गया था जिसने प्रयोगशाला मानक 96 अनुकूल पट्टिका पर चलने के लिए मुक्त स्रोत समूह परीक्षण प्रारुप जारी किया था।^[40]

Error creating thumbnail:

समूह परीक्षण प्रारुप के लिए ओरिगामी जाँच पत्र आधार पट्ट।

एक प्रयोगशाला अवस्थापन में, समूह परीक्षण की एक चुनौती यह है कि मिश्रण का निर्माण समय लेने वाला हो सकता है और हस्त से सही तरीके से करना कठिन हो सकता है। परीक्षण स्रोत में रोगी के नमूने को कैसे आवंटित किया जाए, इस पर प्रविधिज्ञ को मार्गदर्शन करने के लिए पत्र आधार पट्ट प्रदान करके ओरिगेमी जाँच ने इस निर्माण समस्या के लिए समाधान प्रदान किया।^[41]

सबसे बड़े समूह परीक्षण प्रारुप (XL3) का उपयोग करके 94 जाँच स्रोतों में 1120 रोगी नमूनों का परीक्षण करना संभव था। यदि वास्तविक सकारात्मक दर काफी कम थी, तो किसी अतिरिक्त परीक्षण की आवश्यकता नहीं थी।

न्यायालयिक आंकड़े

आंकड़े न्यायालयिक एक अपराध के अंकीय साक्ष्य को संकलित करने के तरीकों को खोजने के लिए समर्पित क्षेत्र है। इस तरह के अपराधों में सामान्यतः एक विरोधी सम्मिलित होता है जो किसी पीड़ित के आंकड़े, दस्तावेजों या आंकड़ाकोष को संशोधित करता है, उदाहरण के साथ कर अभिलेख में परिवर्तन, एक वायरस अपनी उपस्थिति को गोपनीय है, या एक पहचान तस्कर व्यक्तिगत आंकड़े को संशोधित करता है।^[29]

आंकड़े न्यायालयिक में एक सामान्य उपकरण एकदिशिक गूढ़ालेखी द्रुतान्वेषण है। यह एक ऐसा प्रकार्य है जो आंकड़े लेता है और एक कठिन प्रतिलोम प्रक्रिया के माध्यम से, एक अद्वितीय संख्या उत्पन्न करता है जिसे द्रुतान्वेषण कहा जाता है।^{[lower-alpha 9]} हैश, जो प्रायः आंकड़े की तुलना में बहुत कम होते हैं, हमें यह जाँचने की अनुमति देते हैं कि क्या सूचना की पूर्ण प्रतियों को अपव्ययी ढंग से आंकड़े को परिवर्तित कर दिया गया है: वर्तमान आंकड़े के द्रुतान्वेषण की तुलना पूर्व द्रुतान्वेषण से की जा सकती है, यह निर्धारित करने के लिए कि क्या कोई है परिवर्तन हुए हैं। इस पद्धति की एक दुर्भाग्यपूर्ण विशेषता यह है कि, हालांकि यह बताना सरल है कि क्या आंकड़े संशोधित किया गया है, यह निर्धारित करने का कोई तरीका नहीं है कि कैसे: अर्थात, आंकड़े के किस भाग में परिवर्तन आया है, यह पुनर्प्राप्त करना असंभव है।^[29]

इस सीमा के आसपास जाने का एक तरीका अधिक हैश को संग्रहित करना है - अब आंकड़े संरचना के उपसमुच्चय का - जहां आक्षेप हुआ है, उसे कम करने के लिए है। हालांकि, एक सहज दृष्टिकोण के साथ आक्षेप के सटीक स्थान का पता लगाने के लिए, संरचना में प्रत्येक आंकड़े के लिए एक द्रुतान्वेषण को संग्रहीत करने की आवश्यकता होगी, जो पहले स्थान पर हैश के बिंदु को पराजित करेगा। (कोई भी आंकड़े की एक नियमित प्रति संग्रहीत कर सकता है)। समूह परीक्षण का उपयोग नाटकीय रूप से संग्रहित किए जाने वाले हैश की संख्या को कम करने के लिए किया जा सकता है। एक परीक्षण संग्रहीत और वर्तमान हैश के मध्य तुलना बन जाता है, जो बेमेल होने पर सकारात्मक होता है। यह इंगित करता है कि कम-से-कम एक संपादित आंकड़े (जो इस प्रतिरूप में दोष के रूप में लिया गया है) उस समूह में निहित है जिसने वर्तमान द्रुतान्वेषण उत्पन्न किया है।^[29]

वास्तव में, आवश्यक हैश की मात्रा इतनी कम है कि वे परीक्षण आव्यूह के साथ-साथ आंकड़े के संगठनात्मक संरचना के भीतर भी संग्रहीत किए जा सकते हैं। इसका अर्थ यह है कि जहां तक स्मृति का संबंध है, परीक्षण 'मुक्त करने के लिए' किया जा सकता है। (यह सर्व कुंजी/पारणशब्द के अपवाद के साथ सत्य है जिसका उपयोग द्रुतान्वेषण फलन को गुप्त रूप से निर्धारित करने के लिए किया जाता है)।^[29]

↑ The original problem that Dorfman studied was of this nature (although he did not account for this), since in practice, only a certain number of blood sera could be pooled before the testing procedure became unreliable. This was the main reason that Dorfman’s procedure was not applied at the time.^[3]
↑ However, as is often the case in mathematics, group testing has been subsequently re-invented multiple times since then, often in the context of applications. For example, Hayes independently came up with the idea to query groups of users in the context of multiaccess communication protocols in 1978.^[9]
↑ This is sometimes referred to as the Hu-Hwang-Wang conjecture.
↑ The number of tests, $t$ , must scale as $t=O\left(d^{2}\log _{d}n\right)$ for deterministic designs, compared to $t=O(d\log _{2}n)$ for designs that allow arbitrarily small probabilities of error (as $d\to \infty$ and $n\to \infty$ ).^[4]
↑ One must be careful to distinguish between when a test reports a false result and when the group-testing procedure fails as a whole. It is both possible to make an error with no incorrect tests and to not make an error with some incorrect tests. Most modern combinatorial algorithms have some non-zero probability of error (even with no erroneous tests), since this significantly decreases the number of tests needed.
↑ In fact it is possible to do much better. For example, Li's $s$ -stage algorithm gives an explicit construction were $t\leq {\frac {e}{\log _{2}e}}d\log _{2}{(n/d)}$ .
↑ Alternatively $\mathbf {y}$ can be defined by the equation $\mathbf {y} :=M\mathbf {x}$ , where multiplication is logical AND ( $\wedge$ ) and addition is logical OR ( $\vee$ ). Here, $\mathbf {y}$ will have a $1$ in position $i$ if and only if $(M)_{i,j}$ and $\mathbf {x} _{j}$ are both $1$ for any $j$ . That is, if and only if at least one defective item was included in the $i{\textrm {-th}}$ test.
↑ This kind of measurement comes up in many applications. For example, certain kinds of digital camera^[31] or MRI machines,^[32] where time constraints require that only a small number of measurements are taken.
↑ More formally hashes have a property called collision resistance, which is that the likelihood of the same hash resulting from different inputs is very low for data of an appropriate size. In practice, the chance that two different inputs might produce the same hash is often ignored.

संदर्भ

उद्धरण

↑ Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC, p. 574, Section 46: Pooling Designs, ISBN 978-1-58488-506-1
↑ ^2.0 ^2.1 ^2.2 Dorfman, Robert (December 1943), "The Detection of Defective Members of Large Populations", The Annals of Mathematical Statistics, 14 (4): 436–440, doi:10.1214/aoms/1177731363, JSTOR 2235930
↑ ^3.00 ^3.01 ^3.02 ^3.03 ^3.04 ^3.05 ^3.06 ^3.07 ^3.08 ^3.09 ^3.10 ^3.11 ^3.12 ^3.13 ^3.14 ^3.15 ^3.16 ^3.17 ^3.18 ^3.19 ^3.20 ^3.21 ^3.22 Ding-Zhu, Du; Hwang, Frank K. (1993). Combinatorial group testing and its applications. Singapore: World Scientific. ISBN 978-9810212933.
↑ ^4.0 ^4.1 ^4.2 ^4.3 ^4.4 ^4.5 ^4.6 ^4.7 ^4.8 Atia, George Kamal; Saligrama, Venkatesh (March 2012). "Boolean compressed sensing and noisy group testing". IEEE Transactions on Information Theory. 58 (3): 1880–1901. arXiv:0907.1061. doi:10.1109/TIT.2011.2178156. S2CID 8946216.
↑ ^5.0 ^5.1 ^5.2 ^5.3 ^5.4 ^5.5 ^5.6 ^5.7 ^5.8 ^5.9 Chun Lam Chan; Pak Hou Che; Jaggi, Sidharth; Saligrama, Venkatesh (1 September 2011), "2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton)", 49th Annual Allerton Conference on Communication, Control, and Computing, pp. 1832–1839, arXiv:1107.4540, doi:10.1109/Allerton.2011.6120391, ISBN 978-1-4577-1817-5, S2CID 8408114
↑ Hung, M.; Swallow, William H. (March 1999). "अनुपात के अनुमान में समूह परीक्षण की मजबूती". Biometrics. 55 (1): 231–237. doi:10.1111/j.0006-341X.1999.00231.x. PMID 11318160. S2CID 23389365.
↑ Chen, Hong-Bin; Fu, Hung-Lin (April 2009). "Nonadaptive algorithms for threshold group testing". Discrete Applied Mathematics. 157 (7): 1581–1585. doi:10.1016/j.dam.2008.06.003.
↑ De Bonis, Annalisa (20 July 2007). "New combinatorial structures with applications to efficient group testing with inhibitors". Journal of Combinatorial Optimization. 15 (1): 77–94. doi:10.1007/s10878-007-9085-1. S2CID 207188798.
↑ Hayes, J. (August 1978). "An adaptive technique for local distribution". IEEE Transactions on Communications. 26 (8): 1178–1186. doi:10.1109/TCOM.1978.1094204.
↑ Samuels, Stephen (1978). "The Exact Solution to the Two-Stage Group-Testing Problem". Technometrics. 20 (4): 497–500. doi:10.1080/00401706.1978.10489706.
↑ Sterrett, Andrew (December 1957). "On the detection of defective members of large populations". The Annals of Mathematical Statistics. 28 (4): 1033–1036. doi:10.1214/aoms/1177706807.
↑ Sobel, Milton; Groll, Phyllis A. (September 1959). "Group testing to eliminate efficiently all defectives in a binomial sample". Bell System Technical Journal. 38 (5): 1179–1252. doi:10.1002/j.1538-7305.1959.tb03914.x.
↑ Ungar, Peter (February 1960). "Cutoff points in group testing". Communications on Pure and Applied Mathematics. 13 (1): 49–54. doi:10.1002/cpa.3160130105.
↑ Li, Chou Hsiung (June 1962). "A sequential method for screening experimental variables". Journal of the American Statistical Association. 57 (298): 455–477. doi:10.1080/01621459.1962.10480672.
↑ Katona, Gyula O.H. (1973). "A survey of combinatorial theory". Combinatorial Search Problems. North-Holland, Amsterdam: 285–308.
↑ ^16.0 ^16.1 ^16.2 ^16.3 Hwang, Frank K. (September 1972). "A method for detecting all defective members in a population by group testing". Journal of the American Statistical Association. 67 (339): 605–608. doi:10.2307/2284447. JSTOR 2284447.
↑ Allemann, Andreas (2013). "An efficient algorithm for combinatorial group testing". Information Theory, Combinatorics, and Search Theory. Lecture Notes in Computer Science. 7777: 569–596. doi:10.1007/978-3-642-36899-8_29. ISBN 978-3-642-36898-1.
↑ ^18.0 ^18.1 Hu, M. C.; Hwang, F. K.; Wang, Ju Kwei (June 1981). "A Boundary Problem for Group Testing". SIAM Journal on Algebraic and Discrete Methods. 2 (2): 81–87. doi:10.1137/0602011.
↑ Leu, Ming-Guang (28 October 2008). "A note on the Hu–Hwang–Wang conjecture for group testing". The ANZIAM Journal. 49 (4): 561. doi:10.1017/S1446181108000175.
↑ Riccio, Laura; Colbourn, Charles J. (1 January 2000). "Sharper bounds in adaptive group testing". Taiwanese Journal of Mathematics. 4 (4): 669–673. doi:10.11650/twjm/1500407300.
↑ ^21.0 ^21.1 ^21.2 ^21.3 Aldridge, Matthew; Baldassini, Leonardo; Johnson, Oliver (June 2014). "Group Testing Algorithms: Bounds and Simulations". IEEE Transactions on Information Theory. 60 (6): 3671–3687. arXiv:1306.6438. doi:10.1109/TIT.2014.2314472. S2CID 8885619.
↑ Baldassini, L.; Johnson, O.; Aldridge, M. (1 July 2013), "2013 IEEE International Symposium on Information Theory", IEEE International Symposium on Information Theory, pp. 2676–2680, arXiv:1301.7023, CiteSeerX 10.1.1.768.8924, doi:10.1109/ISIT.2013.6620712, ISBN 978-1-4799-0446-4, S2CID 9987210
↑ Sobel, Milton; Elashoff, R. M. (1975). "एक नए लक्ष्य, अनुमान के साथ समूह परीक्षण". Biometrika. 62 (1): 181–193. doi:10.1093/biomet/62.1.181. hdl:11299/199154.
↑ ^24.0 ^24.1 Brust, D.; Brust, J. J. (January 2023). "Effective matrix designs for COVID-19 group testing". BMC Bioinformatics. 24 (26): 26. doi:10.1186/s12859-023-05145-y. PMC 9872308. PMID 36694117.
↑ Bar-Noy, A.; Hwang, F. K.; Kessler, I.; Kutten, S. (1 May 1992). A new competitive algorithm for group testing. pp. 786–793. doi:10.1109/INFCOM.1992.263516. ISBN 978-0-7803-0602-8. {{cite book}}: |journal= ignored (help)
↑ Damaschke, Peter (2000). "Adaptive versus nonadaptive attribute-efficient learning". Machine Learning. 41 (2): 197–215. doi:10.1023/A:1007616604496.
↑ Stinson, D. R.; van Trung, Tran; Wei, R (May 2000). "Secure frameproof codes, key distribution patterns, group testing algorithms and related structures". Journal of Statistical Planning and Inference. 86 (2): 595–617. CiteSeerX 10.1.1.54.6212. doi:10.1016/S0378-3758(99)00131-7.
↑ Colbourn, C. J.; Dinitz, J. H.; Stinson, D. R. (1999). "Communications, Cryptography, and Networking". Surveys in Combinatorics. 3 (267): 37–41. doi:10.1007/BF01609873. S2CID 10128581.
↑ ^29.0 ^29.1 ^29.2 ^29.3 ^29.4 Goodrich, Michael T.; Atallah, Mikhail J.; Tamassia, Roberto (7 June 2005). Indexing information for data forensics. pp. 206–221. CiteSeerX 10.1.1.158.6036. doi:10.1007/11496137_15. ISBN 978-3-540-26223-7. {{cite book}}: |journal= ignored (help)
↑ Chlebus, B. S. (2001). "Randomized communication in radio networks". In: Pardalos, P. M.; Rajasekaran, S.; Reif, J.; Rolim, J. D. P. (Eds.), Handbook of Randomized Computing, Vol. I, p.401–456. Kluwer Academic Publishers, Dordrecht.
↑ Takhar, D.; Laska, J. N.; Wakin, M. B.; Duarte, M. F.; Baron, D.; Sarvotham, S.; Kelly, K. F.; Baraniuk, R. G. (February 2006). "A new compressive imaging camera architecture using optical-domain compression". Electronic Imaging. Computational Imaging IV. 6065: 606509–606509–10. Bibcode:2006SPIE.6065...43T. CiteSeerX 10.1.1.114.7872. doi:10.1117/12.659602. S2CID 7513433.
↑ Candès, E. J. (2014). "Mathematics of sparsity (and a few other things)". Proceedings of the International Congress of Mathematicians. Seoul, South Korea.
↑ ^33.0 ^33.1 Gilbert, A. C.; Iwen, M. A.; Strauss, M. J. (October 2008). "Group testing and sparse signal recovery". 42nd Asilomar Conference on Signals, Systems and Computers: 1059–1063. Institute of Electrical and Electronics Engineers.
↑ Wright, S. J.; Nowak, R. D.; Figueiredo, M. A. T. (July 2009). "Sparse Reconstruction by Separable Approximation". IEEE Transactions on Signal Processing. 57 (7): 2479–2493. Bibcode:2009ITSP...57.2479W. CiteSeerX 10.1.1.142.749. doi:10.1109/TSP.2009.2016892. S2CID 7399917.
↑ ^35.0 ^35.1 Berinde, R.; Gilbert, A. C.; Indyk, P.; Karloff, H.; Strauss, M. J. (September 2008). Combining geometry and combinatorics: A unified approach to sparse signal recovery. pp. 798–805. arXiv:0804.4666. doi:10.1109/ALLERTON.2008.4797639. ISBN 978-1-4244-2925-7. S2CID 8301134. {{cite book}}: |journal= ignored (help)
↑ Indyk, Piotr (1 January 2008). "Explicit Constructions for Compressed Sensing of Sparse Signals". Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms: 30–33.
↑ Austin, David. "AMS Feature Column — Pooling strategies for COVID-19 testing". American Mathematical Society (in English). Retrieved 2020-10-03.
↑ Prasanna, Dheeraj. "टेपेस्ट्री पूलिंग". tapestry-pooling.herokuapp.com (in English). Retrieved 2020-10-03.
↑ Chiani, M.; Liva, G.; Paolini, E. (February 2022), "Identification-detection group testing protocols for COVID-19 at high prevalence", Scientific Reports, Springer Nature, 12 (1): 3250, doi:10.1038/s41598-022-07205-4, PMC 8885674, PMID 35228579, S2CID 233387831
↑ "ओरिगेमी एसेस". Origami Assays. April 2, 2020. Retrieved April 7, 2020.
↑ "ओरिगेमी एसेस". Origami Assays. April 2, 2020. Retrieved April 7, 2020.

सामान्य संदर्भ

Ding-Zhu, Du; Hwang, Frank K. (1993). मिश्रित समूह परीक्षण और इसके अनुप्रयोग. Singapore: World Scientific. ISBN 978-9810212933.
एरर करेक्टिंग कोड्स पर अत्रि रुद्र का कोर्स: कॉम्बिनेटरिक्स, कलन विधि, और एप्लिकेशन (स्प्रिंग 2007), व्याख्यान 7।
एरर करेक्टिंग कोड्स पर अत्रि रुद्र का कोर्स: कॉम्बिनेटरिक्स, कलन विधि, और एप्लिकेशन (स्प्रिंग 2010), व्याख्यान 10 , 11, कोडिंग-सिद्धांत/spr10/lectures/lect28.pdf 28, 29
डू, डी., और ह्वांग, एफ. (2006)। पूलिंग डिज़ाइन और गैर-अनुकूली समूह परीक्षण। बोस्टन: ट्वेन पब्लिशर्स।
एल्ड्रिज, एम., जॉनसन, ओ. और स्कारलेट, जे. (2019), समूह परीक्षण: एक सूचना सिद्धांत परिप्रेक्ष्य, संचार और सूचना सिद्धांत में नींव और रुझान: वॉल्यूम। 15: संख्या 3-4, पीपी 196-392। doi:10.1561/0100000099
एली पोराट, आमिर रोथ्सचाइल्ड: स्पष्ट गैर-अनुकूली संयोजन समूह परीक्षण योजनाएँ। आईसीएएलपी (1) 2008: 748-759
Kagan, Eugene; Ben-gal, Irad (2014), "A group testing algorithm with online informational learning", IIE Transactions, 46 (2): 164–184, doi:10.1080/0740817X.2013.803639, ISSN 0740-817X, S2CID 18588494

यह भी देखें

संतुलन पहेली

श्रेणी: संयोजन विज्ञान श्रेणी:प्रयोगों का प्रारुप

[7] The original problem that Dorfman studied was of this nature (although he did not account for this), since in practice, only a certain number of blood sera could be pooled before the testing procedure became unreliable. This was the main reason that Dorfman’s procedure was not applied at the time.^[3]

[11] However, as is often the case in mathematics, group testing has been subsequently re-invented multiple times since then, often in the context of applications. For example, Hayes independently came up with the idea to query groups of users in the context of multiaccess communication protocols in 1978.^[9]

[22] This is sometimes referred to as the Hu-Hwang-Wang conjecture.

[24] The number of tests, $t$ , must scale as $t=O\left(d^{2}\log _{d}n\right)$ for deterministic designs, compared to $t=O(d\log _{2}n)$ for designs that allow arbitrarily small probabilities of error (as $d\to \infty$ and $n\to \infty$ ).^[4]

[26] One must be careful to distinguish between when a test reports a false result and when the group-testing procedure fails as a whole. It is both possible to make an error with no incorrect tests and to not make an error with some incorrect tests. Most modern combinatorial algorithms have some non-zero probability of error (even with no erroneous tests), since this significantly decreases the number of tests needed.

[27] In fact it is possible to do much better. For example, Li's $s$ -stage algorithm gives an explicit construction were $t\leq {\frac {e}{\log _{2}e}}d\log _{2}{(n/d)}$ .

[29] Alternatively $\mathbf {y}$ can be defined by the equation $\mathbf {y} :=M\mathbf {x}$ , where multiplication is logical AND ( $\wedge$ ) and addition is logical OR ( $\vee$ ). Here, $\mathbf {y}$ will have a $1$ in position $i$ if and only if $(M)_{i,j}$ and $\mathbf {x} _{j}$ are both $1$ for any $j$ . That is, if and only if at least one defective item was included in the $i{\textrm {-th}}$ test.

[40] This kind of measurement comes up in many applications. For example, certain kinds of digital camera^[31] or MRI machines,^[32] where time constraints require that only a small number of measurements are taken.

[50] More formally hashes have a property called collision resistance, which is that the likelihood of the same hash resulting from different inputs is very low for data of an appropriate size. In practice, the chance that two different inputs might produce the same hash is often ignored.

[1] Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC, p. 574, Section 46: Pooling Designs, ISBN 978-1-58488-506-1

[Dorfman-2] 2.0 ^2.1 ^2.2 Dorfman, Robert (December 1943), "The Detection of Defective Members of Large Populations", The Annals of Mathematical Statistics, 14 (4): 436–440, doi:10.1214/aoms/1177731363, JSTOR 2235930

[book-3] 3.00 ^3.01 ^3.02 ^3.03 ^3.04 ^3.05 ^3.06 ^3.07 ^3.08 ^3.09 ^3.10 ^3.11 ^3.12 ^3.13 ^3.14 ^3.15 ^3.16 ^3.17 ^3.18 ^3.19 ^3.20 ^3.21 ^3.22 Ding-Zhu, Du; Hwang, Frank K. (1993). Combinatorial group testing and its applications. Singapore: World Scientific. ISBN 978-9810212933.

[compressedSensing-4] 4.0 ^4.1 ^4.2 ^4.3 ^4.4 ^4.5 ^4.6 ^4.7 ^4.8 Atia, George Kamal; Saligrama, Venkatesh (March 2012). "Boolean compressed sensing and noisy group testing". IEEE Transactions on Information Theory. 58 (3): 1880–1901. arXiv:0907.1061. doi:10.1109/TIT.2011.2178156. S2CID 8946216.

[comp-5] 5.0 ^5.1 ^5.2 ^5.3 ^5.4 ^5.5 ^5.6 ^5.7 ^5.8 ^5.9 Chun Lam Chan; Pak Hou Che; Jaggi, Sidharth; Saligrama, Venkatesh (1 September 2011), "2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton)", 49th Annual Allerton Conference on Communication, Control, and Computing, pp. 1832–1839, arXiv:1107.4540, doi:10.1109/Allerton.2011.6120391, ISBN 978-1-4577-1817-5, S2CID 8408114

[6] Hung, M.; Swallow, William H. (March 1999). "अनुपात के अनुमान में समूह परीक्षण की मजबूती". Biometrics. 55 (1): 231–237. doi:10.1111/j.0006-341X.1999.00231.x. PMID 11318160. S2CID 23389365.

[8] Chen, Hong-Bin; Fu, Hung-Lin (April 2009). "Nonadaptive algorithms for threshold group testing". Discrete Applied Mathematics. 157 (7): 1581–1585. doi:10.1016/j.dam.2008.06.003.

[9] De Bonis, Annalisa (20 July 2007). "New combinatorial structures with applications to efficient group testing with inhibitors". Journal of Combinatorial Optimization. 15 (1): 77–94. doi:10.1007/s10878-007-9085-1. S2CID 207188798.

[Hayes-10] Hayes, J. (August 1978). "An adaptive technique for local distribution". IEEE Transactions on Communications. 26 (8): 1178–1186. doi:10.1109/TCOM.1978.1094204.

[Samuels-12] Samuels, Stephen (1978). "The Exact Solution to the Two-Stage Group-Testing Problem". Technometrics. 20 (4): 497–500. doi:10.1080/00401706.1978.10489706.

[Sterrett-13] Sterrett, Andrew (December 1957). "On the detection of defective members of large populations". The Annals of Mathematical Statistics. 28 (4): 1033–1036. doi:10.1214/aoms/1177706807.

[groll-14] Sobel, Milton; Groll, Phyllis A. (September 1959). "Group testing to eliminate efficiently all defectives in a binomial sample". Bell System Technical Journal. 38 (5): 1179–1252. doi:10.1002/j.1538-7305.1959.tb03914.x.

[Ungar-15] Ungar, Peter (February 1960). "Cutoff points in group testing". Communications on Pure and Applied Mathematics. 13 (1): 49–54. doi:10.1002/cpa.3160130105.

[li-16] Li, Chou Hsiung (June 1962). "A sequential method for screening experimental variables". Journal of the American Statistical Association. 57 (298): 455–477. doi:10.1080/01621459.1962.10480672.

[Katona-17] Katona, Gyula O.H. (1973). "A survey of combinatorial theory". Combinatorial Search Problems. North-Holland, Amsterdam: 285–308.

[Hwang-18] 16.0 ^16.1 ^16.2 ^16.3 Hwang, Frank K. (September 1972). "A method for detecting all defective members in a population by group testing". Journal of the American Statistical Association. 67 (339): 605–608. doi:10.2307/2284447. JSTOR 2284447.

[Allemann-19] Allemann, Andreas (2013). "An efficient algorithm for combinatorial group testing". Information Theory, Combinatorics, and Search Theory. Lecture Notes in Computer Science. 7777: 569–596. doi:10.1007/978-3-642-36899-8_29. ISBN 978-3-642-36898-1.

[huhwangwang-20] 18.0 ^18.1 Hu, M. C.; Hwang, F. K.; Wang, Ju Kwei (June 1981). "A Boundary Problem for Group Testing". SIAM Journal on Algebraic and Discrete Methods. 2 (2): 81–87. doi:10.1137/0602011.

[21] Leu, Ming-Guang (28 October 2008). "A note on the Hu–Hwang–Wang conjecture for group testing". The ANZIAM Journal. 49 (4): 561. doi:10.1017/S1446181108000175.

[Riccio-23] Riccio, Laura; Colbourn, Charles J. (1 January 2000). "Sharper bounds in adaptive group testing". Taiwanese Journal of Mathematics. 4 (4): 669–673. doi:10.11650/twjm/1500407300.

[dd-25] 21.0 ^21.1 ^21.2 ^21.3 Aldridge, Matthew; Baldassini, Leonardo; Johnson, Oliver (June 2014). "Group Testing Algorithms: Bounds and Simulations". IEEE Transactions on Information Theory. 60 (6): 3671–3687. arXiv:1306.6438. doi:10.1109/TIT.2014.2314472. S2CID 8885619.

[Baldassini-28] Baldassini, L.; Johnson, O.; Aldridge, M. (1 July 2013), "2013 IEEE International Symposium on Information Theory", IEEE International Symposium on Information Theory, pp. 2676–2680, arXiv:1301.7023, CiteSeerX 10.1.1.768.8924, doi:10.1109/ISIT.2013.6620712, ISBN 978-1-4799-0446-4, S2CID 9987210

[30] Sobel, Milton; Elashoff, R. M. (1975). "एक नए लक्ष्य, अनुमान के साथ समूह परीक्षण". Biometrika. 62 (1): 181–193. doi:10.1093/biomet/62.1.181. hdl:11299/199154.

[brustbrust-31] 24.0 ^24.1 Brust, D.; Brust, J. J. (January 2023). "Effective matrix designs for COVID-19 group testing". BMC Bioinformatics. 24 (26): 26. doi:10.1186/s12859-023-05145-y. PMC 9872308. PMID 36694117.

[noy-32] Bar-Noy, A.; Hwang, F. K.; Kessler, I.; Kutten, S. (1 May 1992). A new competitive algorithm for group testing. pp. 786–793. doi:10.1109/INFCOM.1992.263516. ISBN 978-0-7803-0602-8. {{cite book}}: |journal= ignored (help)

[learning-33] Damaschke, Peter (2000). "Adaptive versus nonadaptive attribute-efficient learning". Machine Learning. 41 (2): 197–215. doi:10.1023/A:1007616604496.

[keys-34] Stinson, D. R.; van Trung, Tran; Wei, R (May 2000). "Secure frameproof codes, key distribution patterns, group testing algorithms and related structures". Journal of Statistical Planning and Inference. 86 (2): 595–617. CiteSeerX 10.1.1.54.6212. doi:10.1016/S0378-3758(99)00131-7.

[colbourn-35] Colbourn, C. J.; Dinitz, J. H.; Stinson, D. R. (1999). "Communications, Cryptography, and Networking". Surveys in Combinatorics. 3 (267): 37–41. doi:10.1007/BF01609873. S2CID 10128581.

[data-36] 29.0 ^29.1 ^29.2 ^29.3 ^29.4 Goodrich, Michael T.; Atallah, Mikhail J.; Tamassia, Roberto (7 June 2005). Indexing information for data forensics. pp. 206–221. CiteSeerX 10.1.1.158.6036. doi:10.1007/11496137_15. ISBN 978-3-540-26223-7. {{cite book}}: |journal= ignored (help)

[multi-37] Chlebus, B. S. (2001). "Randomized communication in radio networks". In: Pardalos, P. M.; Rajasekaran, S.; Reif, J.; Rolim, J. D. P. (Eds.), Handbook of Randomized Computing, Vol. I, p.401–456. Kluwer Academic Publishers, Dordrecht.

[takhar-38] Takhar, D.; Laska, J. N.; Wakin, M. B.; Duarte, M. F.; Baron, D.; Sarvotham, S.; Kelly, K. F.; Baraniuk, R. G. (February 2006). "A new compressive imaging camera architecture using optical-domain compression". Electronic Imaging. Computational Imaging IV. 6065: 606509–606509–10. Bibcode:2006SPIE.6065...43T. CiteSeerX 10.1.1.114.7872. doi:10.1117/12.659602. S2CID 7513433.

[candes-39] Candès, E. J. (2014). "Mathematics of sparsity (and a few other things)". Proceedings of the International Congress of Mathematicians. Seoul, South Korea.

[gilbert-41] 33.0 ^33.1 Gilbert, A. C.; Iwen, M. A.; Strauss, M. J. (October 2008). "Group testing and sparse signal recovery". 42nd Asilomar Conference on Signals, Systems and Computers: 1059–1063. Institute of Electrical and Electronics Engineers.

[wright-42] Wright, S. J.; Nowak, R. D.; Figueiredo, M. A. T. (July 2009). "Sparse Reconstruction by Separable Approximation". IEEE Transactions on Signal Processing. 57 (7): 2479–2493. Bibcode:2009ITSP...57.2479W. CiteSeerX 10.1.1.142.749. doi:10.1109/TSP.2009.2016892. S2CID 7399917.

[berinde-43] 35.0 ^35.1 Berinde, R.; Gilbert, A. C.; Indyk, P.; Karloff, H.; Strauss, M. J. (September 2008). Combining geometry and combinatorics: A unified approach to sparse signal recovery. pp. 798–805. arXiv:0804.4666. doi:10.1109/ALLERTON.2008.4797639. ISBN 978-1-4244-2925-7. S2CID 8301134. {{cite book}}: |journal= ignored (help)

[poitr-44] Indyk, Piotr (1 January 2008). "Explicit Constructions for Compressed Sensing of Sparse Signals". Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms: 30–33.

[45] Austin, David. "AMS Feature Column — Pooling strategies for COVID-19 testing". American Mathematical Society (in English). Retrieved 2020-10-03.

[46] Prasanna, Dheeraj. "टेपेस्ट्री पूलिंग". tapestry-pooling.herokuapp.com (in English). Retrieved 2020-10-03.

[47] Chiani, M.; Liva, G.; Paolini, E. (February 2022), "Identification-detection group testing protocols for COVID-19 at high prevalence", Scientific Reports, Springer Nature, 12 (1): 3250, doi:10.1038/s41598-022-07205-4, PMC 8885674, PMID 35228579, S2CID 233387831

[48] "ओरिगेमी एसेस". Origami Assays. April 2, 2020. Retrieved April 7, 2020.

[49] "ओरिगेमी एसेस". Origami Assays. April 2, 2020. Retrieved April 7, 2020.

[1]

[2]

[3]

[4]

[5]

[6]

[lower-alpha 1]

[7]

[8]

[lower-alpha 2]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[lower-alpha 3]

[20]

[lower-alpha 4]

[21]

[lower-alpha 5]

[lower-alpha 6]

[22]

[lower-alpha 7]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[lower-alpha 8]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[lower-alpha 9]

[9]

[31]

[32]

@@ Line 666: / Line 666: @@
 श्रेणी:प्रयोगों का प्रारुप
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
-[[Category: Machine Translated Page]]
+[[Category:CS1 English-language sources (en)]]
 [[Category:Created On 01/05/2023]]
-[[Category:Vigyan Ready]]
+[[Category:Good articles]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]

Anonymous

Search