請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/91765
標題: | 針對持續性隨機比較錯誤的高效率最小數近似演算法 An efficient algorithm for approximating the minimum with persistent random comparison faults |
作者: | 張祐承 Yu-Cheng Chang |
指導教授: | 劉智弘 Chih-Hung Liu |
關鍵字: | 近似最小數,不可靠,比較,持續錯誤, Approximate Minimum,Unreliable,Comparisons,Persistent Faults, |
出版年 : | 2023 |
學位: | 碩士 |
摘要: | 我們研究如何在持續且隨機的比較錯誤下,高機率地從n個數中找到一個排序在O(logn) 以下的數(高機率的定義是,機率至少超過1− 1/n)。持續且隨機的比較錯誤是指說任兩個數互相比較大小不管幾次,都會產生一樣的比較結果,且有一個已知的機率p< 1/2 可能產生錯誤,也就是跟實際大小關係不同的比較結果,其中每對數字的互相比較,錯誤比較事件的發生都是互相獨立的。現在最好的演算法在p< 1/16 的條件下,(由Geissmann等人[8]提出的演算法)可以在O(nlogn) 的時間複雜度內,高機率地找到一個排序在O(logn)以下的數,但當在1/16 ≤ p < 1/2 的情況(BravermanandMossel[4]的演算法)時間複雜度提升到n^O(1)。
我們設計的演算法可以在所有p< 1/2的條件下,只花費O(nlogn)的時間複雜度,高機率地從n個數中找到一個排序在O(logn)以下的數,其中時間和排序大O裡的常數跟p有關。 The problem we address is finding an element of rank O(logn) from n elements with the so-called high success probability (i.e., with success probability at least 1 − 1/n) in the presence of persistent random comparison faults where the outcome of comparing two elements is wrong with a known error probability p < 1/2, comparing the same pair of elements multiple times always gets the same outcome, and the outcomes of comparing different pairs of elements are independent. The state-of-the-art sorting algorithm with persistent random comparison faults can find an element of rank O(logn) with high success probability. However, the sorting time is O(nlogn) if p < 1/16 by Geissmann et al. [8], but is n^O(1) if 1/16 ≤ p < 1/2 by Braverman and Mossel [4]. It is an open question to find an element of rank O(logn) with high success probability in O(nlogn) time for 1/16 ≤ p < 1/2. We develop an O(nlogn)-time algorithm that for any error probability p < 1/2, finds an element of rank O(logn) from n elements with probability at least 1 − 1/n, where the constant inside the big-O notation depends on the error probability p. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/91765 |
DOI: | 10.6342/NTU202400463 |
全文授權: | 同意授權(限校園內公開) |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-112-1.pdf 授權僅限NTU校內IP使用(校園外請利用VPN校外連線服務) | 357.02 kB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。