计算机问题求解-2013-04-02-概率分析与随机算法.ppt

课外作业 CS pp.340-: 4, 8 CS pp.355-: 1, 2, 4, 6, 12, 16, 18 TC pp.122-: Ex.5.2-1, 5.2-2, 5.2-4 TC pp.128-: Ex.5.3-1 – Ex.5.3-4 TC pp.143-: prob.5-2 * 计算机问题求解 – 论题2-6 - 概率分析与随机算法 2013年04月02日 Histogram for 10 flips of a coin Histogram for answers for a 10-problem test 贝努利试验过程： 当k=8, Average-Case Analysis of Algorithms Expected running time vs. the worst-case running time Worst-case是什么？需执行多少次hiring ? Indicator Random Variable Hiring-Assistant算法的平均情况分析 涉及的随机变量： Hiring操作执行次数：X ； 事件“第i个候选人被雇用”的indicator：Xi ; 为什么？ 让随机“更随机” 条件期望值 将penny也纳入： 引入条件期望值： 若F=“Head”： 若F=“Tail”： X的期望值； 这里n=2；P(F1)=P(F2)=0.5 ? E(X) = (30+20)/2 = 25 随机算法 相当于用抛硬币或者掷色子的方式决定下一步该干什么！ 生成序列的“随机”排列 O(nlogn) O(n) 对两个算法都必须回答同样的问题： 是否得到任意可能的排列的机会是一样的(uniformly distribution)? 相交事件的概率 对一个特别的排列，证明其概率是1/n!：第i个元素“权”恰好是第i个最小。 用Ei表示对特定的i上述条件成立的事件，则要求的排列生成的概率是： 按照条件概率的定义式，并利用归纳法加以推广，上面的式子可以写为： 于是： 只要对上述的“最小”加以不同的解释，这个证明适用于任意排列！ 在by-sorting算法中依次将n个随机生成的“权”赋给各元素。 利用循环不变式的归纳 针对 In-place 算法 可定义如下的不变式： 考虑一个特定排列： 如果第 i 次循环开始前，前i -1个元素恰好是?x1,x2,…xi-1?（事件E1)，定义事件E2：第i次循环恰好将xi放到了第i个位置。则生成上述排列的概率是： 放在第i个位置的元素是在[i,n]中选的 从n个元素中任选i个排列的种数的倒数。 简单、高效是有代价的，所以随机算法经常用于那些“难”问题，牺牲“一点点”正确性。 一个关于网络通信的例子 Computer A Computer B far far away We want to verify the consistency between the two databases of size n (n=1016, say) located on A and B. For a deterministic answer, we may have to transfer a message of at least n bits, and (!) without an error on the way. It doesn’t look a pleasant task. 用随机的方法解决上述问题 将逐位比较改为比较两个整数x 和 y的值。 并不直接比较它们的值，而是采用以下方法： 计算 s = x mod p, (p 是一个质数) 计算 q = y mod p 通过比较 q 和 s 来判断 x 是否等于y 。 p 是在 [2, n2] 区间随机选择的质数。 协议描述 关于通信量 原来最坏情况下要传输 n 位信息。 现在只需要传输两个不大于n2的信息。每个信息的位数为： 假设 x = 011112 = 15; y = 101102 =22; n=5 PRIM(25) ={2, 3, 5, 7, 11, 13, 17, 19, 23}; ? ? 出错的概率有多大？ 关键是：能否证明这个概率很小？ 两个关于质数的结论 对任意n67, , 因此对任意n?9, 注意：如果x=y, 没有bad prime。 如何识别bad primes? 你能得出什么有用的结论吗？ Bad Primes数量的上限 显然： 你还记得“算术基本定理”吗？ 出错率大致的概念 *