内容发布更新时间 : 2024/12/27 20:09:25星期一 下面是文章的全部内容请认真阅读。
总复习提纲：
1． 判断一个数a是否为素数的算法，最多、一般情况下、至少要作多少次除法运算？要达
到最少的次数应该附加什么？依据是什么（素数定义、性质(Th9.2.2)）P184、P185 观察一正整数a是否素数，要用小于a大于1的整数一一来试除吗？不要。 定理9.2.2 若a是大于1的整数，而所有小于或等于a的素数都不能整除a，则a是素数。
令π(x)表示不超过x的素数个数，可以证明
x???lim?(x)x?0
它表明了:尽管素数个数无穷多，但它比起正整数的个数来少得很多。 2． 欧几里德算法思想及时间复杂度问题？P201
本质上是用辗转相除把求两个正整数最大公因数的问题化为求两个较小整数的最大公因数，直到两个整数中的一个为0。
现将定理9.3.2欧几里德算法以伪码形式给出如下： Euclid(a，b：整数) if b=0 then return a while b>0
{ r←a(mod b) a←b b←r } return a
算法中过程的每一步都是a用b代替，而b用a(mod b)代替。只要b>0，这个过程就重复下去，当b=0时算法终止，此时a的值也就是这一过程的非零余数，即为a和b的最大公因数。
在欧几里德算法中基本操作是除法，为研究欧几里德算法的时间复杂性，需要求出算法中所使用的除法次数，下面拉梅定理给出解答。 证明：如下定理
定理10.2.1 设a和b是满足a≥b的正整数，则欧几里德算法求得(a，b)而使用除法的次数小于或等于b的十进制位数的5倍。
3． 两个n位的二进制整数a和b的乘法算法 P204
可按下面等式进行计算：
ab=a?bi2=?(abi)2i
i?0i?0n?1in?1计算过程：如下(核心思想：将abi当作一个整体，做平移，再做加法，而不是直接做乘法运算)
首先注意在bi=1时abi=a，而bi=0时abi=0。每当用2乘一项时，结果都是把该项的二进制展开向左移一位并在尾部加上一个0，因此，可把abi的二进制展开向左移i位，再在尾部加上i个0来计算(abi)2i。最后，将n个整数(abi)2i，i=0，1，…，n-1，相加得到ab。
两个正整数a和b二进制展开的乘法算法： mul(a，b)
for i← 0 to n-1
if bi=1 then ci← a左移i位
else ci← 0 //c0c1…cn-1是部分积
1 / 5
p ← 0
for i← 0 to n-1
p ← p+ci //p是ab的值
读者不难得出：移位个数是O(n2)，位加法个数是O(n2)，这是因为，所有n个整数(abi)2i，i=0，1，…，n-1，需要0+1+2+…+n-1次移位，故移位数是O(n2)，而将(abi)2i从i=0到i = n+1加起来，需要做一次n位整数、(n+1)位整数、…以及2n位整数的加法，这些加法都需要O(n)次位相加，因此完成所有n个数加法需要O(n2)次位加法。
4． 最常用的产生伪随机数的方法是线性同余法。P220
它是递归定义的：
xn+1=(axn+c)(mod m) （1） Ui=xn/m （2）
其中，m称为模数，a为乘数，c为增量，x0为种数，且2≤a 分析此算法的特点： 5． RSA公钥系统 P222 RSA公钥系统是由MIT的三名研究人员：瑞弗斯特(Ron Rivest)、沙米尔(Adi Sharmir)和阿德莱门(Len Adleman)于1978年联合提出的，它的安全性是基于大整数因数分解困难问题，至今没有有效的算法。 RSA加密算法的过程： ① 选取两素数p和q(保密) ② 计算n = pq(公开)，φ(n)=(p-1)(q-1)(保密) ③ 选取加密公钥e，满足(e，φ(n))=1 ④ 计算解密私钥d，满足de≡1(modφ(n)) 使用RSA加密之前，应将明文数字化，并取长度小于log n位的数字作为明文块。 加密算法 c=E(m)=me(mod n) 解密算法 D(c)=cd(mod n) 6． 最短路径算法 P325 1959年，荷兰数学家E.W.Dijkstra给出了求某结点到其他各结点的最短链的一个标记算法。 Dijkstra标记算法： (1) 令w(vi，vj)← ∞，(vi，vj)?E(G) l(u0)←0 l(v)←∞，v≠u0 S←{u0} i←0 //初始化标记 (2) While v?S if l(ui)+w(ui，v) then l(v)←l(ui)+w(ui，v) //更新不在S中结点的标记 ui+1←min l(v) 取最小值的且不属于S中结点ui+1 S ← S∪{ui+1} //给S中添加带最小标记的结点 若i=n-1，算法结束；否则i←i+1，转至(2) 由上述算法知： ① S中各结点的标记l(u)即是从u0到u的距离。又因n<∞，经有限步后，每个结点都 2 / 5 标记了，从而得到了从u0到各结点的最短链。 ② 算法和时间复杂性是O(n2)，所以是有效算法。 说明： 1． 算法中的标记设计l(u)问题。在算法的运行过程中，依次为各点作标记，当经历到 此点时为它作一个标记，未经历到时，标记为∞。标记的论据为 min{ l(ui)+w(ui，v),l(v)}. 当没有直接的边相连时，不作标记。 2． 提供了一个图的搜索算法，并且是对图的遍历算法，经过了图的所有点。集合S 作为搜索结果的表示，其形成过程标记了下次的搜索方向的起点， ui+1←min l(v) S ← S∪{ui+1} 搜索方向的边为(ui，v)且v?S，随着搜索过程的进行，S中的元素渐渐增多，当然不属于S的元素渐渐减少。当所有的点都加入到其中时算法结束。 3． S中的元素是有序的，唯一么？什么情况下不唯一？ 形成了一棵树。对图的点进行了排列(其结果为一个偏序)。 v14v0210v2v418235v36v5 7． 关键路算法 P326 关键路是通过求事件的最早期望完成时间和事件的最迟必须完成时间来实现的，为此定义： ?+(v)={x|x∈V? -分别称?+(v)和?(v)为结点v的后继结点集合和v的先驱结点集合。 ① 最早期望完成时间 从始点开始沿着最长路到达vi所需时间，称为vi的最早期望完成时间，记为TE(vi)， i=1.2，…，n。于是 TE(v1)=0 TE(vi)=max?vj??(vi){TE(vj)+wji} i=2，3，…，n ②最迟必须完成时间 在保证终点vn的最早期望完成时间TE(vn)不增加前提下，自始点v1最迟到达vi的时间，称为vi的最迟必须完成时间，记为TL(vi)。 TL(vn)=TE(vn) TL(vi)= vj??min?(vi){TL(vj)-wij} i=1，2，…，n-1 ③松驰时间 TS(vi)=TL(vi)-TE(vi) i=1，2，…，n 显然，TS(vi)≥0，i=1，2，…，n 关键路上的各结点的松驰时间均为0，即由松驰时间为0的结点构成关键路，因为任何工序延误了时间，整个工程项目就延误了时间。 算法的复杂性是O(n)。 3 / 5