论文部分内容阅读
本文研究了搜索论中如何从n个硬币(元素)的集合中找到所含唯一重币(一个未知元素)的经典问题.内容包括非容错搜索和容错搜索两大部分.该问题的目的是要用尽量少的实验次数找到重币(未知元素).称一种算法完成搜索任务所需的最少实验次数为其长度.
第二章为非容错搜索部分.该部分研究的问题为:如何用b≥1个天平从含有n个硬币的集合中找到其所含的唯一重币.这是对通常所研究的搜索问题中采用一个天平为实验装置的推广.我们证明了最坏情况下序列算法及预确定算法的长度均为问题的信息论下界「log2b+1n].在假设分布为均匀分布时,也分别确定出了序列算法和预确定算法的平均长度.此外,我们也考虑了该问题的两个变式.
第三章和第四章为容错搜索部分.研究的是一类受限制说谎问题:当允许说谎一次且说谎受一个d-正则信道(1≤d≤q-1)限制时,如何用最少次数的q-元提问从一个有限的集合中找到一个未知元素(数字).在第三章,当搜索空间的大小为qi,i≥1时,对1≤d≤q-1证明了所求的最少次数就为该问题的信息论下界.在第四章,在一个特殊的1-正则信道G1下,对具有任意大小n≥2的搜索空间确定出了找到未知元素所需的最少q-元提问次数.