臺灣博碩士論文加值系統

　　在傳統的群試理論裡，給定一個群體N，其中有些雜質，一次的測試(群試) 是一個N 的子集合，如果測試中沒有雜質則結果為負性，如果測試中有至少一個雜質則結果為正性，然而我們不能得知是哪個為雜質。
　　群試的問題是一種搜尋方法論的研究，目標是用較少的測試去找出所有的雜質；而最終目標是在最糟的情況使用最少的測試次數。形式上，我們用M(d,n) 表示當群體N 有n個而雜質有d個時的最少的測試次數，而演算法的設計都是要去將M(d,n)最小化。
　　主要而言，有兩種型態的演算法：調整型和非調整型兩種。調整型演算法中的測試設計可依據之前測試的結果，而非調整型演算法則是一次給出全部的測試，因此一般而言，調整型演算法可用較少的測試次數去找出全部的雜質。
　　在這篇論文中，我們主要的研究是用調整型演算法去估計M(d,n)，而我們有一個結果是改良了黃光明老師的演算法，而對於某些(d, n) 的數對，進而縮小與資訊量下界⌈log_2 C(n,d)⌉的差距。

In classical group testing, one is given a population N which contains some defective items inside. A group test (pool) is a test on a subset of N. A test is negative if the testing pool contains no defective items and the test is positive if the pool contains at least one defective item but we don’t know which one.
Group Testing is a search methodology. The goal is to use less tests to find all defectives. Mainly, to minimize the number of tests in worst case situation. Formally, we let M(d,n) denote the minimum number of tests if |N| = n and d is the number of defectives. The algorithms designed are then applying to minimize M(d,n). Two basic algorithms are adaptive and non-adaptive algorithms.
The tests designed in an adaptive algorithm may depend on the outcome of previous tests but in a non-adaptive algorithm all tests are carried out simultaneously. Therefore, in general, an adaptive algorithm takes less tests in determining all the defectives.
In this thesis, our study focuses on estimating M(d,n) by using the adaptive algorithms. As a consequence, we further improve the well-known generalized splitting algorithm by Frank K. Hwang. For some pairs (d,n) we are able to determine M(d; n) and for general pairs (d,n) we can close the gap between the number of tests we need and the information lower bound　⌈log_2 C(n,d))⌉.

Contents
誌謝 . . . . . i
中文摘要 . . . . . ii
Abstract . . . . . iii
Content . . . . . iv
List of Figures . . . . . v
1 Introduction . . . . . 1
1.1 Motivation . . . . . 1
1.2 Basic Notations . . . . . 1
1.3 Preliminaries . . . . . 2
2 Main Results . . . . . 5
2.1 Adaptive algorithm for d = 2, 3 . . . . . 5
2.2 Adaptive algorithm for general cases . . . . . 14
2.3 Upper Bounds of M(d, n) . . . . . 17
2.4 Lower Bounds of M(d, n) . . . . . 18
2.5 Concluding Remark . . . . . 22
Bibliography . . . . . 23

[1] Aigner, M. : Combinatorial Search, John Wiley and Sons (1988).
[2] Bruno, W. J. , Knill, E. , Balding, D. J. , Bruce, D. C. , Doggett, N. A. , Sawhill, W. W. , Stallings, R. L. , Whittaker, C. C. , Torney, D. C. : Efficient pooling designs for library screening, Genomics 26, 21–30 (1995).
[3] Chang, G. J. , Hwang, F. K. : A group testing problem on two disjoint sets, SIAM J. Alg. Disc. Methods 2, 35-38 (1981).
[4] Chang, X. M. , Hwang, F. K. , Weng, J.F. : Group testing with two and three defectives, in Graph Theory and Its Applications: East and West, ed. M. F. Capobianco, M. Guan, K. F. Hsu and T. Tian, The New York Academy of Sciences, New York, 86-96 (1989).
[5] Cheng, M. , Miao, Y. : On Anti-Collusion Codes and Detection Algorithms for Multimedia Fingerprinting. IEEE Trans. Inform, Theory 57(7), 4843-4851 (2011).
[6] Donoho, D. : Compressed sensing. IEEE Trans. Inform. Theory 52(4), 1289-1306 (2006).
[7] Dorfman, R. : The detection of defective members of large populations. Annals of Mathematical Statistics 14, 436-440 (1943).
[8] Du, D. Z. , Hwang, F. K. : Combinational Group Testing and Its Applications, 2nd ed. Would Scientific (2000).
[9] Farach, M. , Kannan S. , Knill, E. , Muthvkrishnan, S. : Group testing problems with sequences in experimental molecular biology, Proc. Compression and Complexity of Sequences, B. Carpentieri et al. (eds). IEEE Press 357-367 (1997).
[10] Hong, E. S. , Ladner, R. E. : Group testing for image compression. IEEE Trans. Image Process. , 11(8), 901-911 (2002).
[11] Hu, M. C. , Hwang, F. K. , Wang, J. K. : A boundary problem for group testing, SIAM J. Alg. Disc. Methods 2, 81-87 (1981).
[12] Hwang, F. K. : “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. (1972).
[13] Thai, M. T. : Group Testing Theory in Network Security, Springer New York (2012).
[14] Torney, D. C. : Sets pooling designs, Ann. Comb. 3, 95-101 (1999).
[15] Weng, J. F. , Hwang, F. K. : An optimal group testing algorithm for k disjoint sets, Oper. Res. Lett. 13, 43-44 (1993).
[16] Wolf, J. : Born-again group testing: multiaccess communications. IEEE Trans. Inform. Theory 31 , 185–191 (1985).