國立高雄大學圖資館 |

語系: 繁體中文

說明(常見問題)

圖資館首頁

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

連續型閾限群試研究 = Threshold group testing ...

國立高雄大學應用數學系碩士班

連續型閾限群試研究 = Threshold group testing with consecutive positives

紀錄類型:	書目-語言資料,印刷品 : 單行本
並列題名:	Threshold group testing with consecutive positives
作者:	蔡宜霖,
其他團體作者:	國立高雄大學
出版地:	[高雄市]
出版者:	撰者;
出版年:	2014[民103]
面頁冊數:	33面圖，表 : 30公分;
標題:	群試設計
標題:	Group testing
電子資源:	http://handle.ncl.edu.tw/11296/ndltd/31626678416779631014
附註:	參考書目：面25-27
附註:	103年12月16日公開
摘要註:	閾限群試研究最早是由Damaschke 在2006年所提出來的。有別於傳統的群試設計，如果一個測驗的回答是正(負)，代表此測驗包含至少 𝑢 個(至多 𝑙 個)正的物品，其餘則是會任意回答。另外基於DNA 比對序列的應用，Balding 和Torney(1997)、Colbourn(1999)分別提出了連續型群試模型：總共有 𝑛 個有次序的物品，其中包含最多 𝑑 個正的物品且連續出現。在這篇論文裡，我們用閾限群試設計來處理連續型的群試問題。當𝑛 ≥ 𝑑 + 𝑢 − 2時，我們給定了這類模型的理論下界為⌈log2 𝑛(𝑑 − 𝑢 + 1)⌉ − 1。我們證明了在沒有門檻限制下的情況，順序演算法找到所有正的物品所需要的測驗次數為⌈log2(⌈𝑛/𝑢⌉ −1)⌉ + 2⌈log2(𝑢 + 2)⌉ + ⌈log2(𝑑 − 𝑢 + 1)⌉ − 2。同時，對於有門檻限制的情況，我們證明使用沒有門檻限制情況的演算法亦可完成。此外，針對非調整型演算法我們運用了變形的非覆蓋集合族，幫助我們找到包含正的物品的集合所需要的測驗次數為15log2(𝑛/𝑑) + 4𝑑 + 71，而且解碼的時間複雜度為𝑂((𝑛/𝑑) log2(𝑛/𝑑) + 𝑢𝑑2)。 Threshold group testing introduced by Damaschke (2006) is a generalization of classical group testing where a group test yields a positive (negative) outcome if it contains at least u (at most l) positive items, and an arbitrary outcome for otherwise.Motivated by applications to DNA sequencing, group testing with consecutive positives has been proposed by Balding and Torney (1997) and Colbourn (1999) where n items are linearly ordered and all up to d positive items are consecutive in the order. In this thesis, we use threshold-constrained group tests to deal with group testing with consecutive positives. We prove that all positive items can be identifed in ⌈log2(⌈𝑛/𝑢⌉ −1)⌉ + 2⌈log2(𝑢 + 2)⌉ + ⌈log2(𝑑 − 𝑢 + 1)⌉ − 2 tests sequentially for the gap-free case (u = l + 1) while the information-theoretic lower bound is ⌈log2 𝑛(𝑑 − 𝑢 + 1)⌉ − 1 when 𝑛 ≥ 𝑑 + 𝑢 − 2 and show that the case with a gap (u > l + 1) can be dealt with by the subroutines used to conquer the gap-free case.Using a variation of cover-free family we show that the set of positives can be approximately identified in 15log2(𝑛/𝑑) + 4𝑑 + 71 group tests nonadaptively and its decoding complexity is 𝑂((𝑛/𝑑) log2(𝑛/𝑑) + 𝑢𝑑2).

連續型閾限群試研究 = Threshold group testing with consecutive positives
蔡, 宜霖

連續型閾限群試研究 = Threshold group testing with consecutive positives / 蔡宜霖撰 - [高雄市] : 撰者, 2014[民103]. - 33面 ; 圖，表 ; 30公分.
參考書目：面25-27103年12月16日公開.
群試設計Group testing

