群試檢驗演算法的相關數學模型探討

Abstract

考慮一包含n個待測物，且最多有d個呈陽性的集合。我們的目的是藉由群試設計的概念找出所有呈陽性的待測物。一個群試設計含有多個測試，每個測試都包含兩個以上的待測物。我們探討群試設計的目的是去減少測試的個數和階段數。而在同一個階段裡的測試可同時執行。 我們修改並且分析了一個適用於在已知最多二個陽性物的情況下的二階段群試檢驗演算法。此演算法的測試次數是O(3log n)。

Consider a set of n items which has at most d positive items. Our aim is to find all positive items by using the concept of group testing. A group testing consists of a few tests, each of them containing more than one item. The objective in the study of group testing is to reduce the number of test times and to reduce the number of stages which partition the tests into different time slots.

By group testing, each test contains more than one items in order to reduce the number of test times. And these tests often can be conducted simultaneously. indent We modify and analysis a group testing algorithm, which has 2-stage for the case d=2 and the test number of this algorithm is O(3log n).