数值概率算法PPT学习教案

1、会计学1 数值概率算法数值概率算法 随机数在概率算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都是一定程度上随机的，即伪随机数。 线性同余法是产生伪随机数的最常用的方法。由线性同余法产生的随机序列a0,a1,an满足 , 2 , 1mod)( 1 0 nmcbaa da nn 其中b0，c0，dm。d称为该随机序列的种子。如何选取该方法中的常数b、c和m直接关系到所产生的随机序列的随机性能。这是随机性理论研究的内容，已超出本书讨论的范围。从直观上看，m应取得充分大，因此可取m为机器大数，另外应取gcd(m,b)=1，因此可取b为一素数。 第1页

2、/共17页 设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布，因而所投入的点落入圆内的概率为 。所以当n足够大 时，k与n之比就逼近这一概率。从而 。 44 2 2 r r n k4 public static double darts(int n) / 用随机投点法计算值 int k=0; for (int i=1;i =n;i+) double x=dart.fRandom(); double y=dart.fRandom(); if (x*x+y*y)=1) k+; return 4*k/(double)n; 第2页/共

3、17页 设f(x)是0，1上的连续函数，且0f(x)1。 需要计算的积分为 , 积分I等于图中的面积G。 1 0 )(dxxfI 在图所示单位正方形内均匀地作投点试验，则随机点落在曲线下面的概率为 假设向单位正方形内随机地投入n个点(xi,yi)。如果有m个点落入 G内，则随机点落入G内的概率 1 0 )( 0 1 0 )()( xf r dxxfdydxxfyP n m I 第3页/共17页 第4页/共17页 第5页/共17页 解释一：把解释一：把RAMRAM程序看成是计算一个函数程序看成是计算一个函数 若一个RAM程序P总是从输入带前n个方格中读入n个整数 x1，x2，xn，并且在输出带的

4、第一个方格上输出一个整数y 后停机，那么就说程序P计算了函数f(xf(x1 1，x x2 2，x xn n)=y )=y 第6页/共17页 解释二：把解释二：把RAMRAM程序当作一个语言接受器。程序当作一个语言接受器。 将字符串S=a1a2an放在输入带上。在输入带的第一个方 格中放入符号a1，第二个方格中放入符号a2，第n个方格中 放入符号an。然后在第n+1个方格中放入0，作为输入串的结束标 志符。如果一个RAM程序P读了字符串S及结束标志符0后，在输出 带的第一格输出一个1并停机，就说程序P接受字符串S。 第7页/共17页 标准一：均匀耗费标准标准一：均匀耗费标准 在均匀耗费标准下，每

5、条RAM指令需要一个单位时间；每 个寄存器占用一个单位空间。以后除特别注明，RAM程序的复杂 性将按照均匀耗费标准衡量。 标准二：对数耗费标准标准二：对数耗费标准 对数耗费标准是基于这样的假定，即执行一条指令的耗费 与以二进制表示的指令的操作数长度成比例。在RAM计算模型下， 假定一个寄存器可存放一个任意大小的整数。因此若设l(i)是整 数i所占的二进制位数，则 0 0 1 |log )( i ii il 第8页/共17页 第9页/共17页 在RRAM模型下，一个存储单元可以存放一个实数。下列的各 运算为基本运算且每个运算只耗费单位时间。 (1)算术运算+，。 (2)2个实数间的比较()。 (

6、3)间接寻址(整数地址)。 (4)常见函数的计算，如三角函数，指数函数，对数函数等。 优点：能够方便处理实数； 适合于用FORTRAN，PASCAL等高级语言写的算法。 第10页/共17页 对于许多问题，所设计的RAM程序中的转移指令仅用于重复 一组指令，而且重复的次数与问题的输入规模n成比例。在这种情 况下，可以用重复地写出相同指令组的方法来消除程序中的循环。 由此，对每一个固定的n得到一个无循环的直线式程序。 经过对RAM模型的简化，得到直线式程序的指令系统如下： xy+z xy-z xy*z xy/z xi 其中x，y和z是符号地址(或变量)，而i是常数。 每条指令耗费一个单位时间。每条

7、指令耗费一个单位时间。 第11页/共17页 直线式程序计算模型显然是基于均匀耗费标准的。在对数 耗费标准下，使用另一个RAM的简化计算模型，称之为位式计算 (Bitwise Computation)模型。 除了下列2点外，该计算模型与直线式程序计算模型基本 相同： (1)假设所有变量取值0或1，即为位变量。 (2)所用的运算是逻辑运算而不是算术运算。 用代表与，代表或，代表异或，代表非。 在位式计算模型下，每个逻辑运算指令耗费一个单位时间。在位式计算模型下，每个逻辑运算指令耗费一个单位时间。 第12页/共17页 若在直线式程序计算模型中，假设所有变量均为位向量，而 且所用的运算均为位操作指令，

8、则得到位向量运算计算模型。 例如，要表示一个有100个顶点的图中从顶点v到其余各顶点 间有没有边相连，可以用100位的一个位向量表示。若顶点v到顶 点vj之间有边相连，则该位向量的第j位为1，否则为0。 缺点：所需的机器字长要远大于其他模型。 第13页/共17页 判定树是一棵二叉树。它的每个内结点表示一个形如xy的 比较。指向该结点左儿子的边相应于xy，标号为。指向该结 点右儿子的边相应于xy，标号为。每一次比较耗费一个单位时 间。下图是对a，b，c三个数进行排序的一棵判定树。 在判定树模型下在判定树模型下 ，算法的时间复，算法的时间复 杂性可用判定树杂性可用判定树 的高度衡量。最的高度衡量。

9、最 大的比较次数是大的比较次数是 从根到叶的最长从根到叶的最长 路径的长度。路径的长度。 第14页/共17页 以x=(x1，x2，xn)为输入的一棵代数计算树T是一棵 二叉树，且： (1)每个叶结点表示一个输出结果YES或NO。 (2)每个单儿子内部结点(简单结点)v表示下列形式运算指令： op 或 op 或 其中， 和 分别是结点v在树T中的祖先结点v1和v2处得到 的结果值，或是x的分量；op+，/；c是一个常数。 (3)每个有2个儿子的内部结点(分支结点)v，表示下列形式的 测试指令： 0或 0或 =0 其中， 是结点v在树T中的祖先结点v1处得到的结果值，或是 x的分量。 1 vv ff 2v f cf v 1v f 1vv ff 1v f 2v f 1v f 1v f 1v f 1v f 第15页/共17页 在代数计算树T中，若将所有的简单结点都压缩到其最近 的子孙分支结点处，并将简单结点处的计算在压缩后的分支结点 处同时完成，则计算结果可看作是输入