連續型閾限群試研究 = Threshold group testing with consecutive positives
LDR:04007nam0a2200289 450 001 430263
005 20170214095626.0
009 430263
010 0 $b 精裝
010 0 $b 平裝
100 $a 20170214d2014 k y0chiy05 b
101 1 $a eng $d chi $d eng
102 $a tw
105 $a ak am 000yy
200 1 $a 連續型閾限群試研究 $d Threshold group testing with consecutive positives $z eng $f 蔡宜霖撰
210 $a [高雄市] $c 撰者 $d 2014[民103]
215 0 $a 33面 $c 圖，表 $d 30公分
300 $a 參考書目：面25-27
300 $a 103年12月16日公開
314 $a 指導教授：張惠蘭博士
328 $a 碩士論文--國立高雄大學應用數學系碩士班
330 $a 閾限群試研究最早是由Damaschke 在2006年所提出來的。有別於傳統的群試設計，如果一個測驗的回答是正(負)，代表此測驗包含至少 𝑢 個(至多 𝑙 個)正的物品，其餘則是會任意回答。另外基於DNA 比對序列的應用，Balding 和Torney(1997)、Colbourn(1999)分別提出了連續型群試模型：總共有 𝑛 個有次序的物品，其中包含最多 𝑑 個正的物品且連續出現。在這篇論文裡，我們用閾限群試設計來處理連續型的群試問題。當𝑛 ≥ 𝑑 + 𝑢 − 2時，我們給定了這類模型的理論下界為⌈log2 𝑛(𝑑 − 𝑢 + 1)⌉ − 1。我們證明了在沒有門檻限制下的情況，順序演算法找到所有正的物品所需要的測驗次數為⌈log2(⌈𝑛/𝑢⌉ −1)⌉ + 2⌈log2(𝑢 + 2)⌉ + ⌈log2(𝑑 − 𝑢 + 1)⌉ − 2。同時，對於有門檻限制的情況，我們證明使用沒有門檻限制情況的演算法亦可完成。此外，針對非調整型演算法我們運用了變形的非覆蓋集合族，幫助我們找到包含正的物品的集合所需要的測驗次數為15log2(𝑛/𝑑) + 4𝑑 + 71，而且解碼的時間複雜度為𝑂((𝑛/𝑑) log2(𝑛/𝑑) + 𝑢𝑑2)。 Threshold group testing introduced by Damaschke (2006) is a generalization of classical group testing where a group test yields a positive (negative) outcome if it contains at least u (at most l) positive items, and an arbitrary outcome for otherwise.Motivated by applications to DNA sequencing, group testing with consecutive positives has been proposed by Balding and Torney (1997) and Colbourn (1999) where n items are linearly ordered and all up to d positive items are consecutive in the order. In this thesis, we use threshold-constrained group tests to deal with group testing with consecutive positives. We prove that all positive items can be identifed in ⌈log2(⌈𝑛/𝑢⌉ −1)⌉ + 2⌈log2(𝑢 + 2)⌉ + ⌈log2(𝑑 − 𝑢 + 1)⌉ − 2 tests sequentially for the gap-free case (u = l + 1) while the information-theoretic lower bound is ⌈log2 𝑛(𝑑 − 𝑢 + 1)⌉ − 1 when 𝑛 ≥ 𝑑 + 𝑢 − 2 and show that the case with a gap (u > l + 1) can be dealt with by the subroutines used to conquer the gap-free case.Using a variation of cover-free family we show that the set of positives can be approximately identified in 15log2(𝑛/𝑑) + 4𝑑 + 71 group tests nonadaptively and its decoding complexity is 𝑂((𝑛/𝑑) log2(𝑛/𝑑) + 𝑢𝑑2).
510 1 $a Threshold group testing with consecutive positives $z eng
610 0 $a 群試設計 $a 閾限 $a 連續正模型 $a 非覆蓋集合族
610 1 $a Group testing $a Threshold $a Consecutive positives $a Cover-free families
681 $a 008M/0019 $b 462101 4431.1 $v 2007年版
700 1 $a 蔡 $b 宜霖 $4 撰 $3 85824
712 0 2 $a 國立高雄大學 $b 應用數學系碩士班 $3 166142
801 0 $a tw $b NUK $c 20141021 $g CCR
856 7 $z 電子資源 $2 http $u http://handle.ncl.edu.tw/11296/ndltd/31626678416779631014