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年贵州工贸职业学院单招综合素质考试题库.. 73页

2025年幼儿园语言教学说课稿 24页

2025年贵州文化旅游职业学院单招职业技能测试.. 74页

基于CUDA的数控仿真加工面显示算法的研究 3页

基于CREAM的电网人为可靠性定量分析方法 3页

2025年神木职业技术学院单招职业适应性考试题.. 72页

2025年贵州盛华职业学院单招职业倾向性测试题.. 75页

2025年贵州省毕节地区单招职业适应性测试题库.. 72页

2025年贵州省黔西南布依族苗族自治州单招职业.. 74页

2025年福建农林大学金山学院单招职业适应性考.. 73页

2025年贵州职业技术学院单招职业适应性测试题.. 72页

2025年福建林业职业技术学院单招职业技能测试.. 74页

2025年贵州轻工职业技术学院单招职业倾向性考.. 75页

幼儿园中班十月份计划报告 4页

基于BOPPPS教学模式的“基础会计”课程教学设.. 3页

2025年赤峰工业职业技术学院单招职业倾向性测.. 72页

2025年绍兴文理学院元培学院单招职业技能测试.. 74页

2025年绍兴职业技术学院单招综合素质考试题库.. 73页

2025年幼儿园春季开学典礼活动方案主题 27页

2025年苏州健雄职业技术学院单招职业适应性测.. 74页

2025年幼儿园教育讲座的心得体会 4页

相机租赁合同 4页

菜鸟驿站员工工作合同 5页

学徒工聘用劳动协议汇编3篇 10页

电梯质量手册程序文件 49页

钢结构厂房施工合同范本 11页

员工入职健康体检表健康证明 2页

基地种植主管岗位职责(共8篇) 14页

《基本要道》 187页

《GJB2650-1996 微波元器件性能测试方法》.pd.. 68页