1 / 38
文档名称:

第九章概率算法.ppt

格式:ppt   大小:2,176KB   页数:38页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

第九章概率算法.ppt

上传人:卓小妹 2022/8/16 文件大小:2.13 MB

下载得到文件列表

第九章概率算法.ppt

相关文档

文档介绍

文档介绍:第九章概率算法
第1页,共38页,2022年,5月20日,14点43分,星期日
2022/8/22
1
计算机算法设计与分析
概率计算
概率计算就是在算法中可采用随机选择计算的步骤、元素或参数等。
它的基本特征是计算具有022年,5月20日,14点43分,星期日
2022/8/22
9
计算机算法设计与分析
Fermat素数测试法
Fermat定理: 若p是素数,则对任意整数a,gcd(a, p) = 1,则有ap–1≡1 (mod p)。
显然,对素数p有pp–1 ≡1 (mod p)。
对于一般的整数n,满足nn–1≡1 (mod n)的数目很少。满足的称为伪素数。
就用是否满足nn–1≡1 (mod n)来判断n是否为素数。
第10页,共38页,2022年,5月20日,14点43分,星期日
2022/8/22
10
计算机算法设计与分析
Fermat素数测试法
Bool Fermat_Prime(int n) {
a = 2; power = n – 1; other = 1;
while(power > 1) {
if (power % 2 = = 1) {other *= a; other %= n;}
power /= 2; a = a * a % n;}
if (a * other % n == 1) return True;
return False;
}
第11页,共38页,2022年,5月20日,14点43分,星期日
2022/8/22
11
计算机算法设计与分析
合数的见证者
设n为测试的自然数,不妨设n是大于2的奇数,则有n – 1 = 2im,其中i是非负整数,m是正奇数。取一自然数b,1 < b < n,记W(b)为条件:
① bn–1 ≠ 1 (mod n) 或
②i,使得m = (n–1)/2i 且 1 < gcd(bm–1, n) < b。
若①或②中有一个为真,就认为W(b)满足,则n必定是合数,我们称b是n为合数的见证者。
若n有见证者,则n必定为合数。
第12页,共38页,2022年,5月20日,14点43分,星期日
2022/8/22
12
计算机算法设计与分析
合数的见证者多于一半
Miller已经证明,存在常数c,使得当n为合数时,在[1, c(log n)2]范围内有见证者。
Rabin证明了:如果n是合数,则
|{b|1<b<n,W(b)满足}|≥(n–1)/2
即,在小于n的自然数中有多半是n的见证者。
任取一个自然数b < n,若b不是n的见证者,则n是合数的概率小于1/2。若随机取m个数都不是见证者,则n是合数的概率小于1/2m。
第13页,共38页,2022年,5月20日,14点43分,星期日
2022/8/22
13
计算机算法设计与分析
Miller-Rabin素数判定概率算法
Bool Miller_Rabin_Prime(int n){
b[1 .. m] = RandomSampling(n, m);
/*随机选取m个大于1小于n的无重复的自然数
for (j = 1; j <= m; j++)
if (W(b[j]) 满足) return False;
return True;
}
若m = 100,则n不是素数的概率小于1/2100。
第14页,共38页,2022年,5月20日,14点43分,星期日
2022/8/22
14
计算机算法设计与分析
Las Vegas算法
Las Vegas算法的特点是随机性地进行决策。
例如对n后问题,Las Vegas算法是随机地产生一组王后放置的位置。若成功了,便找到了一个解;若失败了,就整个重来,再随机产生另外一组王后的位置。这样作,直至找到解。
此算法能显著地改进算法的有效性,甚至对迄今为止找不到有效算法的问题,也能得到满意的结果。
第15页,共38页,2022年,5月20日,14点43分,星期日
2022/8/22
15
计算机算法设计与分析
瞎子爬山法与局部最优
更一般的求解问题的方法是瞎子爬山法。
一个瞎子从山脚开始,试探着一步一步向上爬,就可以一直爬到山顶。
可是,他爬上的可能只是个小山头,更高的山还在后面。而他无法从小山头下来,也就无法爬到更高的山头了。
这种情形就被称为陷入了局部最优。
如何避免陷入局部最优是求解问题中要注意的一个重要问题。
第16页,共38页,2022年,5月20日,14点43分,星期日
2022/8/22
16
计算机算法设计与分析
进化算法(Evolutionary

最近更新

2025年重庆航天职业技术学院单招职业技能测试.. 74页

2025年年江苏高考英语作文范文 3页

2025年大学大二学生学年自我鉴定 15页

2025年重庆轻工职业学院单招职业技能测试题库.. 73页

高校校园记者新闻写作培训 37页

2025年重庆商务职业学院单招职业适应性测试题.. 75页

2025年年度培训计划表内容模板 60页

固定化光合细菌处理含氯酚废水的特性研究 3页

2025年重庆工贸职业技术学院单招职业倾向性测.. 75页

2025年重庆市内江市单招职业适应性测试题库审.. 74页

2025年重庆市宜宾市单招职业适应性测试题库最.. 74页

2025年重庆市泸州市单招职业倾向性考试题库及.. 75页

2025年长春医学高等专科学校单招职业倾向性考.. 76页

2025年长春汽车职业技术大学单招职业倾向性测.. 76页

2025年长春职业技术学院单招职业技能考试题库.. 74页

2025年长春金融高等专科学校单招职业适应性考.. 76页

2025年大学什么专业好就业 4页

2025年重庆机电职业技术大学单招职业技能考试.. 74页

2025年年事业单位年度总结工作报告 18页

2025年长沙文创艺术职业学院单招职业倾向性考.. 74页

2025年新课程理念下学生学习方式转变的研究【.. 8页

2025年重庆能源职业学院单招职业适应性考试题.. 73页

2025年长沙轨道交通职业学院单招职业倾向性测.. 73页

2025年新药研发的项目策划书3篇 6页

2025年平安夜圣诞节高级文案 17页

哈尔滨市汽车零部件产业国际科技合作状况研究.. 3页

创意英语数字教案:提升学生学习兴趣 9页

人教版一年级数学下册各单元知识点 14页

2024年小学生知识竞赛问答试题及答案(共44题).. 7页

plc1200六层三部电梯控制系统的设计模板 38页