演算法證明

1. RSA演算法的證明

分兩種情況考慮，
1.m,n互素的時候。要證明c^d≡m (molo n)。在上面一步中 再加一步，讀者應該就更好理解了。由歐拉定理退出XXXX，然後下面還有一步。m^kφ（n）≡1 modn 最後一步應該是寫成m^(kφ（n）+1)≡1 mod n.然後你應該就知道c^d≡m (molo n)。
2.這步中的p-1其實就是φ（p），你先算m^kφ（n）≡1 modn 然後再φ（p），結果還是1啊。
另外，你看的是不是電子檔的應用密碼學的？建議你去看實體書，那個上面寫的很詳細。不會像這個那麼簡略，很多都不能理解

2. 演算法分析證明題

程序設計里的時間復雜度？
就是同階無窮大那個演算法，lim(n->+inf,18n^2+4n+2014/n^2)=18 成立
這里只要不是無窮大就成立(inf=無窮大)
同理2,3
二：lim(n->+inf,log 3 n/log 100 n)=lim(n->+inf,ln n/ln n)*(ln 100/ln 3)=(ln 100/ln 3)不是無窮大所以成立

3. 演算法證明

顯然是錯的
比如說，有個問題是尋找某個數列中最大數所在的位置
一種演算法可以是從前向後找，返回找到的第一個
一種演算法可以是從後向前找，返回找到的第一個
還有演算法可以是等分成兩段，遞歸地使用上面的第一種（或者第二種）方法找，最後合並
還可以按奇偶性分類

諸如此類，可以有多種演算法
如果輸入數據是0,1,2,0,1,2，輸出是3，上面的演算法至少有兩種會產生這個輸出，但顯然合理的輸出既可以是3也可以是6，並不唯一

4. 離散數學等值演演算法證明，第一，第三問

（1）
(p∧q)∨(p∧¬q)
⇔p∧（q∨¬q）分配率
⇔p∧TRUE
⇔p

（2）
¬(p↔q)
⇔¬((p→q)∧(q→p)) 變成 合取析取
⇔¬((¬p∨q)∧(¬q∨p)) 變成 合取析取
⇔¬((¬p∨(p∧q))∧(¬q∨(p∧q))) 吸收率 反過來用
⇔¬((¬p∧¬q)∨(p∧q)) 分配率 把上式中(p∧q)看成一個整體來處理
⇔¬(¬p∧¬q)∧¬(p∧q) 德摩根定律
⇔(p∨q)∧¬(p∧q) 德摩根定律

5. 有關DES演算法的一道證明題

證明：DES演算法的加密演算法和解密演算法是完全一樣的，所不同的是密鑰以相反的順序依次加入到輪函數中。

DES演算法的加密流程如下：
（1）生成子密鑰
首先，將64比特的密鑰（實際有效位數只有56比特）進行置換，得到56比特的密鑰串；
然後，將56比特的串分為兩個28比特的子串，經過16輪的循環左移以及合並置換，生成16個子密鑰，記為K1K2K3...K16；
（2）加密
首先，將64比特的明文W做初始置換，得到結果IP（W）；
將結果分成兩個32比特的子串，記為L0和R0，所以L0R0=IP（W）；
然後，根據L0、R0以及K1，求得L1和R1，具體如下：
L1=R0，即L1跟R0完全相同；
R1=P(S(E(R0)^K1))^L0，其中：
E(R0)表示對R0做擴展置換；
E(R0)^K1表示上一步的結果與K1做異或運算；
S(E(R0)^K1)表示上一步的結果做S-box運算；
P(S(E(R0)^K1))表示上一步的結果做置換；
P(S(E(R0)^K1))^L0表示上一步的結果與L0做異或運算。
以上的過程就是一次輪函數。如此，再由L1、R1以及K2，求得L2R2。以此類推，經過16次輪函數的迭代即可求得L16R16。
最後，把L16R16交換順序，得到R16L16，再經過一次逆置換FP(R16L16),可以得到64比特的密文C,所以C=FP（R16L16）。

