离散数学期末复习题VIP

总复习提纲：判断一个数a是否为素数的算法，最多、一般情况下、至少要作多少次除法运算？要达到最少的次数应该附加什么？依据是什么（素数定义、性质(Th9.2.2)）P184、P185观察一正整数a是否素数，要用小于a大于1的整数一一来试除吗？不要。定理9.2.2若a是大于1的整数，而所有小于或等于的素数都不能整除a，则a是素数。令π(x)表示不超过x的素数个数，可以证明它表明了:尽管素数个数无穷多，但它比起正整数的个数来少得很多。欧几里德算法思想及时间复杂度问题？P201本质上是用辗转相除把求两个正整数最大公因数的问题化为求两个较小整数的最大公因数，直到两个整数中的一个为0。现将定理9.3.2欧几里德算法以伪码形式给出如下：Euclid(a，b：整数)ifb=0thenreturnawhileb>0{r←a(modb)a←bb←r}returna算法中过程的每一步都是a用b代替，而b用a(modb)代替。只要b>0，这个过程就重复下去，当b=0时算法终止，此时a的值也就是这一过程的非零余数，即为a和b的最大公因数。在欧几里德算法中基本操作是除法，为研究欧几里德算法的时间复杂性，需要求出算法中所使用的除法次数，下面拉梅定理给出解答。证明：如下定理定理10.2.1设a和b是满足a≥b的正整数，则欧几里德算法求得(a，b)而使用除法的次数小于或等于b的十进制位数的5倍。两个n位的二进制整数a和b的乘法算法P204可按下面等式进行计算：ab=a=计算过程：如下(核心思想：将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)fori←0ton-1ifbi=1thenci←a左移i位elseci←0//c0c1…cn-1p←0fori←0ton-1p←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)次位加法。最常用的产生伪随机数的方法是线性同余法。P220它是递归定义的：xn+1=(axn+c)(modm)（1）Ui=xn/m（2）其中，m称为模数，a为乘数，c为增量，x0为种数，且2≤a<m，0≤c<m，及0≤x0<m。有时要求伪随机数为小数，为此使用xn/m。分析此算法的特点：RSA公钥系统P222RSA公钥系统是由MIT的三名研究人员：瑞弗斯特(RonRivest)、沙米尔(AdiSharmir)和阿德莱门(LenAdleman)于1978年联合提出的，它的安全性是基于大整数因数分解困难问题，至今没有有效的算法。RSA加密算法的过程：①选取两素数p和q(保密)②计算n=pq(公开)，φ(n)=(p-1)(q-1)(保密)③选取加密公钥e，满足(e，φ(n))=1④计算解密私钥d，满足de≡1(modφ(n))使用RSA加密之前，应将明文数字化，并取长度小于logn位的数字作为明文块。加密算法c=E(m)=me(modn)解密算法D(c)=cd(modn)最短路径算法P3251959年，荷兰数学家E.W.Dijkstra给出了求某结点到其他各结点的最短链的一个标记算法。Dijkstra标记算法：令w(vi，vj)←∞，(vi，vj)E(G)l(u0)←0l(v)←∞，v≠u0S←{u0}i←0//初始化标记WhilevSifl(ui)+w(ui，v)<l(v)thenl(v)←l(ui)+w(ui，v)//更新不在S中结点的标记ui+1←minl(v)取最小值的且不属于S中结点ui+1S←S∪{ui+1}//给S中添加带最小标记的结点若i=n-1，算法结束；否则i←i+1，转至(2)由上述算法知：①S中各结点的标记l(u)即是从u0到u的距离。又因n<∞，经有限步后，每个结点都标记了，从而得到了从u0到各结点的最短链。②算法和时间复杂性是O(n2)，所以是有效算法。说明：算法中的标记设计l(u)问题。在算法的运行过程中，依次为各点作标记，当经历到此点时为它作一个标记，未经历到时，标记为∞。标记的论据为min{l(ui)+w(ui，v),l(v)}.当没有直接的边相连时，不作标记。提供了一个图的搜索算法，并且是对图的遍历算法，经过了图的所有点。集合S作为搜索结果的表示，其形成过程标记了下次的搜索方向的起点，ui+1←minl(v)S←S∪{ui+1}搜索方向的边为(ui，v)且vS，随着搜索过程的进行，S中的元素渐渐增多，当然不属于S的元素渐渐减少。当所有的点都加入到其中时算法结束。S中的元素是有序的，唯一么？什么情况下不唯一？形成了一棵树。对图的点进行了排列(其结果为一个偏序)。关键路算法P326关键路是通过求事件的最早期望完成时间和事件的最迟必须完成时间来实现的，为此定义：+(v)={x|x∈V<v，x>∈E}-(v)={x|x∈V<x，v>∈E}。分别称+(v)和-(v)为结点v的后继结点集合和v的先驱结点集合。最早期望完成时间从始点开始沿着最长路到达vi所需时间，称为vi的最早期望完成时间，记为TE(vi)，i=1.2，…，n。于是TE(v1)=0TE(vi)={TE(vj)+wji}i=2，3，…，n②最迟必须完成时间在保证终点vn的最早期望完成时间TE(vn)不增加前提下，自始点v1最迟到达vi的时间，称为vi的最迟必须完成时间，记为TL(vi)。TL(vn)=TE(vn)TL(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)。已知简单有向图G=<V，E>如图16.4.3所示，G的邻接矩阵A是P331A=试求A1，A2，A3，A4，A5。并说明A4中各非0元素的含义。图16.4.3设图G的邻接矩阵A是P335A=试求G的可达矩阵P。请描述：什么是代数结构？什么是半群、独异点、群？请描述什么是代数结构之间的同态？对于代数结构V1=<Z,＋>,V2=<Zn,Å>,其中＋为普通加法,Å为模n加法,即"x,yÎZn有xÅy=(x＋y)modn,这里Zn={0,1,…,n-1}．假设给定映射j:Z→Zn,j(x)=(x)modn,V2是否是V1的同态象？（验证j(x＋y)=j(x)Åj(y)）给定独异点<G,*>，G={1,a,b,c}，*定义如下：，请问，该独异点是否是循环独异点？请描述什么是一个群的子群？

设<G,*>是一个群，对任意的a∈G，令S={an|n∈Z，Z是整数}，证明<S,*>是G的子群。分析使用定理13.6.3来证明。证明：显然S非空。对"x,y∈S，则存在n,m∈Z，x=an，y=am，则x*y-1=an*(am)-1=an-m，且n-m∈Z，所以x*y-1=an-m∈S，故由定理13.6.3可得，<S,*>是<G,*>的子群。