離散數(shù)學(xué)期末復(fù)習(xí)題

總復(fù)習(xí)提綱：判斷一個數(shù)a是否為素數(shù)的算法，最多、一般情況下、至少要作多少次除法運算？要達(dá)到最少的次數(shù)應(yīng)該附加什么？依據(jù)是什么（素數(shù)定義、性質(zhì)(Th9.2.2)）P184、P185觀察一正整數(shù)a是否素數(shù)，要用小于a大于1的整數(shù)一一來試除嗎？不要。定理9.2.2若a是大于1的整數(shù)，而所有小于或等于的素數(shù)都不能整除a，則a是素數(shù)。令π(x)表示不超過x的素數(shù)個數(shù)，可以證明它表明了:盡管素數(shù)個數(shù)無窮多，但它比起正整數(shù)的個數(shù)來少得很多。歐幾里德算法思想及時間復(fù)雜度問題？P201本質(zhì)上是用輾轉(zhuǎn)相除把求兩個正整數(shù)最大公因數(shù)的問題化為求兩個較小整數(shù)的最大公因數(shù)，直到兩個整數(shù)中的一個為0?，F(xiàn)將定理9.3.2歐幾里德算法以偽碼形式給出如下：Euclid(a，b：整數(shù))ifb=0thenreturnawhileb>0{r←a(modb)a←bb←r}returna算法中過程的每一步都是a用b代替，而b用a(modb)代替。只要b>0，這個過程就重復(fù)下去，當(dāng)b=0時算法終止，此時a的值也就是這一過程的非零余數(shù)，即為a和b的最大公因數(shù)。在歐幾里德算法中基本操作是除法，為研究歐幾里德算法的時間復(fù)雜性，需要求出算法中所使用的除法次數(shù)，下面拉梅定理給出解答。證明：如下定理定理10.2.1設(shè)a和b是滿足a≥b的正整數(shù)，則歐幾里德算法求得(a，b)而使用除法的次數(shù)小于或等于b的十進(jìn)制位數(shù)的5倍。兩個n位的二進(jìn)制整數(shù)a和b的乘法算法P204可按下面等式進(jìn)行計算：ab=a=計算過程：如下(核心思想：將abi當(dāng)作一個整體，做平移，再做加法，而不是直接做乘法運算)首先注意在bi=1時abi=a，而bi=0時abi=0。每當(dāng)用2乘一項時，結(jié)果都是把該項的二進(jìn)制展開向左移一位并在尾部加上一個0，因此，可把abi的二進(jìn)制展開向左移i位，再在尾部加上i個0來計算(abi)2i。最后，將n個整數(shù)(abi)2i，i=0，1，…，n-1，相加得到ab。兩個正整數(shù)a和b二進(jìn)制展開的乘法算法：mul(a，b)fori←0ton-1ifbi=1thenci←a左移i位elseci←0//c0c1…cn-1p←0fori←0ton-1p←p+ci//p是ab的值讀者不難得出：移位個數(shù)是O(n2)，位加法個數(shù)是O(n2)，這是因為，所有n個整數(shù)(abi)2i，i=0，1，…，n-1，需要0+1+2+…+n-1次移位，故移位數(shù)是O(n2)，而將(abi)2i從i=0到i=n+1加起來，需要做一次n位整數(shù)、(n+1)位整數(shù)、…以及2n位整數(shù)的加法，這些加法都需要O(n)次位相加，因此完成所有n個數(shù)加法需要O(n2)次位加法。最常用的產(chǎn)生偽隨機數(shù)的方法是線性同余法。P220它是遞歸定義的：xn+1=(axn+c)(modm)（1）Ui=xn/m（2）其中，m稱為模數(shù)，a為乘數(shù)，c為增量，x0為種數(shù)，且2≤a<m，0≤c<m，及0≤x0<m。有時要求偽隨機數(shù)為小數(shù)，為此使用xn/m。分析此算法的特點：RSA公鑰系統(tǒng)P222RSA公鑰系統(tǒng)是由MIT的三名研究人員：瑞弗斯特(RonRivest)、沙米爾(AdiSharmir)和阿德萊門(LenAdleman)于1978年聯(lián)合提出的，它的安全性是基于大整數(shù)因數(shù)分解困難問題，至今沒有有效的算法。RSA加密算法的過程：①選取兩素數(shù)p和q(保密)②計算n=pq(公開)，φ(n)=(p-1)(q-1)(保密)③選取加密公鑰e，滿足(e，φ(n))=1④計算解密私鑰d，滿足de≡1(modφ(n))使用RSA加密之前，應(yīng)將明文數(shù)字化，并取長度小于logn位的數(shù)字作為明文塊。加密算法c=E(m)=me(modn)解密算法D(c)=cd(modn)最短路徑算法P3251959年，荷蘭數(shù)學(xué)家E.W.Dijkstra給出了求某結(jié)點到其他各結(jié)點的最短鏈的一個標(biāo)記算法。Dijkstra標(biāo)記算法：令w(vi，vj)←∞，(vi，vj)E(G)l(u0)←0l(v)←∞，v≠u0S←{u0}i←0//初始化標(biāo)記WhilevSifl(ui)+w(ui，v)<l(v)thenl(v)←l(ui)+w(ui，v)//更新不在S中結(jié)點的標(biāo)記ui+1←minl(v)取最小值的且不屬于S中結(jié)點ui+1S←S∪{ui+1}//給S中添加帶最小標(biāo)記的結(jié)點若i=n-1，算法結(jié)束；否則i←i+1，轉(zhuǎn)至(2)由上述算法知：①S中各結(jié)點的標(biāo)記l(u)即是從u0到u的距離。又因n<∞，經(jīng)有限步后，每個結(jié)點都標(biāo)記了，從而得到了從u0到各結(jié)點的最短鏈。②算法和時間復(fù)雜性是O(n2)，所以是有效算法。說明：算法中的標(biāo)記設(shè)計l(u)問題。在算法的運行過程中，依次為各點作標(biāo)記，當(dāng)經(jīng)歷到此點時為它作一個標(biāo)記，未經(jīng)歷到時，標(biāo)記為∞。標(biāo)記的論據(jù)為min{l(ui)+w(ui，v),l(v)}.當(dāng)沒有直接的邊相連時，不作標(biāo)記。提供了一個圖的搜索算法，并且是對圖的遍歷算法，經(jīng)過了圖的所有點。集合S作為搜索結(jié)果的表示，其形成過程標(biāo)記了下次的搜索方向的起點，ui+1←minl(v)S←S∪{ui+1}搜索方向的邊為(ui，v)且vS，隨著搜索過程的進(jìn)行，S中的元素漸漸增多，當(dāng)然不屬于S的元素漸漸減少。當(dāng)所有的點都加入到其中時算法結(jié)束。S中的元素是有序的，唯一么？什么情況下不唯一？形成了一棵樹。對圖的點進(jìn)行了排列(其結(jié)果為一個偏序)。關(guān)鍵路算法P326關(guān)鍵路是通過求事件的最早期望完成時間和事件的最遲必須完成時間來實現(xiàn)的，為此定義：+(v)={x|x∈V<v，x>∈E}-(v)={x|x∈V<x，v>∈E}。分別稱+(v)和-(v)為結(jié)點v的后繼結(jié)點集合和v的先驅(qū)結(jié)點集合。最早期望完成時間從始點開始沿著最長路到達(dá)vi所需時間，稱為vi的最早期望完成時間，記為TE(vi)，i=1.2，…，n。于是TE(v1)=0TE(vi)={TE(vj)+wji}i=2，3，…，n②最遲必須完成時間在保證終點vn的最早期望完成時間TE(vn)不增加前提下，自始點v1最遲到達(dá)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關(guān)鍵路上的各結(jié)點的松馳時間均為0，即由松馳時間為0的結(jié)點構(gòu)成關(guān)鍵路，因為任何工序延誤了時間，整個工程項目就延誤了時間。算法的復(fù)雜性是O(n)。已知簡單有向圖G=<V，E>如圖16.4.3所示，G的鄰接矩陣A是P331A=試求A1，A2，A3，A4，A5。并說明A4中各非0元素的含義。圖16.4.3設(shè)圖G的鄰接矩陣A是P335A=試求G的可達(dá)矩陣P。請描述：什么是代數(shù)結(jié)構(gòu)？什么是半群、獨異點、群？請描述什么是代數(shù)結(jié)構(gòu)之間的同態(tài)？對于代數(shù)結(jié)構(gòu)V1=<Z,＋>,V2=<Zn,?>,其中＋為普通加法,?為模n加法,即"x,y?Zn有x?y=(x＋y)modn,這里Zn={0,1,…,n-1}．假設(shè)給定映射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)獨異點？請描述什么是一個群的子群？

設(shè)<G,*>是一個群，對任意的a∈G，令S={an|n∈Z，Z是整數(shù)}，證明<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,*>的子群。