总复习提纲：1．判断一个数a 是否为素数的算法，最多、一般情况下、至少要作多少次除法运算？要达到最少的次数应该附加什么？依据是什么（素数定义、性质(Th9.2.2)）P184、P185观察一正整数a 是否素数，要用小于a 大于1的整数一一来试除吗？不要。
定理9.2.2 若a 是大于1的整数，而所有小于或等于a 的素数都不能整除a ，则a 是素数。
令π(x )表示不超过x 的素数个数，可以证明0)(lim =+∞→xx x π 它表明了:尽管素数个数无穷多，但它比起正整数的个数来少得很多。
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 ∑-=12n i i i b =∑-=12)(n i i i ab计算过程：如下(核心思想：将ab i 当作一个整体，做平移，再做加法，而不是直接做乘法运算)首先注意在b i =1时ab i =a ，而b i =0时ab i =0。
每当用2乘一项时，结果都是把该项的二进制展开向左移一位并在尾部加上一个0，因此，可把ab i 的二进制展开向左移i 位，再在尾部加上i 个0来计算(ab i )2i 。
最后，将n 个整数(ab i )2i ，i =0，1，…，n -1，相加得到ab 。
两个正整数a 和b 二进制展开的乘法算法： mul (a ，b )for i← 0 to n-1if b i=1 then c i← a左移i位else c i← 0 //c0c1…c n-1是部分积p ← 0for i← 0 to n-1p ← p+c i//p是ab的值读者不难得出：移位个数是O(n2)，位加法个数是O(n2)，这是因为，所有n个整数(ab i)2i，i=0，1，…，n-1，需要0+1+2+…+n-1次移位，故移位数是O(n2)，而将(ab i)2i从i=0到i = n+1加起来，需要做一次n位整数、(n+1)位整数、…以及2n位整数的加法，这些加法都需要O(n)次位相加，因此完成所有n个数加法需要O(n2)次位加法。
4．最常用的产生伪随机数的方法是线性同余法。
P220它是递归定义的：x n+1=(ax n+c)(mod m) （1）U i=x n/m （2）其中，m称为模数，a为乘数，c为增量，x0为种数，且2≤a<m，0≤c<m，及0≤x0<m。
有时要求伪随机数为小数，为此使用x n/m。
分析此算法的特点：5．RSA公钥系统 P222RSA公钥系统是由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)=m e(mod n)解密算法D(c)=c d(mod n)6．最短路径算法 P3251959年，荷兰数学家E.W.Dijkstra给出了求某结点到其他各结点的最短链的一个标记算法。
Dijkstra标记算法：(1)令w(v i，v j)←∞，(v i，v j)∉E(G)l(u0)←0l(v)←∞，v≠u0S←{u0}i←0 //初始化标记(2)W hile v∉Sif l(u i)+w(u i，v)<l(v)then l(v)←l(u i)+w(u i，v)//更新不在S中结点的标记u i +1←min l (v ) 取最小值的且不属于S 中结点u i +1S ← S ∪{u i +1} //给S 中添加带最小标记的结点若i =n -1，算法结束；否则i ←i +1，转至(2)由上述算法知：① S 中各结点的标记l (u )即是从u 0到u 的距离。
又因n <∞，经有限步后，每个结点都标记了，从而得到了从u 0到各结点的最短链。
② 算法和时间复杂性是O (n 2)，所以是有效算法。
说明：1． 算法中的标记设计l (u )问题。
在算法的运行过程中，依次为各点作标记，当经历到此点时为它作一个标记，未经历到时，标记为∞。
标记的论据为min{ l (u i )+w (u i ，v ),l (v )}.当没有直接的边相连时，不作标记。
2． 提供了一个图的搜索算法，并且是对图的遍历算法，经过了图的所有点。
集合S 作为搜索结果的表示，其形成过程标记了下次的搜索方向的起点，u i +1←min l (v ) S ← S ∪{u i +1}搜索方向的边为(u i ，v )且v ∉S ，随着搜索过程的进行，S 中的元素渐渐增多，当然不属于S 的元素渐渐减少。
当所有的点都加入到其中时算法结束。
3． S 中的元素是有序的，唯一么？什么情况下不唯一？ 形成了一棵树。
对图的点进行了排列(其结果为一个偏序)。
v 5v 3v 4v 2v 1v 012108542367．关键路算法 P326关键路是通过求事件的最早期望完成时间和事件的最迟必须完成时间来实现的，为此定义：π+(v )={x |x ∈V ∧<v ，x >∈E } π-(v )={x |x ∈V ∧<x ，v >∈E }。
分别称π+(v )和π-(v )为结点v 的后继结点集合和v 的先驱结点集合。
① 最早期望完成时间从始点开始沿着最长路到达v i 所需时间，称为v i 的最早期望完成时间，记为TE (v i )，i =1.2，…，n 。
于是 TE (v 1)=0TE (v i )=)(max i j v v -∈π{TE (v j )+w ji } i =2，3，…，n ②最迟必须完成时间在保证终点v n 的最早期望完成时间TE (v n )不增加前提下，自始点v 1最迟到达v i 的时间，称为v i 的最迟必须完成时间，记为TL (v i )。
TL (v n )=TE (v n )TL (v i )=)(m in i j v v +∈π{TL (v j )-w ij } i =1，2，…，n -1③松驰时间TS (v i )=TL (v i )-TE (v i ) i =1，2，…，n 显然，TS (v i )≥0，i =1，2，…，n关键路上的各结点的松驰时间均为0，即由松驰时间为0的结点构成关键路，因为任何工序延误了时间，整个工程项目就延误了时间。
算法的复杂性是O (n )。
4v v 68．已知简单有向图G =<V ，E >如图16.4.3所示，G 的邻接矩阵A 是 P331A =⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡010001000000010001010001试求A 1，A 2，A 3，A 4，A 5。
并说明A 4中各非0元素的含义。
3v 5图16.4.39．设图G 的邻接矩阵A 是 P335A =⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0001101111000010 试求G 的可达矩阵P 。
10． 请描述：什么是代数结构？什么是半群、独异点、群？11． 请描述什么是代数结构之间的同态？对于代数结构V1 =<Z,＋>, V2 =<Zn,⊕>,其中＋为普通加法,⊕为模n 加法,即∀x,y ∈Zn 有 x ⊕y=(x ＋y)mod n,这里Zn={0,1,…,n-1}．假设给定映射ϕ :Z →Zn, ϕ (x)= (x)mod n, V2是否是V1的同态象？（验证ϕ (x ＋y)= ϕ(x) ⊕ ϕ (y)）12． 给定独异点<G , *>，G={1, a, b, c}，*定义如下：，请问，该独异点是否是循环独异点？13．请描述什么是一个群的子群？设<G, *>是一个群，对任意的a∈G，令S = {a n | n∈Z，Z是整数}，证明<S, *>是G的子群。
分析使用定理13.6.3来证明。
证明：显然S非空。
对∀x, y∈S，则存在n, m∈Z，x = a n，y = a m，则x*y-1 = a n* (a m)-1 = a n-m，且n-m∈Z，所以x*y-1 = a n-m∈S，故由定理13.6.3可得，<S, *>是<G, *>的子群。
14．对于三次对称群<S3,◇>，其中运算◇定义如下：证明：<G={P1, P5, P6}，◇>是<S3,◇>的子群，并计算该子群所确定的所有左陪集和右陪集，给出这些陪集形成的等价类。
证明该陪集关系是同余关系。
（使用定理13.6.4证明子群，参考课件上此陪集的计算结果，同余关系的证明可以利用定理证明aH=Ha，进而得到该子群是正规子群，正规子群的陪集关系是同余关系得到）。