【关於群试的一些完全性结果】.pdf
浙江大学新究生学位论文早级P 关干 群试的一些 完全性结果.摘要.群试tti的)的计称复杂性一直是一个未 解的问题。最近,Du和k研究了5之紧密相关 的一幸到问题,从而间接地说明了群试问题 的难渡。但在他们的文幸中仍有很多有待研 究的问题,本文解决了所有这些问题。
新江大学有究生学位汇文用级P 第一章综述 5 1 引言 在第=次世界大战期间.Darfman [1]在做征兵 验血试验时首先提出了群试(grap testing) 方法。现 在静试方法已经应用于多门学科,诸如计称机科 学但合学及统计学甘。群低同题的一般形式如下.设N是会有n个元素的集会,记为N={1,n了,在 N中有一些“坏”元素,我们试图通过一享到试验 找出全都“坏“元素,向:是否存在一找出所有“你”元幸的方法使得试验次数最少？群试间题可一般 化为求决定树(decisin tree)的高瘦的最小值。
浙江大学研究生学位论文后F Sn,d ={s/S≤N, Is1=d}和 S≤d ={s-s≤N, 1S1≤d了。群碱中每一个碱验是在N的一个子集T 上进行的,我们以同一符与T记之。试验T在样 本S上的测试结果记为 ANSs(T),称之为回答函败, 我们讨论如下的测试模型[2].模型Ak(K=1):给定样本空间Sh和一个 回答函敏:{,lSITl=