浅析非完美算法在信息学竞赛中的应用课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《浅析非完美算法在信息学竞赛中的应用课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 浅析 完美 算法 信息学 竞赛 中的 应用 课件
- 资源描述:
-
1、 计算机科学中非完美的例子计算机科学中非完美的例子 图片、音频、视频的压缩图片、音频、视频的压缩 很多压缩率比较高的压缩方法都是有损压缩很多压缩率比较高的压缩方法都是有损压缩 密码验证密码验证 很多都是多对一,通过验证的不一定是正确的很多都是多对一,通过验证的不一定是正确的 搜索引擎搜索引擎 不一定能搜索到所有匹配的内容不一定能搜索到所有匹配的内容较小的磁盘空间较小的磁盘空间安全、实用安全、实用方便、快捷方便、快捷非完美算法非完美算法 在信息学乃至整个计算机科学领域,不一定在信息学乃至整个计算机科学领域,不一定绝对正确的算法就是最好的算法,有可能一绝对正确的算法就是最好的算法,有可能一个在绝大
2、多数情况下正确的算法个在绝大多数情况下正确的算法(非完美算法非完美算法)比一个完全正确的算法更有前途。比一个完全正确的算法更有前途。时间使用较少时间使用较少 空间使用较少空间使用较少 实现较容易实现较容易 容易被接受容易被接受 非完美算法的一些常见方法非完美算法的一些常见方法 随机贪心随机贪心 抽样测试抽样测试 部分忽略部分忽略 周咏基周咏基论随机化算法的论随机化算法的原理与设计原理与设计(*)(*)抽样测试法抽样测试法 抽样:从统计总体中,任意抽出一部分单位抽样:从统计总体中,任意抽出一部分单位作为样本,并以其结果推算总体的相应指标。作为样本,并以其结果推算总体的相应指标。抽样测试法抽样测试
3、法s满足条件满足条件A具有性质具有性质P抽样测试法抽样测试法10000个元素个元素100个满足条件个满足条件只要少量抽样就能取只要少量抽样就能取 得较高的正确率得较高的正确率抽样测试法抽样测试法 在抽样测试时,有时总体中存在一些特殊的在抽样测试时,有时总体中存在一些特殊的元素,这些元素满足条件的概率往往与其他元素,这些元素满足条件的概率往往与其他元素满足条件的概率相差较大。如果特别的元素满足条件的概率相差较大。如果特别的在这些元素中抽取一些进行测试,则可以加在这些元素中抽取一些进行测试,则可以加快出解的速度或增大解的正确率。快出解的速度或增大解的正确率。特殊抽样特殊抽样抽样测试法抽样测试法特殊
4、抽样特殊抽样=A,B,C,Z总体:总体:的所有子集的所有子集条件:含条件:含A,B,C,G的集合的集合取特殊元素取特殊元素即满足条件!即满足条件!质数判定质数判定 朴素的质数判定方法:朴素的质数判定方法:用用2试除。试除。O(n0.5)抽样测试法:抽样测试法:在在2中抽取中抽取k个试除。个试除。nnStrong Pseudoprime 对于奇数对于奇数n和正整数和正整数a,设,设n-1=d2s(d为奇数为奇数),若:若:ad1(mod n)或或 存在存在0rs,使,使-1(mod n)则称则称n是以是以a为底的为底的强伪质数强伪质数(Strong Pseudoprime)。判断:判断:O(lo
5、g2n)rda2质数测试质数测试 当当a不是不是n的整数倍时,质数的整数倍时,质数n必然是以必然是以a为底为底的强伪质数。的强伪质数。在所有可能的在所有可能的a中,一个合数至多有的机会中,一个合数至多有的机会为强伪质数。为强伪质数。抽样测试:随机抽取抽样测试:随机抽取k个不同的个不同的a进行测试。进行测试。正确率大于正确率大于14k 时间复杂度为时间复杂度为O(klog2n)。14抽样测试抽样测试质数测试质数测试抽样测试抽样测试 特殊抽样:让特殊抽样:让a取最小的若干个质数。取最小的若干个质数。只用只用2测试:最小的强伪质数为测试:最小的强伪质数为2047,在小于,在小于2.51010中有中有
6、4842个强伪质数。个强伪质数。只用只用2,3测试:最小强伪质数大于测试:最小强伪质数大于1.3106。只用只用2,3,5测试:最小强伪质数大于测试:最小强伪质数大于2.5107。只用只用2,3,5,7测试:最小强伪质数大于测试:最小强伪质数大于3.2109。质数测试质数测试抽样测试抽样测试 一般情况下,只要用一般情况下,只要用2,3,5,7进行测试就能正进行测试就能正确的判断一个数是否为质数。确的判断一个数是否为质数。时间复杂度:时间复杂度:O(log2n)抽样测试法抽样测试法明显降低时间复杂度!明显降低时间复杂度!抽样测试法抽样测试法部分忽略法部分忽略法 在信息学中,可能会遇到这样情况:一
展开阅读全文