臺灣博碩士論文加值系統

論 文 摘 要
群試發展至今已經有50多年的歷史。Dorfman (經濟學者)在1942年研究徵
兵驗血問題，發現10人一起檢驗，可以省下約80%的經費。這事件就是群試的
起源。1959年Sobel& Groll在Bell研究室用群試的辦法測試裝置是否漏氣問題，
，使得群試逐漸受到學術界重視，引進許多傳統數學的技巧來解決群試問題，
更進而發現許多有名的數學問題可以用群試問題做更全新的解釋。
群試問題中有一個很重要的子題 : 平行測試 (Non-adaptive test )問題。在
這個子題中，有一種很重要的測試模式稱為 d-disjunct 模式，在這種模式下，
做完測試後可以很容易指認出有瑕疵的元素。現在假設樣本中最多只有d件可
能有瑕疵，如果只做 t次測試，要如何設計一個好的測試法則，且能處理的樣
本個數最多可有多少？這都是至今未解的難題。假設用符號N(d , t)代表此種模
式上可處理最大樣本的個數。黃光明和Sos在1987年提出一個平行測試法則且
證明在此種法則下可以得到
N(d , t)≧ (2/9)2^(ct) , 其中 C≒ (0.099/d^2 )
到目前為止，我們不知道有其他的法則使得N(d , t)能夠達到類似的指數上界。
在這一篇論文中，我們發現黃光明和Sos的法則其實有更好的估計，即我們可
證明
N(d , t)≧2^(ct) , 其中 c≒0.23355/d^2
如果用或然率的估計技巧Erods 等人證明在d=2時N(2 , t)的值可以更大。
但是，現在仍沒有一種運算法則可以把這種d-disjunct矩陣找出來。

目 錄
第一章 群試與基本定義…………………………………………………………1
第二章 平行群試的上下界………………………………………………………7
參考文獻 …………………………………………………………………31

參考文獻
〔1〕 Ding-Zhu Du and Frank K.Hwang,"Combinatorial group testing and its appli-
cations", World Scientific Pub.Co.,1993.
〔2〕 P.Erdos, P.Frankel and Z.Furedi,.Familes of finite set in which no set is covered
by the union of two others , J.Com.Th.A33（1982）158-166
〔3〕 P.Erdos, P.Frankel and Z.Furedi, Familes of finite set in which no set is covered
by the union of r others, Israel J.Math.51（1985）79-89
〔4〕 F.K.Hwang and V.T Sos , Non-adaptive hypergeometric group testing , Studia.
Scient. Math. Huangarica 22（1987）257-263
〔5〕 F.J. Macwilliams and N.J.A. sloane ,"The theory of error correcting codes",
North Holland Pub.co.,1977
〔6〕 P. Frankl , On Sperner families sotisfying an additional Tcondition , J. Combin
Thy. A24（1978）308-311
〔7〕 M. Ruszinko , On the upper bound of the sign of the r-cover-free families , pre-
print.
〔8〕 P.Busschbach, Constructive methods to solve the problem：s-subjectivetivity,
conflict resolution, coding in defective memories, unpublished manuscipt, 1984