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

《计算机问题求解-2013-04-02-概率分析与随机算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机问题求解–论题2-6-概率分析与随机算法2013年04月02日Histogramfor10flipsofacoin问题1:你能否结合这个图解释与随机变量相关的以下的概念:期望值、分布以及它们之间的关系？问题2：图中纵坐标值是怎么得出来的？Histogramforanswersfora10-problemtest贝努利试验过程：当k=8,问题3：这个算法是“确定”的吗？什么是“随机”的呢？Average-CaseAnalysisofAlgorithmsExpectedrunningtimevs.theworst-caserunningtime问题4：你能否描述一下对应于hiringp

2、roblem的问题空间以及分析算法所需要的随机变量？Worst-case是什么？需执行多少次hiring?IndicatorRandomVariable问题5：这句话是什么意思？Hiring-Assistant算法的平均情况分析涉及的随机变量：Hiring操作执行次数：X；事件“第i个候选人被雇用”的indicator：Xi;为什么？让随机“更随机”问题6：你还记得上次我们讨论条件概率时（掷两个色子，已知两个值一样）如何讨论到附加条件如何导致样本空间的变化的吗？又是通过什么方法来避免直接改变样本空间的呢？条件期望值将penny也纳入：引入条件期望值：若F=“Head”：若F=“Tail”

3、：X的期望值；这里n=2；P(F1)=P(F2)=0.5E(X)=(30+20)/2=25问题7：这个例子与我们前面遇到的概率试验过程有什么不同？随机算法相当于用抛硬币或者掷色子的方式决定下一步该干什么！问题8:这个算法还有“最坏情况”吗？生成序列的“随机”排列O(nlogn)O(n)对两个算法都必须回答同样的问题：是否得到任意可能的排列的机会是一样的(uniformlydistribution)?相交事件的概率对一个特别的排列，证明其概率是1/n!：第i个元素“权”恰好是第i个最小。用Ei表示对特定的i上述条件成立的事件，则要求的排列生成的概率是：按照条件概率的定义式，并利用归纳法加

4、以推广，上面的式子可以写为：于是：只要对上述的“最小”加以不同的解释，这个证明适用于任意排列！在by-sorting算法中依次将n个随机生成的“权”赋给各元素。利用循环不变式的归纳针对In-place算法可定义如下的不变式：考虑一个特定排列：如果第i次循环开始前，前i-1个元素恰好是x1,x2,…xi-1（事件E1)，定义事件E2：第i次循环恰好将xi放到了第i个位置。则生成上述排列的概率是：放在第i个位置的元素是在[i,n]中选的从n个元素中任选i个排列的种数的倒数。简单、高效是有代价的，所以随机算法经常用于那些“难”问题，牺牲“一点点”正确性。一个关于网络通信的例子Compute

5、rAComputerBfarfarawayWewanttoverifytheconsistencybetweenthetwodatabasesofsizen(n=1016,say)locatedonAandB.Foradeterministicanswer,wemayhavetotransferamessageofatleastnbits,and(!)withoutanerrorontheway.Itdoesn’tlookapleasanttask.用随机的方法解决上述问题将逐位比较改为比较两个整数x和y的值。并不直接比较它们的值，而是采用以下方法：计算s=xmodp,(p是一个质数)计

6、算q=ymodp通过比较q和s来判断x是否等于y。p是在[2,n2]区间随机选择的质数。协议描述问题8：你能看出这样做的好处吗？关于通信量原来最坏情况下要传输n位信息。现在只需要传输两个不大于n2的信息。每个信息的位数为：问题9：你觉得这个结果可靠吗？假设x=011112=15;y=101102=22;n=5PRIM(25)={2,3,5,7,11,13,17,19,23};出错的概率有多大？关键是：能否证明这个概率很小？两个关于质数的结论对任意n>67,,因此对任意n9,注意：如果x=y,没有badprime。如何识别badprimes?你能得出什么有用的结论吗？BadPrime

7、s数量的上限显然：你还记得“算术基本定理”吗？出错率大致的概念问题10:如果x,y确实相等,则没有“badprime”。这个结论对降低出错率有什么意义？问题11：经证明正确的确定算法不会出错吗？课外作业CSpp.340-:4,8CSpp.355-:1,2,4,6,12,16,18TCpp.122-:Ex.5.2-1,5.2-2,5.2-4TCpp.128-:Ex.5.3-1–Ex.5.3-4TCpp.143-:prob.5-2