我們知道，DES的解密只需將16個子密鑰以相反的順序加入到輪函數中，重復加密的步驟即可。 現在我們要證明DES加密和解密的演算法是完全一樣，只是子密鑰使用的順序相反。也就是說，我們要證明密文經過子密鑰順序相反的加密之後可以得到明文。
DES演算法的解密流程如下：
（1）生成子密鑰
解密的時候使用的子密鑰與加密時的順序相反，記為K16K15...K2K1；
（2）解密
首先，將64比特的密文C做初始置換IP（C），
由於C=FP（R16L16），所以IP（C）=IP（FP（R16L16））=R16L16，因此得到的結果為R16L16。
將結果分成兩個32比特的子串，也就是R16和L16。
然後，對其進行輪函數運算，結果記為XY，具體如下：
X=L16，
Y=P(S(E(L16)^K16))^R16。
從加密的過程中，我們知道，
L16=R15,
R16=P(S(E(R15)^K16))^L15，
因此，Y=P(S(E(L16)^K16))^P(S(E(R15)^K16))^L15。
由於L16=R15，所以P(S(E(L16)^K16))=P(S(E(R15)^K16))，
所以P(S(E(L16)^K16))^P(S(E(R15)^K16))=，
因為^L15=L15，
所以Y=P(S(E(L16)^K16))^P(S(E(R15)^K16))^L15=L15。
由此可知，R16L16經過一次輪函數之後，得到的結果是R15L15。
如此，在對R15L15做輪函數運算，得到R14L14。以此類推，經過16次輪函數的迭代，得到R0L0。
最後，把R0L0交換順序，得到L0R0，再經過一次逆置換FP（L0R0）=FP（IP（W））=W，就得到了明文W。
綜上所述，DES演算法的加密演算法和解密演算法是完全一樣的，所不同的是密鑰以相反的順序依次加入到輪函數中。

6. SPFA演算法的原理及證明

求單源最短路的SPFA演算法的全稱是：Shortest Path Faster Algorithm，是西南交通大學段凡丁於1994年發表的。從名字我們就可以看出，這種演算法在效率上一定有過人之處。很多時候，給定的圖存在負權邊，這時類似Dijkstra演算法等便沒有了用武之地，而Bellman-Ford演算法的復雜度又過高，SPFA演算法便派上用場了。簡潔起見，我們約定加權有向圖G不存在負權迴路，即最短路徑一定存在。如果某個點進入隊列的次數超過N次則存在負環（SPFA無法處理帶負環的圖）。當然，我們可以在執行該演算法前做一次拓撲排序，以判斷是否存在負權迴路，但這不是我們討論的重點。我們用數組d記錄每個結點的最短路徑估計值，而且用鄰接表來存儲圖G。我們採取的方法是動態逼近法：設立一個先進先出的隊列用來保存待優化的結點，優化時每次取出隊首結點u，並且用u點當前的最短路徑估計值對離開u點所指向的結點v進行鬆弛操作，如果v點的最短路徑估計值有所調整，且v點不在當前的隊列中，就將v點放入隊尾。這樣不斷從隊列中取出結點來進行鬆弛操作，直至隊列空為止。
定理：只要最短路徑存在，上述SPFA演算法必定能求出最小值。證明：每次將點放入隊尾，都是經過鬆弛操作達到的。換言之，每次的優化將會有某個點v的最短路徑估計值d[v]變小。所以演算法的執行會使d越來越小。由於我們假定圖中不存在負權迴路，所以每個結點都有最短路徑值。因此，演算法不會無限執行下去，隨著d值的逐漸變小，直到到達最短路徑值時，演算法結束，這時的最短路徑估計值就是對應結點的最短路徑值。
期望時間復雜度：O(me)， 其中m為所有頂點進隊的平均次數，可以證明m一般小於等於2：「演算法編程後實際運算情況表明m一般沒有超過2n.事實上頂點入隊次數m是一個不容易事先分析出來的數,但它確是一個隨圖的不同而略有不同的常數.所謂常數,就是與e無關,與n也無關,僅與邊的權值分布有關.一旦圖確定,權值確定,原點確定,m就是一個確定的常數.所以SPFA演算法復雜度為O(e).證畢.（SPFA的論文）不過，這個證明是非常不嚴謹甚至錯誤的，事實上在bellman演算法的論文中已有這方面的內容，所以國際上一般不承認SPFA演算法。
對SPFA的一個很直觀的理解就是由無權圖的BFS轉化而來。在無權圖中，BFS首先到達的頂點所經歷的路徑一定是最短路(也就是經過的最少頂點數)，所以此時利用數組記錄節點訪問可以使每個頂點只進隊一次，但在帶權圖中，最先到達的頂點所計算出來的路徑不一定是最短路。一個解決方法是放棄數組，此時所需時間自然就是指數級的，所以我們不能放棄數組，而是在處理一個已經在隊列中且當前所得的路徑比原來更好的頂點時，直接更新最優解。
SPFA演算法有兩個優化策略SLF和LLL——SLF：Small Label First 策略，設要加入的節點是j，隊首元素為i，若dist(j)<dist(i)，則將j插入隊首，否則插入隊尾； LLL：Large Label Last 策略，設隊首元素為i，隊列中所有dist值的平均值為x，若dist(i)>x則將i插入到隊尾，查找下一元素，直到找到某一i使得dist(i)<=x，則將i出隊進行鬆弛操作。 SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高約 50%。 在實際的應用中SPFA的演算法時間效率不是很穩定，為了避免最壞情況的出現，通常使用效率更加穩定的Dijkstra演算法。

