算法设计与分析黄刘生中国科学技术大学计算机系国家高性能.ppt

算法设计与分析黄刘生中国科学技术大学计算机系国家高性能计算中心（合肥）2008.8.191第一部分概率算法2Ch.1 绪论1. 故事：想象自己是神化故事的主人公， 你有一张不易懂的地图，上面描述了一 处宝藏的藏宝地点经分析你能确定最 有可能的两个地点是藏宝地点，但二者 相距甚远假设你如果已到达其中一处 ，就立即知道该处是否为藏宝地点你 到达两处之一地点及从其中一处到另一 处的距离是5天的行程进一步假设有一 条恶龙，每晚光顾宝藏并从中拿走一部 分财宝假设你取宝藏的方案有两种：§1.1 引言3方案1. 花4天的时间计算出准确的藏宝地点， 然后出发寻宝，一旦出发不能重新计算方案2. 有一个小精灵告诉你地图的秘密，但你 必须付给他报酬，相当于龙3晚上拿走的财宝Prob 1.1.1 若忽略可能的冒险和出发寻宝的代 价，你是否接受小精灵的帮助？显然，应该接受小精灵的帮助，因为你只 需给出3晚上被盗窃的财宝量，否则你将失去4 晚被盗财宝量但是，若冒险，你可能做得更好！§1.1 引言4设x是你决定之前当日的宝藏价值，设y是恶龙每 晚盗走的宝藏价值，并设x>9y方案1：4天计算确定地址，行程5天，你得到的 宝藏价值为：x-9y方案2：3y付给精灵，行程5天失去5y，你得到的 宝藏价值为：x-8y方案3：投硬币决定先到一处，失败后到另一处( 冒险方案)一次成功所得：x-5y，机会1/2二次成功所得：x-10y，机会1/2§1.1 引言}期望赢利：x-7.5y52. 意义该故事告诉我们：当一个算法面临某种选择 时，有时随机选择比耗时做最优选择更好，尤其 是当最优选择所花的时间大于随机选择的平均时 间的时侯显然，概率算法只能是期望的时间更有效， 但它有可能遭受到最坏的可能性。

