【概率型群试问题研究】.pdf
浙江大学研究生学位论文用纸P./摘 要 教讨论概率型群试问题的个横型:二证群试横型 和对称型二该群试模型。对前一个模型:提出了群试算法 的关联约来松念,记明了两两测试算法是最优关鞋算法 的充要手体,这个结论部分证明了[2}]中猜想;提出了群试 算法可竞多性起之念,通过新给出的E以们下界,得到了几个 可意行算法,并证用了一一测试两两则试皆是可竟争口对 后一模型;给出了最化节巢算法的意式递归公式,证明 了一一测试不可能是最化带掌算法,首次给出了两雨测讨 法类,给出了该类中最优算法的必要体,并给出了该寿中一个 新算法一网形算法,它比已有的是式算法皆好。
浙江大学研究生学位论文用纸 P 第一章 综 述 1.问题的提出及研完意义 在质量检验中,如对大是产品中每体单独一一浏试是一体抗长而化费大 的过程,遍常采用的方法是位取这批产品中的一些样本进行一试,如果坏元比率过大拒绝接受这批产品。这种统计方法的缺点是不 能找出所有坏元,而它在许多时候是父需的年 Dorfman[2]左军 队征兵检血中首次这用了群试亦法转好解决了比问题。目体方法是; 先持每个应征者血液分成两部分,每次将个应征者(江)的血挥混在 一起化拾一次如果结果是未被传染,则说明这x久符合要求,占别,人 中至少有一人被传染,此时再将这个人的另一部分血液一一化捡。
浙江大学研究生学位论文用纸 P 这样,最优带肇算法已分长为N的=证巢所用测试期望次数为 H(N)该公式计算它的复利性为 D(N3)[17]中还证明了中x 仅依赖于m,利用此性质远给出了计算HLN)的O(N)算法 结论14 L1)用Fm)表示在最优节巢算法下从长为m的不纯集中找出一坏元的测试期望次数,则 F=0 Hloy=o 1-(4h F(m)=1+min{-9m ≤x1qm -9n H(n)=+Hwang 又给出了计算H(W) 的 D(N)算法: 结论比t7]设km)表示在最优带巢算法下长为m的二识集中找出第一个 坏元的测试期望次数,则 k(o)=0 H(o)=