(44.192.112.123) 您好!臺灣時間:2021/03/07 17:11
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:黃冠豪
研究生(外文):Huang, Guan-Hao
論文名稱:密度型群試設計的研究
論文名稱(外文):A study on density-based group testing
指導教授:張惠蘭
指導教授(外文):Chang, Huilan
口試委員:林琲琪鄭斯恩
口試委員(外文):Lin, Bey-ChiCheng, Szu-En
口試日期:2018-01-02
學位類別:碩士
校院名稱:國立高雄大學
系所名稱:應用數學系碩博士班
論文種類:學術論文
論文出版年:2018
畢業學年度:106
語文別:英文
論文頁數:25
中文關鍵詞:密度型群試限區間群試逐步演算法連續型群試
外文關鍵詞:Sequential algorithmDensity-based group testingInterval group testingConsecutive defectives
相關次數:
  • 被引用被引用:0
  • 點閱點閱:44
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:2
  • 收藏至我的研究室書目清單書目收藏:0
在傳統群試的模型裡面,給定 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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
無相關期刊
 
無相關點閱論文
 
系統版面圖檔 系統版面圖檔