63. 期望时间和平均时间的区别v确定算法的平均执行时间输入规模一定的所有输入实例是等概率出现时，算 法的平均执行时间v概率算法的期望执行时间反复解同一个输入实例所花的平均执行时间因此，对概率算法可以讨论如下两种期望时间n平均的期望时间：所有输入实例上平均的期望执行时 间n最坏的期望时间：最坏的输入实例上的期望执行时间74. 例子n 快速排序中的随机划分要求学生写一算法，由老师给出输入实例，按运行时间打分， 大部分学生均不敢用简单的划分，运行时间在1500-2600ms ，三个学生用概率的方法划分，运行时间平均为300msn 8皇后问题系统的方法放置皇后(回溯法)较合适，找出所有92个解 O(2n) ，若只找92个其中的任何一个解可性时间内完成O(n)随机法：随机地放置若干皇后能够改进回溯法，特别是当n 较大时n 判断大整数是否为素数确定算法无法在可行的时间内判断一个数百位十进制数是否素 数，否则密码就不安全概率算法将有所作为：若能接受一个任意小的错误的概率85. 概率算法的特点(1) 不可再现性在同一个输入实例上，每次执行结果不尽相同， 例如nN-皇后问题概率算法运行不同次将会找到不同的正确解n找一给定合数的非平凡因子每次运行的结果不尽相同，但确定算法每次运行结果必 定相同(2) 分析困难要求有概率论，统计学和数论的知识96. 约定随机函数uniform：随机，均匀，独立n设a，b为实数，a0 do { if (j is odd) s ← s·a mod p; a ← a2 mod p; j ← j div 2; } return s; }Draw (a, p) { // 在X中随机取一元素 j ← uniform(1p-1); return ModularExponent(a, j, p); // 在X中随机取一元素 }12n 伪随机数发生器 在实用中不可能有真正的随机数发生器，多数情况 下是用伪随机数发生器代替。

大多数伪随机数发生器是基于一对函数： S: X → X, 这里X足够大，它是种子的值域 R: X → Y, Y是伪随机数函数的值域 使用S获得种子序列：x0=g, xi=S(xi-1), i>0 然后使用R获得伪随机序列：yi=R(xi), i ≥ 0 该序列必然是周期性的，但只要S和R选的合适，该 周期长度会非常长 TC中可用rand()和srand(time), 用GNU C更好13n 基本特征随机决策在同一实例上执行两次其结果可能不同在同一实例上执行两次的时间亦可能不太相同n 分类Numerical, Monte Carlo, Las Vegas, Sherwood.很多人将所有概率算法(尤其是数字的概率算法) 称为Monte Carlo算法§1.2 概率算法的分类14n数字算法 随机性被最早用于求数字问题的近似解 例如，求一个系统中队列的平均长度的问题，确定算法很 难得到答案 • 概率算法获得的答案一般是近似的，但通常算法执行的时 间越长，精度就越高，误差就越小 • 使用的理由 –现实世界中的问题在原理上可能就不存在精确解 例如，实验数据本身就是近似的，一个无理数在计算机 中只能近似地表示 –精确解存在但无法在可行的时间内求得 有时答案是以置信区间的形式给出的§1.2 概率算法的分类15nMonte Carlo算法 (MC算法) 蒙特卡洛算法1945年由J. Von Neumann进行核武模拟提出 的。

它是以概率和统计的理论与方法为基础的一种数值计算方 法，它是双重近似：一是用概率模型模拟近似的数值计算，二 是用伪随机数模拟真正的随机变量的样本 这里我们指的MC算法是： 若问题只有1个正确的解，而无近 似解的可能时使用MC算法 例如，判定问题只有真或假两种可能性，没有近似解因式分解，我们不能说某数几乎是一个因子 n特点：MC算法总是给出一个答案，但该答案未必正确，成 功(即答案是正确的)的概率正比于算法执行的时间n缺点：一般不能有效地确定算法的答案是否正确§1.2 概率算法的分类16nLas Vegas算法 (LV算法) LV算法绝不返回错误的答案n特点：获得的答案必定正确，但有时它仍根本就找不 到答案和MC算法一样，成功的概率亦随算法执行时间增加而 增加无论输入何种实例，只要算法在该实例上运行足 够的次数，则算法失败的概率就任意小 ④ Sherwood算法 Sherwood算法总是给出正确的答案 当某些确定算法解决一个特殊问题平均的时间比最坏时 间快得多时，我们可以使用Sherwood算法来减少，甚 至是消除好的和坏的实例之间的差别§1.2 概率算法的分类17这类算法主要用于找到一个数字问题的近似解 §2.1 π值计算 n 实验：将n根飞镖随机投向一正方形的靶子，计算落入此正方 形的内切圆中的飞镖数目k。

假定飞镖击中方形靶子任一点的概率相等(用计算机模拟比任 一飞镖高手更能保证此假设成立) 设圆的半径为r，面积s1= πr2； 方靶面积积s2=4r2 由等概率假设可知落入圆中的飞镖和正方形内的飞镖平均比为 ：由此知：Ch.2 数字概率算法18n 求π近似值的算法 为简单起见，只以上图的右上1/4象限为样本 Darts (n) { k ← 0; for i ← 1 to n do { x ← uniform(0, 1); y ← uniform(0, 1); // 随机产生点(x,y) if (x2 + y2 ≤ 1) then k++; //圆内 } return 4k/n; } 实验结果： π=3.141592654 n = 1000万: 3.140740, 3.142568 (2位精确) n = 1亿亿: 3.141691, 3.141363 (3位精确) n = 10亿亿: 3.141527, 3.141507 (4位精确)§2.1 π值计算19n 求π近似值的算法 Ex.1 若将y ← uniform(0, 1) 改为 y ← x, 则上 述的算法估计的值是什么？§2.1 π值计算20Monte Carlo积分(但不是指我们定义的MC算法) n 概率算法1 设f: [0, 1] → [0, 1]是一个连续函数，则由曲线y=f(x), x 轴, y轴和直线x=1围成的面积由下述积分给出：向单位面积的正方形内投镖n次，落入阴影部分的镖的 数目为k，则显然，只要n足够大§2.2 数字积积分 (计计算定积积分的值值)21n 概率算法1 HitorMiss (f, n) { k ← 0; for i ← 1 to n do { x ← uniform(0, 1); y ← uniform(0, 1);if y ≤ f(x) then k++; } return k/n; } Note: 是S/4的面积，∵ π =S, ∴§2.2 数字积积分 (计计算定积积分的值值)22n 概率算法1 Ex2. 在机器上用 估计π值值，给给出不 同的n值值及精度。

Ex3. 设设a, b, c和d是实实数，且a ≤ b, c ≤ d, f:[a, b] → [c, d]是一个连续连续 函数，写一概率算法计计 算积积分：注意，函数的参数是a, b, c, d, n和f, 其中f用函 数指针实现针实现 ，请选请选 一连续连续 函数做实验实验 ，并给给 出实验结实验结 果§2.2 数字积积分 (计计算定积积分的值值)23n 概率算法1 *Ex4. 设ε,δ是(0,1)之间的常数，证明：若I是 的正确值，h是由HitorHiss算法返回的 值，则当n ≥ I(1-I)/ε2δ时有： Prob[|h-I| T[j];}}§3.2 随机的预处预处 理51例2：离散对数计算• 离散对数计算困难使其可用于密码算法，数字签名等 • 定义：设 a=gx mod p，记 logg,pa=x，称x为a的(以g为底模除p)对数从p，g，a计算x称为离散对数问题• 简单算法： ① 计算gx对所有的x，最多计算0≤x≤ p-1 或 1≤x≤p，因为实际上离散 对数是循环群；② 验证a=gx mod p 是否成立dlog(g, a, p) { // 当这样的对数不存在时，算法返回px ← 0; y ← 1;do { x++;y ← y*g; // 计算y=gx} while ( a ≠ y mod p) and (x ≠ p);return x}§3.2 随机的预处预处 理52• 问题：最坏O(p)循环次数难以预料，当满足一定条件时平均循环p/2次当p=24位十进制数，循环1024次，千万亿次/秒 (1016次/秒) 大约算1 年(108秒/年)若p是数百位十进制？随机选择都可能无法在可行的时间内求解。

• 假设有一个平均时间性能很好，但最坏情况差的确定算法求logp,ga ，怎样用Sherwood算法求解该问题？设p=19, g=2当a=14, 6时，log2,1914 = 7, log2,196=14，即用dlog求14和6的离散 对数时，分别要循环7和14次，执行时间与a的取值相关用sherwood算法应该使得与a无关，用随机预处理的方法计算 logg,pa§3.2 随机的预处预处 理53• 定理(见p877, § 31.6)① ②dlogRH(g, a p) { // 求logg,pa, a = gx mod p，求x// Sherwood算法r ← uniform(0p-2);b ← ModularExponent(g, r, p); //求幂模b=gr mod pc ← ba mod p; //((gr modp)(gxmodp))modp=gr+xmodp=cy ← logg,pc; // 使用确定性算法求logp,gc, y=r+xreturn (y-r) mod (p-1); // 求x}Ex. 分析dlogRH的工作原理，指出该算法相应的u和v§3.2 随机的预处预处 理54• 随机预处理提供了一种加密计算的可能性假定你想计算某个实例x，通过f(x)计算，但你缺乏 计算能力或是缺乏有效算法，而别人有相应的计算能力 ，愿意为你。