7. 證明分治演算法要對什麼性質展開證明

(1)設一函數intcount(intb,inte,intx),可求出A[b,e]中x的出現頻度,則:intcount(intb,inte,intx){if(b==e){returnA[b]==x);}else{returncount(b,(b+e)/2,x)+count((b+e)/2+1,e,x);}}復雜度O(n),具體地n次比較,n-1次加法運算.(2)直接從第1個往後選,選到滿為止.復雜度O(n)證明:假設此方法得出的解不是最優解,則:設所選物品為1~k,必然存在一個n(n>k),用這個物品代替原所選物品物品時,能取得更優的解值.但由條件可知,位置大於k的物品重量必然比小於k的物品大,所以至少要替換掉1個;而它的值卻小於原物品中的任何一個.所以假設不成立.按"直接從第1個往後選,選到滿為止"的方法選取,得出的解就是最優解.

8. 演算法設計與分析 證明n!＝Θ（n^n）

n!/(n^n)=(1/n)(2/n)……(n/n)<=1/n，當n趨向無窮時，趨於0,所以n！=o（n^n）

9. 貪心演算法的證明方法

貪心演算法的基本思路如下：
1.建立數學模型來描述問題。
2.把求解的問題分成若干個子問題。
3.對每一子問題求解，得到子問題的局部最優解。
4.把子問題的解局部最優解合成原來解問題的一個解。
----------------------------------------------
其實歸納起來也就一個類。其他的都是分支

10. 求Kruskal演算法正確性證明b

證明：令G為任何一個與Kruskal演算法產生的樹F不同的樹。考慮構造F的過程。令e為第一次選的一條不屬於G的邊。如果我們將e加入G，我們會得到一個圈C。這個圈不完全包含在F裡面，因此在C中有一條不屬於F的邊f。如果我們將e加入G並刪除f，我們就得到了一個新的樹H。

我們想要證明H不比G貴。這意味著e不比f貴。用反證法。假設f比e便宜。

現在考慮這樣一個問題：為什麼Kruskal演算法選擇了f而不是e呢？唯一的原因只可能是f被排除了，即f與加入e之前被選入F的邊會形成一個圈。但是所有這些已經被選的邊都是G的邊，因為e為第一次選的一條不屬於G的邊。又f本身屬於G，所以G就包含了一個圈，這是不可能的（G是樹）。這個矛盾證明了H不比G貴。

因此我們可以用H來代替G，而且H比G更接近F（即H與F有更多相同的邊）。如果H不是F，重復以上步驟，我們得到一系列與H越來越接近的不比G貴的樹。這個過程遲早會以F終結，這就證明了F不比G貴。

Kruskal演算法的正確性也就得證。