在傳統群試的模型裡面，給定 n 個元素，其中有最多有 d 個元素是有缺陷的。我們可以測試某個子集，看它是否包含至少一個有缺陷的元素。目標是通過盡可能少的測試來找出所有有缺陷的元素。

在連續型群試模型裡（由 Balding 和 Torney（1997）和 Colbourn（1999）提出），n 個元素是線性排列的並且有缺陷的元素是連續出現在同一段。在密度型群試設計(Gerbner et al.(2013))，給定一個比率 α 並且測試子集 A，假如測試答案是YES若且唯若子集 A 裡面至少包含 α|A| 個缺陷元素。在限區間群試裡(Cicalese et al. (2007))，每個測試都要是限區間的，也就是說，它的所有元素在搜索空間中都是連續的。在本篇論文裡，我們研究限區間型的密度群試設計並且是連續缺陷的模型。通常假設有 n 個元素和至少 k 的缺陷在裡面。在缺陷的元素沒有連續的情形下，我們可以找到 m 個缺陷的元素，最多只要 ⌈n/a⌉+m⌈log a⌉+(m-1) 限區間測試，其中 a=⌊1/α⌋。假如缺陷元素是連續出現，我們可以找到 m 個缺陷的元素，最多只要 ⌈(n-k+1)/(ka-k+1)⌉+⌈log ⁡ka⌉+⌈log(m-⌊k/2⌋-1)⌉* 限區間測試。

In the classical model of group testing, n elements are given, and there are at most d defective elements among them. We can test a certain subset of elements to see whether it contains at least one defective element or not. The goal is to identify all defectives by using as few tests as possible.

In the group testing with consecutive defectives (proposed by Balding and Torney (1997) and Colbourn (1999)), n elements are linearly ordered and all defective elements are consecutive in the order. In a density-based group testing (Gerbner et al. (2013)), where the presence of defective elements in a test set A can be recognized if and only if their number is large enough compared to the size of A; more precisely, a ratio α is given and for a test A, the answer is YES if and only if there are at least α|A| defectives in A. In a interval group testing (Cicalese et al. (2007)), where each group test is an interval, that is, all its elements are consecutive in the search space. In this thesis, we study a density-based interval group testing with consecutive defectives. It is usually assumed that there are n elements in the search space and at least k defectives. We can identify at least m defective elements in at most ⌈n/a⌉+m⌈log a⌉+(m-1) interval tests where a=⌊1/α⌋. If the defective elements are consecutive, we can identify at least m defective elements in at most ⌈(n-k+1)/(ka-k+1)⌉+⌈log ⁡ka⌉+⌈log(m-⌊k/2⌋-1)⌉* interval tests. All logarithms appearing in the paper are binary.

1.Introduction
2.Preliminaries and Density-based group testing
3.Density-based Group Testing with Consecutive Defectives
4.Density-based Interval Group Testing
4.1 Group Testing with Consecutive Defectives
4.2 General Density-based Interval Group Testing

1. R. Ahlswede, C. Deppe, and V. S. Lebedev, Majority Group Testing with Density Tests, IEEE International Symposium on Information Theory (ISIT), (2011) 326-330.
2. D.J. Balding, D.C. Torney, The design of pooling experiments for screening a clone map, Fungal Genet. Biol. 21 (1997) 302-307.
3. F. Cicalese, J. A. Amgarten Quitzau, 2-Stage fault tolerant interval group testing, in: International Symposium on Algorithms and Computation, Springer. (2007) 858-868.
4. C.J. Colbourn, Group testing for consecutive positives, Ann. Comb. 3 (1999) 37-41.
5. Z.A. Cox Jr., X. Sun, Y. Qiu, Optimal and heuristic search for a hidden object in one dimension. IEEE Int. Conf. Syst. Man Cybern. Hum. Inf. Technol. 2,(1994) 1252-1256.
6. R. Dorfman, The detection of defective members of large populations, Ann. Math. Statist. 14 (1943) 436-440.
7. D.Z. Du, F.K. Hwang, Combinational Group Testing and Its Applications, 2nd ed., World Scientic (2000).
8. D.Z. Du, F.K. Hwang, Pooling Designs and Nonadaptive Group Testing Important Tools for DNA Sequencing, World Scientic (2006).
9. D. Gerbner, B. Keszegh, D. Palvolgyi, and G. Wiener. Density-based group testing. In Information Theory, Combinatorics, and Search Theory - In Memory of Rudolf Ahlswede, (2013) 543-556.
10. Y.W. Hong, A. Scaglione, On multiple access for distributed dependent sources:A content-based group testing approach. In: IEEE Information Theory Workshop ITW (2004).
11. Y.W. Hong, A. Scaglione, Group testing for sensor networks: the value of asking the right answers. In: Asilomar Conference (2004).
12. Y.W. Hong, A. Scaglione, Generalized group testing for retrieving distributed information. In: ICASSP (2005).
13. C.H. Li, A sequential method for screening experimental variable, J. Amer. Statist. Assoc. 57 (1962) 455-477.
14. P.A. Pevzner, Computational Molecular Biology, An Algorithmic Approach. MIT Press, Cambridge (2000).
15. G. Xu, S.H. Sze, C.P. Liu, P.A. Pevzner, N. Arnheim, Gene hunting without sequencing genomic clones: Finding exon boundaries in cDNAs. Genomics 47,(1998) 171-179.