VLSI 芯片测试:
Diogenes 教授有n个被认为是完全相同的VLSI芯片,原则上它们是可以互相测试的.教授的测试装置一次可测试二片,当该装置中放有两片芯片时,每一片就对另一片作测试并报告其好坏.一个好的芯片总能够正确的报告另一片的好坏,但一个坏的芯片的结果就是不可靠的.这样,每次的测试的四种可能结果如下:
a)证明若少于 n/2 的芯片是坏的,在这种成对测试方式下,使用任何策略都不能确定哪个芯片是好的.
b)假设有多于 n/2 的芯片是好的,考虑从 n 片中找出一片好芯片的问题.证明 n/2 对测试就足以使问题的规模降至近原来的一半.
c)假设有多于 n/2 的芯片是好的,证明好的芯片可用 O(n) 对测试找出.
分析:
a)比较显然.略.
b)本题要求证明 n/2 对测试就能使问题的规模降至近原来的一半.所以要考虑的是怎么降低待测芯片的规模,而且还能继续可解.也就是需证明剩下的近一半中,仍然有多于1/2 的芯片是好的. 分两种情况讨论:
如果 n 是偶数,则把它为成 n/2 对.分别测试每一对.如果出现结果2,3,4.则将两片都暂时搁置.如果是结果1,则随意把其中一片搁置.因为有大于1/2 的芯片是好的,所以肯定总是能出现结果为1的一对芯片.设好的芯片 有 k 个,坏芯片 n-k个,分对时有 r 个坏芯片跟好芯片分成一对. k>n-k>=r. 则剩余的好芯片为 (k-r)/2, 剩余的坏芯片至多为 (n-k-r)/2,(当每对坏芯片相遇结果都是1的时候).显然 (k-r)/2 >(n-k-r)/2 .得证.
如果 n 是奇数,则先提一片(设代号为A),剩下的n-1片变为偶数,这在n-1片中,有好片>=坏片,然后按数偶数的情况处理.设经处理后剩下 q 片. 根据上面的步骤易知.在这 q 片中,好片不少于坏片.
现在又为两种情况: 1) q 为奇数: 这时 q 中的好片肯定多于坏片,将A 搁置.
2) q 为偶数: 这时 q 中的好片不少于坏片.若好片等于坏片,反推易知 A 为好片.将 加入 q 中.得证.
c)用b)方法找出一个好片对全部芯片做测试即可.显然只用O(n)对即可得出答案.
看到网上都没有递归式的证明，我证一下。
T(n)表示n个芯片需要找1个好芯片。
T(n/2)表示n/2个芯片需要找一个好芯片。
n/2表示需要n/2次比较n/2对芯片。
所以T(n)=T(n/2)+n/2;
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/atyuwen/archive/2007/10/09/1817600.aspx
分享到：
相关推荐
4.6 证明主定理 4.6.1 对b的幂证明主定理 4.6.2 向下取整和向上取整 思考题 本章注记 第5章 概率分析和随机算法 5.1 雇用问题 5.2 指示器随机变量 5.3 随机算法 ?5.4 概率分析和指示器...
4.6 Proof of the master theorem 97 5 Probabilistic Analysis and Randomized Algorithms 114 5.1 The hiring problem 114 5.2 Indicator random variables 118 5.3 Randomized algorithms 122 5.4 Probabilistic ...
中文名: 算法导论 原名: Introduction to Algorithms 作者: Thomas H. Cormen Ronald L. Rivest Charles E. Leiserson Clifford Stein 资源格式: PDF 版本: 文字版 出版社: The MIT Press书号: 978-0262033848发行...
4.6 Proof of the master theorem 97 5 Probabilistic Analysis and Randomized Algorithms 114 5.1 The hiring problem 114 5.2 Indicator random variables 118 5.3 Randomized algorithms 122 5.4 Probabilistic ...
算法导论英文版，非图片版。 I Foundations Introduction 3 1 The Role of Algorithms in Computing 5 1.1 Algorithms 5 1.2 Algorithms as a technology 11 2 Getting Started 16 2.1 Insertion sort 16 2.2 ...
算法设计与分析第二章学习指南视频算法设计与分析(基础篇) 第二讲 2.1-2.3阅读算法导论(第三版) 第三章，4.3-4.5 节，4.6 节(选读)练习题(3
109 4.4.4 泛化误差估计 110 4.4.5 处理决策树归纳中的过分拟合 113 4.5 评估分类器的性能 114 4.5.1 保持方法 114 4.5.2 随机二次抽样 115 4.5.3 交叉验证 115 4.5.4 自助法 115 4.6 比较分类器的方法 116 4.6.1 ...
中文名: 算法导论 原名: Introduction to Algorithms 作者: Thomas H.Cormen, 达特茅斯学院计算机科学系副教授 Charles E.Leiserson, 麻省理工学院计算机科学与电气工程系教授 Ronald L.Rivest, 麻省理工学院...
4.1 跟踪A∗搜索算法用直线距离启发式求解从Lugoj到 4.2 启发式路径算法是一个最佳优先搜索，它的目标函数是 4.6 设计一个启发函数，使它在八数码游戏
4.6 循环移位 4.6.1 格网 4.6.2 超立方体 4.7 提高某些通信操作的速度 4.7.1 消息分裂和路由选择 4.7.2 全端口通信 4.8 小结 4.9 书目评注 习题 第5章 并行程序的解析建模 5.1 并行程序中的开销来源 5.2 ...
4.6 广义特征值问题 174 4.7 奇异值分解的计算 175 4.8 有关特征值问题的软件 175 4.9 有关历史的注记及参考文献 177 第5章 非线性方程 187 5.1 非线性方程 187 5.2 解的存在性和惟一性 188 5.3 问题的敏感性...
4.6 自稳定 第5章 死锁的预防、避免和检测 5.1 死锁问题 5.1.1 死锁发生的条件 5.1.2 图论模型 5.1.3 处理死锁的策略 5.1.4 请求模型 5.1.5 资源和进程模型 5.1.6 死锁条件 5.2 死锁预防 5.3 一个死锁预防...
4.6 自稳定 第5章 死锁的预防、避免和检测 5.1 死锁问题 5.1.1 死锁发生的条件 5.1.2 图论模型 5.1.3 处理死锁的策略 5.1.4 请求模型 5.1.5 资源和进程模型 5.1.6 死锁条件 5.2 死锁预防 5.3 一个死锁预防...
4.6 嵌入式SQL 59 4.7 SQL是不完美的 66 4.8 小结 66 练习 67 参考文献和简介 68 部分练习答案 73 第二部分 关系数据模型 第5章 域、关系和基本关系变量 77 5.1 引言 77 5.2 域 79 5.3 关系值 86 5.4 关系变量 90 ...
4.6 并行计算技术在实际系统中的应用 4.6.1 主要功能模块与实现方法 该飞机订票系统主要实现了对机票的一些基本信息进行存储和管理的功能。在系统中实现了对机票信息的增删改查，考虑到查询的方便性，对机票按照航班...
4.6 嵌入式SQL 59 4.7 SQL是不完美的 66 4.8 小结 66 练习 67 参考文献和简介 68 部分练习答案 73 第二部分 关系数据模型 第5章 域、关系和基本关系变量 77 5.1 引言 77 5.2 域 79 5.3 关系值 86 5.4 关系变量 90 ...
4.6 嵌入式SQL 59 4.7 SQL是不完美的 66 4.8 小结 66 练习 67 参考文献和简介 68 部分练习答案 73 第二部分 关系数据模型 第5章 域、关系和基本关系变量 77 5.1 引言 77 5.2 域 79 5.3 关系值 86 5.4 关系变量 90 ...
4.6 stlsoft::string_tokeniser 24 4.7 效率大PK 24 五、 C++字符串使用的建议 24 附录1：参考资料： 24 附录2： MSSTL中basic_string的部分源码解读 24 2.1 string的allocator 24 2.1.1 Allocate和Deallocate 24 ...