欢迎来到技术文库! | 帮助中心 技术提升企业竞争力!
技术文库
全部分类
  • 化工机械>
    石油标准 机械标准 阀门标准
    化工机械
    石油标准 机械标准 阀门标准 管件接头 法兰标准 钢铁标准 金属冶金 锅炉标准 特种设备 重型机械 紧固件标 泵类标准 压缩机标 换热器标 联轴器标 过滤器标 人孔手孔 密封垫片 气体贮罐 轴承齿轮 仪器仪表 气动液压 油脂油品 焊接标准 铸造锻造 计量标准 涂料染料 化工原料 热处理标 无损检测 检验检测 管道工程 规章规范 机械制图 其他标准 工业自动化
  • 国外标准>
    JIS标准 BS标准 ASME标准
    国外标准
    JIS标准 BS标准 ASME标准 DIN标准 EN标准 ISO标准 ANSI标准 NF标准 KS标准 CSA标准 其他标准
  • 行业标准>
    煤矿能源 铁路标准 船舶标准
    行业标准
    煤矿能源 铁路标准 船舶标准 电气电力 电子信息 汽车标准 航空民航 纺织标准 家用电器 包装储运 质量管理 医药卫生 通信标准 交通标准 烟草标准 轻工标准 公安消防 检验检疫 核工业标准 环保气象 土地测绘 水利标准 林业标准 劳动安全 文体教育 广播影视 稀土标准 合格评定 军用标准 地方标准 其他标准 橡胶塑料 贸易标准 海洋标准 地震标准 密码行业标准 认证认可标准 旅游标准 金融标准 民政标准 团体标准 团体标准
  • 管理文献>
    经营企划 财务管理 生产管理
    管理文献
    经营企划 财务管理 生产管理 质量管理 仓储管理 销售管理 代理连锁 工程管理 信息管理 行政管理 经典理论 管理咨询 经营战略 管理决策 资本运营 组织管理 品牌管理 市场营销 广告经营 项目管理 成本管理 物流管理
  • 建筑标准>
    通用标准 建筑机械 建材标准
    建筑标准
    通用标准 建筑机械 建材标准 城建标准 路桥标准 给水排水 安装设计 工程结构 施工工艺 混凝土标准 门窗玻璃 材料验收 规章规范 地方其他
  • 书签 分享 收藏 举报 版权申诉 / 95

    随机性在计算机领域中作用

  • 上传人: 娟**
  • 文档编号:31253754
  • 上传时间:2021-04-21
  • 文档格式:PPT
  • 文档页数:95
  • 文档大小:402.50KB
  • 配套讲稿:

    如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。

    特殊限制:

    部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。

    关 键  词:
    随机性 计算机 域中 作用
    资源描述:

    《随机性在计算机领域中作用》由会员分享,可在线阅读,更多相关《随机性在计算机领域中作用(95页珍藏版)》请在技术文库上搜索。

    1、随机性在计算机领域中的作用 随机性的作用 “Randomization is a big idea in computer science.”-C. E. Leiserson MIT 随机性的作用 宾夕法尼亚大学的Andr DeHon在“Big Ideas in Computer Science in Computer Science and Engineering”中总结了所有计 算机学科中有代表性的重要思想,其中多 次提到了“随机性”。 1. 随机化的快速排序算法 确定性的快速排序算法 确定性的快速排序算法的效率依赖于pivot值的选 取。 只要pivot值的选取方式固定,都存在一些规模为。

    2、 n的输入,使得快速排序算法效率为(n2)。 例如,如果每次取pivot待排序数的最后 一个,快速排序算法于已排序好的数 效率最低。 也就是,确定性的快速排序算法希望入数据 没有任何律,是完全随机的。 随机化的快速排序算法 每次在输入数据中随机地选取pivot值。 不存在任何输入使得随机化的快速排序算 法在该输入下复杂度一定为(n2)。 随机化的快速排序算法不依于外部入 数据的随机性。 随机算法的作用之一:降低对输入 数据随机性的依赖 确定性的快速 排序算法 依赖于输入 数据的 “随机性” 随机性的快速 排序算法: 带有一种 内置的随机性 (built-in randomness) 不依赖输入。

    3、 数据的 “随机性” 2. 计算“平均成绩”问题 计算“平均成绩”问题 n个学生P1,P2,Pn参加了一次考试,学生Pi 的成绩为Ci(1in)。现在这n个学生要计算他们的 平均成绩,并且保证: (1) 任何一个学生都不泄露自己的成绩。 (2) 即使有k个学生之间相互共享信息,这k个学生 最多也只能知道其余n-k个学生的平均成绩。 是否存在一种可行的方案? 协议(protocol) 我们通过设计一个“协议”来解决这个问题。简单 地说,“协议”是两个(或两个以上)人为完成某项任 务而进行的一系列操作步骤。 最简单的协议是“切蛋糕”协议。 参与者:两个人A和B。 任务:公平地分一块蛋糕。 操作步骤。

    4、:(1)A把蛋糕切成2块。 (2)B选走其中一块蛋糕。 (3)A取走剩下的那块蛋糕。 计算“平均成绩”问题 参与者: n个学生P1,P2,Pn 任务:计算平均成绩(满足前面提到的两个 条件) 步骤:? 协议1 思想:假设考试包含n道题目。每个同学Pi 负责统计所有同学第i道题目的得分。最后 把所有同学的统计结果加起来,得到总成 绩。 协议1 (1) 每个学生Pi把自己的成绩分成n份Ci=Ci1+Ci2+Cin(其 中Cij代表第i个同学第j道题的分数),学生Pi把Cij告诉给 学生Pj。 (2) 每个学生Pj计算并公布Dj=C1j+C2j+Cnj (所有学生第j道 题的得分)。 (3) 计算D。

    5、1+D2+Dn,得到总成绩。 协议1的优点 一方面,为了计算总成绩,每个学生必须把自己 的成绩以某种方式发布出去,实现“信息共享”。 另一方面,任何学生都不能直接把自己的成绩告 诉给任何人。 每个学生Pi把自己的成绩分成n份,把其中n-1份 分别告诉其他n-1个同学。这样每个学生从Pi那得 到的只不过是关于学生Pi成绩的“部分信息”。 协议1的缺点 考试未必恰好包含n个考试题目。 假设k个同学共享信息,可以大概估计其他 同学的考试分数。 协议2 (1) 每个学生Pi把自己的成绩分成n份Ci=Ci1+Ci2+Cin(对任 意j, Cij为0和Ci之间的随机数),学生Pi把Cij告诉给学生Pj。 。

    6、(2) 每个学生Pi计算并公布Di=C1i+C2i+Cni (3) 计算D1+D2+Dn,得到总成绩。 协议2(例子) 假设n=30,学生P1成绩是90,学生P2成绩 是30。则相应的矩阵可能为: 协议2的缺点 假设k个同学共享信息,可以大概估计出: 某两个学生Pi和Pj的分数哪个更高。 原因:随机变量Cij为0和Ci之间的随机数, 因此可以从Cij中得到关于Ci的统计信息。 协议3 思想: 选取一个数M,使得Cij为0和M之间的随机数。 这样的好处是: 无需担心可以从Cij中得到M的任何统计信息。 协议3 (1) 选取M=101*n,每个学生Pi产生n-1个1到M之间的随机数 Cij(i j。

    7、, 1jn),计算Cii,使得Ci=Ci1+Ci2+Cin(mod M) ,学生Pi把Cij告诉给学生Pj。 (2) 每个学生Pi计算并公布Di=C1i+C2i+Cni(mod M)。 (3) 计算D1+D2+Dn (mod M),得到总成绩。 协议3(例子) 假设n=30,选取M=101*30=3030。学生P1成绩 是90,学生P2成绩是30。 相应的矩阵可能为: 其中矩阵第一行所有值相加等于3120=90(mod 3030) 其中矩阵第一行所有值相加等于6090=30(mod 3030) 协议3 分析: 协议3满足: (1)任何一个学生都不泄露自己的成绩。 (2)即使有k个学生之间相互共。

    8、享信息,这k个学生 最多也只能知道其余n-k个学生的平均成绩。 这是因为:每个学生Pi从其他学生那里得到的无 非是一些0到M(公开的)之间的随机数。 随机性在协议3中起的作用 基本思想:把学生Pi的成绩Ci分成n份 Ci=Ci1+Ci2+Cin(其中n-1个数都是随机 数),借助这些随机数的“掩护”,Ci中包含 的信息才不会被泄露。 3. 验证一个数是否为质数 RSA算法 (1)生成两个大质数p, q 要想保证RSA的安全性,p和q的数量级应 为21000。 生成质数的算法 generatePrime(m, n) /生成一个m到n范围内的质数 isPrime = false; while(!i。

    9、sPrime) k = rand(m,n);/生成一个m到n范围内的随机数 isPrime = primilityTesting(k);/验证n是否为质数 return k; 如果要生成一个21000数量级的质数,对 primilityTesting算法效率有很高的要求。 “验证质数”的一个简单算法 primilityTesting(n) for i = 2 to n 1 if (n % i = 0) return false; return true; 算法复杂度为O(n),也就是说要验证一个21000数 量级的数是否为质数,需要O(21000)的时间。 验证质数的算法 Miller-Rab。

    10、in Test是验证一个数是否为质数 的最常用的方法,也是最著名的随机算法 。 我们这里主要介绍该算法的框架结构和整 体思想。 Miller-Rabin Test的思想 假定要验证n是否为质数,该算法验证n为 质数的某个必要条件(存在高效率的算法 )。根据验证的结果判断n是否为质数。 这个必要条件就是“费马小定理”(Fermats Little Theorem) 费马小定理 如果一个数p是质数,那么对于任意的 a1,2,p-1, ap-1 = 1 (mod p)。 例如, 从1,2,p-1中随机地选取a=2: 7是质数 2(7-1) = 64 = 1 (mod 7) 2(6-1) = 32 =。

    11、 2 1 (mod 6) 6不是质数。 Miller-Rabin Test的思想 如果一个数p是质数,那么对于任意的 a1,2,p-1, ap-1 = 1 (mod p)。 例如, 从1,2,p-1中随机地选取a=2: 2(7-1) = 1 (mod 7) 7是质数。 2(6-1)1 (mod 6) 6不是质数。 Miller-Rabin Test的思想 如果一个数p是质数,那么对于任意的 a1,2,p-1, ap-1 = 1 (mod p)。 从1,2,p-1中随机地选取a: a(n-1) = 1 (mod n) n是质数。(理由不充分 ) a(n-1)1 (mod n) n不是质数。(一定。

    12、成立) Miller-Rabin Test的思想 从1,2,p-1中随机地选取a: a(n-1) = 1 (mod n) n是质数。(理由不充分 ) a(n-1)1 (mod n) n不是质数。(一定成立) 如果算法返回“n不是质数”,则n一定不是质数。 如果算法返回“n是质数”,则算法有可能“出错”。 事实上,可以证明,“出错”的概率小于1/2。 Miller-Rabin Test算法 将以下“实验”重复进行k次: 从1,2,p-1中随机地选取a: a(n-1) = 1 (mod n) n是质数。(理由不充分) a(n-1)1 (mod n) n不是质数。(一定成立) (Miller-Rab。

    13、in Test算法在此基础上还作了进一步的改进。) 如果算法返回“n不是质数”,则n一定不是质数。 如果算法返回“n是质数”,则算法有可能“出错”。 事实上,可以证明,“出错”的概率小于(1/2)k。 随机算法中一种常用的技巧 复 度 “失”的概 率 1次随机 O(f(n)p k次随机 k*O(f(n)pk 在随机算法的精确度和时间复杂度之间可以进行 交换(trade-off): 代价:算法时间复杂度以线性的速度上升。 收益:算法“失败”的概率以指数级的速度下降。 4. 零知识证明(zero- knowledge proof) 什么是零知识证明? A向B证明c,证明结束后B不知道关于c的 任何。

    14、信息。 J.-J. Quisquater et al., How to Explain Zero-Knowledge Protocols to Your Children, Proc. Advances in Cryptology, pp. 628-631, 1989. 我们举另外一个例子。 一个直观的例子 有一个迷宫,A知道这个迷宫从入口s到出口t的n 条路径。假设A想让B相信从s到t至少有一条路径 ,同时A又不希望向B泄露从s到t的路径。该采用 什么样的方法? st 解决办法 (1) A选取从s到t的任意一条路径及路径上的一个 中间点m1。以m1为界,将路径一分为二:s,m1 和m1,t。。

    15、A把m1的位置告诉给B。 st m1 解决办法 (2) B随机地向A提问:“从s如何到达m1?”或“从 m1如何到达t?” st m1 解决办法 (3) A回答B的问题,B验证A的答案是否正确。如 果正确,则B相信A知道从s到t的路径。 st m1 分析 从B的角度,假设A只知道s,m1和m1,t其中的 一条路径。A能正确回答B的问题的概率为1/2。 st m1 解决办法 /在G中随机选择一条边(x, y) contract (x, y); /聚合边(x, y) return |E|; 分析 给定一个图G = (V, E),重复执行 connectivity(G) kn2次之后,算法“出错”的 概率小于(1/e)k (其中n为图G的顶点数,e为 自然对数的底)。 Nick Harvey: “The Best Algorithms are Randomized Algorithms” University of Waterloo, 2010. 总结 基于随机性的方法是计算机领域中常用的 解决问题的方法。 我们列举了随机性在以下几个方面的应用 :设计协议、数论、密码学、数据通信、 图论。。

    展开阅读全文
      技术文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    0条评论

    还可以输入200字符

    暂无评论,赶快抢占沙发吧。

    关于本文
    本文标题:随机性在计算机领域中作用
    链接地址:https://www.jswku.com/p-31253754.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们
    手机版 | MIP | 粤公网安备 44060602000677号 | 经营许可证(粤ICP备16048919号)| 本站法律顾问陈鑫辉律师(13807302170)
    ©2008-2020 by Guangdong Foushan Jswku.com Inc. All Rights Reserved.
    收起
    下载帮助
    侵权处理
    上传问题
    展开