下载此文档

算法合集之《浅析非完美算法在信息学竞赛中的应用》.ppt

文档分类：IT计算机 | 页数：约29页举报非法文档有奖

1/29

下载提示

1.该资料是网友上传的，本站提供全文预览，预览什么样，下载就什么样。
2.下载该文档所得收入归上传者、原创者。
3.下载的文档，不会出现我们的网址水印。

同意并开始全文预览

(约 1-6 秒)

1/29 下载此文档

文档列表 文档介绍

长郡中学胡伟栋
计算机科学中非完美的例子
图片、音频、视频的压缩
很多压缩率比较高的压缩方法都是有损压缩
密码验证
很多都是多对一,通过验证的不一定是正确的
搜索引擎
不一定能搜索到所有匹配的内容
较小的磁盘空间
安全、实用
方便、快捷
非完美算法
在信息学乃至整个计算机科学领域,不一定绝对正确的算法就是最好的算法,有可能一个在绝大多数情况下正确的算法(非完美算法)比一个完全正确的算法更有前途。
时间使用较少
空间使用较少
实现较容易
容易被接受
非完美算法的一些常见方法
随机贪心
抽样测试
部分忽略
……
——周咏基《论随机化算法的
原理与设计》
(*)
(*)
抽样测试法
抽样:从统计总体中,任意抽出一部分单位作为样本,并以其结果推算总体的相应指标。
抽样测试法
s
满足条件A
具有性质P
√
抽样测试法
10000个元素
100个满足条件
只要少量抽样就能取
得较高的正确率
抽样测试法
在抽样测试时,有时总体中存在一些特殊的元素,这些元素满足条件的概率往往与其他元素满足条件的概率相差较大。如果特别的在这些元素中抽取一些进行测试,则可以加快出解的速度或增大解的正确率。
——特殊抽样
抽样测试法——特殊抽样
α={‘A’,’B’,’C’,……,’Z’}
总体:α的所有子集
条件:含{‘A’,’B’,’C’,……,’G’}的集合
取特殊元素α即满足条件!
质数判定
朴素的质数判定方法:
用2~ 试除。O()
抽样测试法:
在2~ 中抽取k个试除。
×

算法合集之《浅析非完美算法在信息学竞赛中的应用》来自淘豆网m.daumloan.com转载请标明出处.

算法合集之《浅析非完美算法在信息学竞赛中的应用》.ppt

算法合集之《一类算法复合的方法》

改进粒子群算法在机械优化设计中的应用

传统优化算法与竞选算法应用于机械优化设计的比较

毕业论文-遗传算法在函数优化中的应用

渗流力学问题精确解的算法及应用

遗传算法在双层圆柱面网壳结构优化中的应用

智能优化算法在电力系统无功优化中的应用研究

变量选择中的LARS算法及其在国民经济中的应用

算法合集之《动态规划的特点及其应用》

国际联运中集装箱单据及集装箱装箱软件算法介绍