On two random search problems |
| |
Authors: | András Sebő |
| |
Institution: | Computer and Automation Institute, Hungarian Academy of Sciences, Budapest, Hungary |
| |
Abstract: | The paper is concerned with static search on a finite set. An unknown subset of cardinality k of the finite set is to be found by testing its subsets. We investigate two problems: in the first, the number of common elements of the tested and the unknown subset is given; in the second, only the information whether the tested and the unknown subset are disjoint or not is given. Both problems correspond to problems on false coins. If the unknown subset is taken from the family of k-element sets with uniform distribution, we determine the minimum of the lengths of the strategies that find the unknown element with small error probability. The strategies are constructed by probabilistic means. |
| |
Keywords: | 94A50 05B99 Sequential Static strategies Random search Separating systems Random construction |
本文献已被 ScienceDirect 等数据库收录! |
|