離散數學期末復習題

總復習提綱：判斷一個數a是否為素數的算法，最多、一般情況下、至少要作多少次除法運算？要達到最少的次數應該附加什么？依據是什么（素數定義、性質(Th9.2.2)）P184、P185觀察一正整數a是否素數，要用小于a大于1的整數一一來試除嗎？不要。定理9.2.2若a是大于1的整數，而所有小于或等于的素數都不能整除a，則a是素數。令π(x)表示不超過x的素數個數，可以證明它表明了:盡管素數個數無窮多，但它比起正整數的個數來少得很多。歐幾里德算法思想及時間復雜度問題？P201本質上是用輾轉相除把求兩個正整數最大公因數的問題化為求兩個較小整數的最大公因數，直到兩個整數中的一個為0。現(xiàn)將定理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公鑰系統(tǒng)P222RSA公鑰系統(tǒng)是由MIT的三名研究人員：瑞弗斯特(RonRivest)、沙米爾(AdiSharmir)和阿德萊門(LenAdleman)于1978年聯(lián)合提出的，它的安全性是基于大整數因數分解困難問題，至今沒有有效的算法。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關鍵路是通過求事件的最早期望完成時間和事件的最遲必須完成時間來實現(xiàn)的，為此定義：+(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。請描述：什么是代數結構？什么是半群、獨異點、群？請描述什么是代數結構之間的同態(tài)？對于代數結構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的同態(tài)象？（驗證j(x＋y)=j(x)?j(y)）給定獨異點<G,*>，G={1,a,b,c}，*定義如下：，請問，該獨異點是否是循環(huán)獨異點？請描述什么是一個群的子群？

設<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,*>的子群。