第一篇：hash算法
Hash，一般翻譯做“散列”，也有直接音譯為“哈希”的，就是把任意長度的輸入（又叫做預映射，pre-image），通過散列算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。
數學表述為：h = H(M)，其中H()--單向散列函數，M--任意長度明文，h--固定長度散列值。
在信息安全領域中應用的Hash算法，還需要滿足其他關鍵特性：
第一當然是單向性(one-way)，從預映射，能夠簡單迅速的得到散列值，而在計算上不可能構造一個預映射，使其散列結果等于某個特定的散列值，即構造相應的M=H-1(h)不可行。這樣，散列值就能在統計上唯一的表征輸入值，因此，密碼學上的 Hash 又被稱為“消息摘要(message digest)”，就是要求能方便的將“消息”進行“摘要”，但在“摘要”中無法得到比“摘要”本身更多的關于“消息”的信息。
第二是抗沖突性(collision-resistant)，即在統計上無法產生2個散列值相同的預映射。給定M，計算上無法找到M'，滿足H(M)=H(M')，此謂弱抗沖突性；計算上也難以尋找一對任意的M和M'，使滿足H(M)=H(M')，此謂強抗沖突性。要求“強抗沖突性”主要是為了防范所謂“生日攻擊(birthday attack)”，在一個10人的團體中，你能找到和你生日相同的人的概率是2.4%，而在同一團體中，有2人生日相同的概率是11.7%。類似的，當預映射的空間很大的情況下，算法必須有足夠的強度來保證不能輕易找到“相同生日”的人。
第三是映射分布均勻性和差分分布均勻性，散列結果中，為 0 的 bit 和為 1 的 bit，其總數應該大致相等；輸入中一個 bit 的變化，散列結果中將有一半以上的 bit 改變，這又叫做“雪崩效應(avalanche effect)”；要實現使散列結果中出現 1bit 的變化，則輸入中至少有一半以上的 bit 必須發生變化。其實質是必須使輸入中每一個 bit 的信息，盡量均勻的反映到輸出的每一個 bit 上去；輸出中的每一個 bit，都是輸入中盡可能多 bit 的信息一起作用的結果。
Damgard 和 Merkle 定義了所謂“壓縮函數(compression function)”，就是將一個固定長度輸入，變換成較短的固定長度的輸出，這對密碼學實踐上 Hash 函數的設計產生了很大的影響。Hash函數就是被設計為基于通過特定壓縮函數的不斷重復“壓縮”輸入的分組和前一次壓縮處理的結果的過程，直到整個消息都被壓縮完畢，最后的輸出作為整個消息的散列值。盡管還缺乏嚴格的證明，但絕大多數業界的研究者都同意，如果壓縮函數是安全的，那么以上述形式散列任意長度的消息也將是安全的。這就是所謂 Damgard/Merkle 結構：
在下圖中，任意長度的消息被分拆成符合壓縮函數輸入要求的分組，最后一個分組可能需要在末尾添上特定的填充字節，這些分組將被順序處理，除了第一個消息分組將與散列初始化值一起作為壓縮函數的輸入外，當前分組將和前一個分組的壓縮函數輸出一起被作為這一次
壓縮的輸入，而其輸出又將被作為下一個分組壓縮函數輸入的一部分，直到最后一個壓縮函數的輸出，將被作為整個消息散列的結果。
MD5 和 SHA1 可以說是目前應用最廣泛的Hash算法，而它們都是以 MD4 為基礎設計的。
1)MD4
MD4(RFC 1320)是 MIT 的 Ronald L.Rivest 在 1990 年設計的，MD 是 Message
Digest 的縮寫。它適用在32位字長的處理器上用高速軟件實現--它是基于 32 位操作數的位操作來實現的。它的安全性不像RSA那樣基于數學假設，盡管 Den Boer、Bosselaers 和 Dobbertin 很快就用分析和差分成功的攻擊了它3輪變換中的 2 輪，證明了它并不像期望的那樣安全，但它的整個算法并沒有真正被破解過，Rivest 也很快進行了改進。
下面是一些MD4散列結果的例子：
MD4(“")= 31d6cfe0d16ae931b73c59d7e0c089c0
MD4(”a“)= bde52cb31de33e46245e05fbdbd6fb24
MD4(”abc“)= a448017aaf21d8525fc10ae87aa6729d
MD4(”message digest“)= d9130a8164549fe818874806e1c7014b
MD4(”abcdefghijklmnopqrstuvwxyz“)= d79e1c308aa5bbcdeea8ed63df412da9
MD4(”ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789“)= 043f8582f241db351ce627e153e7f0e4
MD4
(”***************67890“)= e33b4ddc9c38f2199c3e7b164fcc0536
2)MD5
MD5(RFC 1321)是 Rivest 于1991年對MD4的改進版本。它對輸入仍以512位分組，其輸出是4個32位字的級聯，與 MD4 相同。它較MD4所做的改進是：
1)加入了第四輪
2)每一步都有唯一的加法常數；
3)第二輪中的G函數從((X ∧ Y)∨(X ∧ Z)∨(Y ∧ Z))變為((X ∧ Z)∨(Y ∧ ～Z))以減小其對稱性；
4)每一步都加入了前一步的結果，以加快”雪崩效應“；
5)改變了第2輪和第3輪中訪問輸入子分組的順序，減小了形式的相似程度；
6)近似優化了每輪的循環左移位移量，以期加快”雪崩效應“，各輪的循環左移都不同。盡管MD5比MD4來得復雜，并且速度較之要慢一點，但更安全，在抗分析和抗差分方面表現更好。
消息首先被拆成若干個512位的分組，其中最后512位一個分組是”消息尾+填充字節
(100...0)+64 位消息長度“，以確保對于不同長度的消息，該分組不相同。64位消息長度的限制導致了MD5安全的輸入長度必須小于264bit，因為大于64位的長度信息將被忽略。而4個32位寄存器字初始化為A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210，它們將始終參與運算并形成最終的散列結果。
接著各個512位消息分組以16個32位字的形式進入算法的主循環，512位消息分組的個數據決定了循環的次數。主循環有4輪，每輪分別用到了非線性函數
F(X, Y, Z)=(X ∧ Y)∨(～X ∧ Z)
G(X, Y, Z)=(X ∧ Z)∨(Y ∧ ～Z)
H(X, Y, Z)=X ⊕ Y ⊕ Z
I(X, Y, Z)= X ⊕(Y ∨ ～Z)
這4輪變換是對進入主循環的512位消息分組的16個32位字分別進行如下操作：將A、B、C、D的副本a、b、c、d中的3個經F、G、H、I運算后的結果與第4個相加，再加上32位字和一個32位字的加法常數，并將所得之值循環左移若干位，最后將所得結果加上a、b、c、d之一，并回送至ABCD，由此完成一次循環。
所用的加法常數由這樣一張表T[i]來定義，其中i為1...64，T[i]是i的正弦絕對值之
4294967296次方的整數部分，這樣做是為了通過正弦函數和冪函數來進一步消除變換中的線性性。
當所有512位分組都運算完畢后，ABCD的級聯將被輸出為MD5散列的結果。下面是一些MD5散列結果的例子：
MD5(”“)= d41d8cd98f00b204e9800998ecf8427e
MD5(”a“)= 0cc175b9c0f1b6a831c399e269772661
MD5(”abc“)= 900150983cd24fb0d6963f7d28e17f72
MD5(”message digest“)= f96b697d7cb7938d525a2f31aaf161d0
MD5(”abcdefghijklmnopqrstuvwxyz“)= c3fcd3d76192e4007dfb496cca67e13b
MD5(”ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789“)= d174ab98d277d9f5a5611c2c9f419d9f
MD5
(”***************67890“)= 57edf4a22be3c955ac49da2e2107b67a
參考相應RFC文檔可以得到MD4、MD5算法的詳細描述和算法的C源代碼。
3)SHA1 及其他
SHA1是由NIST NSA設計為同DSA一起使用的，訪問可以得到它的詳細規范--[/url]”FIPS PUB 180-1 SECURE HASH STANDARD“。它對長度小于264的輸入，產生長度為160bit的散列值，因此抗窮舉(brute-force)性更好。SHA-1 設計時基于和MD4相同原理,并且模仿了該算法。因為它將產生160bit的散列值，因此它有
5個參與運算的32位寄存器字，消息分組和填充方式與MD5相同，主循環也同樣是4輪，但每輪進行20次操作，非線性運算、移位和加法運算也與MD5類似，但非線性函數、加法常數和循環左移操作的設計有一些區別，可以參考上面提到的規范來了解這些細節。下面是一些SHA1散列結果的例子：
SHA1(”abc“)= a9993e36 4706816a ba3e2571 7850c26c 9cd0d89d
SHA1(”abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq“)= 84983e44 1c3bd26e baae4aa1 f95129e5 e54670f1
其他一些知名的Hash算法還有MD2、N-Hash、RIPE-MD、HAVAL等等。上面提到的這些都屬于”純“Hash算法。還有另2類Hash算法，一類就是基于對稱分組算法的單向散列算法，典型的例子是基于DES的所謂Davies-Meyer算法，另外還有經IDEA改進的Davies-Meyer算法，它們兩者目前都被認為是安全的算法。另一類是基于模運算/離散對數的，也就是基于公開密鑰算法的，但因為其運算開銷太大，而缺乏很好的應用前景。
沒有通過分析和差分攻擊考驗的算法，大多都已經夭折在實驗室里了，因此，如果目前流行的Hash算法能完全符合密碼學意義上的單向性和抗沖突性，就保證了只有窮舉，才是破壞Hash運算安全特性的唯一方法。為了對抗弱抗沖突性，我們可能要窮舉個數和散列值空間長度一樣大的輸入，即嘗試2^128或2^160個不同的輸入，目前一臺高檔個人電腦可能需要10^25年才能完成這一艱巨的工作，即使是最高端的并行系統，這也不是在幾千年里的干得完的事。而因為”生日攻擊“有效的降低了需要窮舉的空間，將其降低為大約1.2*2^64或1.2*2^80，所以，強抗沖突性是決定Hash算法安全性的關鍵。
在NIST新的 Advanced Encryption Standard(AES)中，使用了長度為128、192、256bit 的密鑰，因此相應的設計了 SHA256、SHA384、SHA512，它們將提供更好的安全性。
Hash算法在信息安全方面的應用主要體現在以下的3個方面：
1)文件校驗
我們比較熟悉的校驗算法有奇偶校驗和CRC校驗，這2種校驗并沒有抗數據篡改的能力，它們一定程度上能檢測并糾正數據傳輸中的信道誤碼，但卻不能防止對數據的惡意破壞。
MD5 Hash算法的”數字指紋“特性，使它成為目前應用最廣泛的一種文件完整性校驗和(Checksum)算法，不少Unix系統有提供計算md5 checksum的命令。它常被用在下面的2種情況下：
第一是文件傳送后的校驗，將得到的目標文件計算 md5 checksum，與源文件的md5 checksum 比對，由兩者 md5 checksum 的一致性，可以從統計上保證2個文件的每一個碼元也是完全相同的。這可以檢驗文件傳輸過程中是否出現錯誤，更重要的是可以保證文件
在傳輸過程中未被惡意篡改。一個很典型的應用是ftp服務，用戶可以用來保證多次斷點續傳，特別是從鏡像站點下載的文件的正確性。
更出色的解決方法是所謂的代碼簽名，文件的提供者在提供文件的同時，提供對文件Hash值用自己的代碼簽名密鑰進行數字簽名的值，及自己的代碼簽名證書。文件的接受者不僅能驗證文件的完整性，還可以依據自己對證書簽發者和證書擁有者的信任程度，決定是否接受該文件。瀏覽器在下載運行插件和java小程序時，使用的就是這樣的模式。
第二是用作保存二進制文件系統的數字指紋，以便檢測文件系統是否未經允許的被修改。不少系統管理/系統安全軟件都提供這一文件系統完整性評估的功能，在系統初始安裝完畢后，建立對文件系統的基礎校驗和數據庫，因為散列校驗和的長度很小，它們可以方便的被存放在容量很小的存儲介質上。此后，可以定期或根據需要，再次計算文件系統的校驗和，一旦發現與原來保存的值有不匹配，說明該文件已經被非法修改，或者是被病毒感染，或者被木馬程序替代。TripWire就提供了一個此類應用的典型例子。
更完美的方法是使用”MAC“。”MAC“ 是一個與Hash密切相關的名詞，即信息鑒權碼
(Message Authority Code)。它是與密鑰相關的Hash值，必須擁有該密鑰才能檢驗該Hash值。文件系統的數字指紋也許會被保存在不可信任的介質上，只對擁有該密鑰者提供可鑒別性。并且在文件的數字指紋有可能需要被修改的情況下，只有密鑰的擁有者可以計算出新的散列值，而企圖破壞文件完整性者卻不能得逞。
2)數字簽名
Hash 算法也是現代密碼體系中的一個重要組成部分。由于非對稱算法的運算速度較慢，所以在數字簽名協議中，單向散列函數扮演了一個重要的角色。
在這種簽名協議中，雙方必須事先協商好雙方都支持的Hash函數和簽名算法。
簽名方先對該數據文件進行計算其散列值，然后再對很短的散列值結果--如Md5是16個字節，SHA1是20字節，用非對稱算法進行數字簽名操作。對方在驗證簽名時，也是先對該數據文件進行計算其散列值，然后再用非對稱算法驗證數字簽名。
對 Hash 值，又稱”數字摘要“進行數字簽名，在統計上可以認為與對文件本身進行數字簽名是等效的。而且這樣的協議還有其他的優點：
首先，數據文件本身可以同它的散列值分開保存，簽名驗證也可以脫離數據文件本身的存在而進行。
再者，有些情況下簽名密鑰可能與解密密鑰是同一個，也就是說，如果對一個數據文件簽名，與對其進行非對稱的解密操作是相同的操作，這是相當危險的，惡意的破壞者可能將一個試圖騙你將其解密的文件，充當一個要求你簽名的文件發送給你。因此，在對任何數據文件進行數字簽名時，只有對其Hash值進行簽名才是安全的。
3)鑒權協議
如下的鑒權協議又被稱作”挑戰--認證模式：在傳輸信道是可被偵聽，但不可被篡改的情況下，這是一種簡單而安全的方法。
需要鑒權的一方，向將被鑒權的一方發送隨機串（“挑戰”），被鑒權方將該隨機串和自己的鑒權口令字一起進行 Hash 運算后，返還鑒權方，鑒權方將收到的Hash值與在己端用該隨機串和對方的鑒權口令字進行 Hash 運算的結果相比較（“認證”），如相同，則可在統計上認為對方擁有該口令字，即通過鑒權。
POP3協議中就有這一應用的典型例子：
S: +OK POP3 server ready <1896.697170952@dbc.mtview.ca.us>
C: APOP mrose c4c9334bac560ecc979e58001b3e22fb
S: +OK maildrop has 1 message(369 octets)
在上面的一段POP3協議會話中，雙方都共享的對稱密鑰（鑒權口令字）是tanstaaf，服務器發出的挑戰是<1896.697170952@dbc.mtview.ca.us>，客戶端對挑戰的應答是MD5(“<1896.697170952@dbc.mtview.ca.us>tanstaaf”)=
c4c9334bac560ecc979e58001b3e22fb，這個正確的應答使其通過了認證。
散列算法長期以來一直在計算機科學中大量應用，隨著現代密碼學的發展，單向散列函數已經成為信息安全領域中一個重要的結構模塊，我們有理由深入研究其設計理論和應用方法。
第二篇：HASH算法安全性淺談
HASH算法安全性淺談
2011年12月，CSDN網站遭到黑客攻擊，約600萬用戶的登錄名、密碼及郵箱遭到泄漏。隨后，CSDN“密碼外泄門”持續發酵，世紀佳緣、人人網、天涯社區等網站相繼被曝出用戶數據遭泄密，大量的用戶賬號和密碼被公開，數量超過5000萬。此次密碼泄漏堪稱近年來國內規模最大的網絡安全事件。
事后，密碼明文保存被認為是此次事件的“罪魁禍首”。當前，互聯網越來越進入人們的生活。用戶訪問各種網站，在注冊的時候需要輸入用戶名和密碼，在僅僅考慮功能的前提下，可以把用戶名和密碼以明文的方式存儲在數據表中。當用戶登錄時，直接將用戶輸入的明文密碼與數據庫中的密碼進行比對，如果相同則授權用戶登錄。
明文密碼保存方式在實現上非常簡單，但面臨的問題也很明顯，那就是沒有任何安全防護機制。任何有權讀取或以某種方式獲得數據庫的人都可以獲取所有用戶的密碼。因此我們需要一種即使數據文件被竊取，竊取者也不能獲得用戶密碼的方式。
現在網站已經基本不再使用明文密碼保存的方式，而是在數據庫中保存散列算法處理的結果。通過HASH散列函數的方式，可以有效的降低密碼泄露的風險。HASH散列函數是把輸入的密碼數據通過特定的算法處理后，輸出為一個固定長度的字符串。這樣，當用戶輸入密碼時，直接將該密碼代入散列算法得出散列結果，再與保存的數據對比，相同則允許登錄。如“abc”經過MD5散列之后，結果為
“900150983CD24FB0D6963F7D28E17F72”，將這個字符串保存到數據庫中替代密碼明文。通過HASH函數的處理，即使密碼數據庫文件被竊取，竊取者也不能直觀的獲取到賬號的密碼。
HASH散列函數的特點是單向性，即由輸入數據可以得到確定的輸出字符串，但從輸出的字符串反向獲取輸入數據的難度很大，幾乎是不可能做到的。
目前常見的散列算法有MD5和SHA1。MD5的輸出是128位字符串，SHA1的輸出是160位字符串。還有更復雜的SHA256，SHA512，其輸出分別是256位和512位。輸出結果的長度越長，HASH函數的安全性就越高。
當前HASH散列算法最大的安全隱患就是字典攻擊。所謂字典攻擊，即根據密碼所使用字符范圍及密碼長度窮舉出所有可能的密碼，對這些密碼進行HASH處理，把HASH值保存在數據庫中，一旦獲得用戶密碼HASH值，將其與數據庫中的HASH值進行對比，就可以快速的找到明文密碼。
對抗字典攻擊的辦法主要是限制密碼最短長度，擴大密碼字符組成，采用更長位數的HASH散列算法。這些都可以增加攻擊者生成字典的時間成本和經濟成本。
個人認為還可以參照3DES加密算法，采用多重HASH算法，即對HASH值再進行多次HASH處理，這樣也可以增加攻擊者破解難度。但在各種資料中，尚未看到有人有提到此種方法，不知何故。
上述方法都是不斷增加攻擊者的難度，但隨著現在計算機的計算
速度和存儲能力的不斷提高，攻擊者破解的時間、經濟成本都在不斷降低，因此這些方法都不是永久有效的。
2004年，山東大學王小云教授公布了利用差分技術實現對HASH算法的碰撞攻擊，隨后又公布了碰撞攻擊的詳細原理過程。MD5、SHA-1是當前國際通行的兩大密碼標準。MD5由國際著名密碼學家圖靈獎獲得者兼公鑰加密算法RSA的創始人Ronald L.Rivest設計，SHA-1是由美國專門制定密碼算法的標準機構——美國國家標準技術研究院（NIST）與美國國家安全局（NSA）設計。兩大算法是目前國際電子簽名及許多其它密碼應用領域的關鍵技術，廣泛應用于金融、證券等電子商務領域。
王小云教授的碰撞攻擊算法，具有非常重要的理論意義，對密碼學的發展具有極大的推動作用，為HASH函數的密碼分析學開辟了一條新的道路。碰撞算法從理論上表明了電子簽名可以偽造，必須及時添加限制條件，或者重新選用更為安全的密碼標準，以保證電子商務的安全。這一成果說明了MD5和SHA1已經不能用作身份驗證或數字簽名，另外在理論上說明了數字摘要算法用于數據的完整性鑒別具有先天缺陷。但另一方面，由于方法上的限制，要構造具有特定語義的碰撞攻擊幾乎是不可能的，因此并不是所有采用MD5等算法的應用都徹底失效。在實際中，MD5和SHA1算法經常與其它算法一起使用，或者進行了很多變形，簡單地找到MD5碰撞對并沒有實際性的威脅。
同時，她的研究成果也給其他研究者以極大的參考價值，后續研究者在其基礎上，不斷推出新的研究成果。2005年3月，用筆記本
在幾個小時內找到MD5碰撞；2006年3月，用筆記本在1分鐘內找到MD5碰撞；2007年12月，用Chosen-Prefix Collision，偽造出了符合X.509標準的數字證書；2008年12月，利用MD5碰撞，創造了一個假的來自可信CA的數字證書。因此，尋找MD5 碰撞的算法的時間、空間復雜度都已降至實用水平。但從實踐角度，不同信息具有相同MD5值的可能性還是非常低的，通過碰撞的方法也很難碰撞出復雜信息的MD5值。現在MD5破譯技術的研究者們正重點研究MD5碰撞的實際應用。
為了防止網絡監聽及重放攻擊，在網站登錄過程中，通常還使用干擾字符串，即在用戶登錄時，服務器隨機生成一段前綴或后綴字符串，瀏覽器將用戶的密碼HASH處理后，再加上干擾字符串，再HASH處理一遍，再提交給服務器。干擾字符串是隨機生成，用過一次即失效，因此即使登錄過程中HASH值被截取，也無法再次使用其來登錄。
如果需要更安全的算法，建議使用SHA256或SHA512。目前還沒有出現針對SHA256，SHA512算法的有效碰撞攻擊方法。該算法可以是MD5及SHA1的不錯的后繼者。
總之，HASH算法是在不斷被破解的過程中，不斷改進的。所謂“魔高一尺，道高一丈。”其安全性也是在不斷提高的。當前主流的MD5和SHA1正在改為SHA256和SHA512。或許以后還會有更復雜的HASH演進算法，甚至更高級的密碼處理算法，我們都拭目以待。
對于碰撞攻擊的實際應用研究，我們也持續關注。王小云教授的差分碰撞攻擊算法，雖然里面沒有太高深的數學算法，但過程還是很
復雜繁瑣的，有興趣可以參考其原始論文，仔細研讀分析。碰撞攻擊的后續研究成果也有很大的參考價值。論文列舉如下：
Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD； How to Break MD5 and other Hash Functions；
Finding Collisions in the Full SHA-1；
Finding MD5 Collisions a Toy For a Notebook；
Tunnels in Hash Functions MD5 Collisions Within a Minute； Efficient Hash Collision Search Strategies on Special-Purpose Hardware；
Chosen-prefix Collisions for MD5 and Applications；
Fast Collision Attack on MD5。
第三篇：算法總結
算法分析與設計總結報告
71110415 錢玉明
在計算機軟件專業中，算法分析與設計是一門非常重要的課程，很多人為它如癡如醉。很多問題的解決，程序的編寫都要依賴它，在軟件還是面向過程的階段，就有程序=算法+數據結構這個公式。算法的學習對于培養一個人的邏輯思維能力是有極大幫助的，它可以培養我們養成思考分析問題，解決問題的能力。作為IT行業學生，學習算法無疑會增強自己的競爭力，修煉自己的“內功”。
下面我將談談我對這門課程的心得與體會。
一、數學是算法的基礎
經過這門課的學習，我深刻的領悟到數學是一切算法分析與設計的基礎。這門課的很多時間多花在了數學公式定理的引入和證明上。雖然很枯燥，但是有必不可少。我們可以清晰的看到好多算法思路是從這些公式定理中得出來的，尤其是算法性能的分析更是與數學息息相關。其中有幾個定理令我印象深刻。
①主定理
本門課中它主要應用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一個大問題分解為a個子問題，其中子問題的規模為b。而f(n)可看作這些子問題的組合時的消耗。這些可以利用主定理的相關結論進行分析處理。當f(n)量級高于nlogba時，我們可以設法降低子問題組合時的消耗來提高性能。反之我們可以降低nlogba的消耗，即可以擴大問題的規模或者減小子問題的個數。因此主定理可以幫助我們清晰的分析出算法的性能以及如何進行有效的改進。
②隨機算法中的許多定理的運用
在這門課中，我學到了以前從未遇見過的隨機算法，它給予我很大的啟示。隨機算法不隨機，它可通過多次的嘗試來降低它的錯誤率以至于可以忽略不計。這些都不是空穴來風，它是建立在嚴格的定理的證明上。如素數判定定理是個很明顯的例子。它運用了包括費馬小定理在內的各種定理。將這些定理進行有效的組合利用，才得出行之有效的素數判定的定理。尤其是對尋找證據數算法的改進的依據，也是建立在3個定理上。還有檢查字符串是否匹配也是運用了許多定理：指紋的運用，理論出錯率的計算，算法性能的評價也都是建立在數學定理的運用上。
這些算法都給予了我很大啟發，要想學好算法，學好數學是必不可少的。沒有深厚的數學功力作為地基，即使再漂亮的算法框架，代碼實現也只能是根底淺的墻上蘆葦。
二、算法的核心是思想
我們學習這門課不是僅僅掌握那幾個經典算法例子，更重要的是為了學習蘊含在其中的思想方法。為什么呢？舉個例子。有同學曾問我這樣一個問題：1000只瓶子裝滿水，但有一瓶有毒，且毒發期為1個星期。現在用10只老鼠在一個星期內判斷那只瓶子有毒，每只老鼠可以喝多個瓶子的水，每個瓶子可以只喝一點。問如何解決？其實一開始我也一頭霧水，但是他提醒我跟計算機領域相關，我就立馬有了思路，運用二進制。因為計算機的最基本思想就是二進制。所以說，我們不僅要學習算法，更得學習思想方法。
①算法最基本的設計方法包括分治法，動態規劃法，貪心法，周游法，回溯法，分支定界法。我們可利用分治法做快速排序，降低找n個元素中最大元和最小元的量級，降低n位二進制x和y相乘的量級，做Strassen矩陣乘法等等。它的思想就是規模很大的問題分解為規模較小的獨立的子問題，關鍵是子問題要與原問題同類，可以采取平衡法來提高性能。
動態規劃法是把大問題分解為子問題，但是子問題是重復的，后面的問題可以利用前面解決過的問題的結果。如構造最優二叉查找樹，解決矩陣連乘時最小計算次數問題，尋找最長公共子序列等等。
貪心法就是局部最優法，先使局部最優，再依次構造出更大的局部直至整體。如Kruscal最小生成樹算法，求哈夫曼編碼問題。
周游法就是簡單理解就是采取一定的策略遍歷圖中所有的點，典型的應用就是圖中的深度優先搜索(DFS)和廣度優先搜索(BFS)。
回溯法就是就是在滿足一定的條件后就往前走，當走到某步時，發現不滿足條件就退回一步重新選擇新的路線。典型的應用就是8皇后問題，平面點集的凸包問題和0-1背包問題。
分支定界法：它是解決整數規劃問題一種最常用的方法。典型應用就是解決整數規劃問題。
②評價算法性能的方法如平攤分析中的聚集法，會計法和勢能法。聚集法就是把指令分為幾類，計算每一類的消耗，再全部疊加起來。會計法就是計算某個指令時提前將另一個指令的消耗也算進去，以后計算另一個指令時就不必再算了。勢能法計算每一步的勢的變化以及執行這步指令的消耗，再將每一步消耗全部累計。
這幾種方法都是平攤分析法，平攤分析的實質就是總體考慮指令的消耗時間，盡管某些指令的消耗時間很大也可以忽略不計。上述三種方法難易程度差不多，每種方法都有屬于它的難點。如聚集法中如何將指令有效分類，會計法中用什么指令提前計算什么指令的消耗，勢能法中如何選取勢能。因此掌握這些方法原理還不夠，還要學會去應用，在具體的問題中去判斷分析。
三、算法與應用緊密相關
我認為學習算法不能局限于書本上的理論運算，局限于如何提高性能以降低復雜度，我們要將它與實際生活聯系起來。其實算法問題的產生就來自于生活，設計出高效的算法就是為了更好的應用。如尋找最長公共子序列算法可以應用在生物信息學中通過檢測相似DNA片段的相似成分來檢測生物特性的相似性，也可以用來判斷兩個字符串的相近性，這可應用在數據挖掘中。快速傅立葉變換（FFT）可應用在計算多項式相乘上來降低復雜度，脫線min算法就是利用了Union-Find這種結構。還有圖中相關算法，它對于解決網絡流量分配問題起了很大的幫助，等等。
這些應用給了我很大的啟發：因為單純講一個Union-Find算法，即使了解了它的實現原理，遇到具體的實際問題也不知去如何應用。這就要求我們要將自己學到的算法要和實際問題結合起來，不能停留在思想方法階段，要學以致用，做到具體問題具體分析。
四、對計算模型和NP問題的理解
由于對這部分內容不是很理解，所以就粗淺的談一下我的看法。
首先談到計算模型，就不得不提到圖靈計算，他將基本的計算抽象化，造出一個圖靈機，得出了計算的本質。并提出圖靈機可以計算的問題都是可以計算的，否則就是不可計算的。由此引申出一個著名論題：任何合理的計算模型都是相互等價的。它說明了可計算性本身不依賴于任何具體的模型而客觀存在。
NP問題比較復雜，我認為它是制約算法發展的瓶頸，但這也是算法分析的魅力所在。NP問題一般可分為3類，NP-C問題，NP-hard問題以及頑型問題。NP-C它有個特殊的性質，如果存在一個NP-C問題找到一個多項式時間的解法，則所有的NP-C問題都能找到多項式時間解法。如哈密頓回路問題。NP-hard主要是解決最優化問題。它不一定是NP問題。這些問題在規模較小時可以找出精確解，但是規模大時，就因時間太復雜而找不到最優解。此時一般會采用近似算法的解法。頑型問題就是已經證明不可能有多項式時間的算法，如漢諾塔問題。
最后談談對這門課程的建議
①對于這門算法課，我認為應該加強對算法思想方法的學習。所以我建議老師可不可以先拋出問題而不給出答案，講完一章，再發課件。讓我們先思考一會兒，或者給出個獎勵機制，誰能解決這個問題，平時成績加分。這在一定程度上會將強我們思考分析問題的能力。因為我感覺到，一個問題出來，未經過思考就已經知曉它的答案，就沒什么意思，得不到提高，而且也不能加深對問題的思考和理解。下次遇到類似的問題也就沒有什么印象。而且上課讓我們思考，點名回答問題可以一定程度上有效的防止不認真聽課的現象。
②作業安排的不是很恰當。本門課主要安排了三次作業，個人感覺只有第一次作業比較有意思。后面兩次作業只是實現一下偽代碼，沒有太多的技術含量。而且對于培養我們的解決問題的能力也沒有太多的幫助，因為這間接成為了程序設計題，不是算法設計題。
③本門課的時間安排的不太恰當，因為本學期的課程太多，壓力太大。沒有太多的時間去學習這門課程。因為我相信大家都對它感興趣，比較重視，想花功夫，但苦于沒時間。所以可不可以將課程提前一個學期，那時候離散數學也已經學過，且課程的壓力也不是很大。錯開時間的話，我覺得應該能夠更好提高大家算法分析設計的能力。
第四篇：算法復習材料
1.假票統計
問題描述：
由于你們團隊在國際大學生詩歌大賽上取得的巨大成就，你們學校決定為你們召開一次慶功雞尾酒會，到來的人數大大超出了預期。然而慶功會的主管卻抱怨發現了有人使用假票，實際的門票是從1到N(N <= 10000)，主管懷疑有人采用復印、打印等手段偽造了門票。他把所有收上來的門票拿給你，要求你編寫程序，統計所有門票中存在假票的門票數。輸入：
輸入文件中包含多組測試數據，每組測試數據占兩行。第1行包括兩個整數N和M，分別表示門票的初始總張數和參加晚會的總人數(1 <= N <= 10000,1 <= M <= 20000)。第2行為M個整數Ti，表示收到的M張門票的號碼(1 <= Ti <= N)。輸入文件最后一行為0 0，表示輸入結束。輸出：
對每組輸入測試數據，輸出一個整數，占一行，表示收上來的門票中共有多少張票被偽造過。輸入樣例： 5 5 3 3 1 2 4 6 10 6 1 3 6 6 4 2 3 1 2 0 0 輸出樣例： 1 4
參考代碼：
//計算有幾個號碼被復制過 #include
2.看和說
問題描述：
看和說的順序定義如下：任何一個字符串都是以數字開頭，每個隨后的元素都是被前一個元素重新定義。例如，字符串“122344111”可以被描述為“1個1，兩個2，1個3，2個4和3個1”。因此，122344111以序列的形式表示出來就是1122132431。同理，101就表示1111111111。輸入：
輸入包括測試數據的組數，然后依次為相應的測試數據，每個數據占一行，不會超過1000位。輸出： 對于每個測試數據，輸出對應的字符串。
輸入樣例： 3 122344111 1111111111 12345 輸出樣例： 1122132431 101 1112131415 參考代碼：
#include
num=1;
gets(s);
len=strlen(s);
for(i=0;i { if(s[i]!=s[i+1]) { printf(“%d%c”,num,s[i]); num=1; } else num++; } printf(“n”);} return 0;} 3．二進制轉化為十六進制 問題描述： 輸入一個2進制的數，要求輸出該2進制數的16進制表示。在16進制的表示中，A-F表示10-15 輸入： 第1行是測試數據的組數n，后面跟著n行輸入。每組測試數據占1行，包括一個以0和1組成的字符串，字符串長度至少是1，至多是10000。輸出： n行，每行輸出對應一個輸入。輸入樣例： 100000 111 輸出樣例： 7 參考代碼1： #include inti,n,dec,len; char bin[10001]; scanf(“%d”,&n); while(n--) { scanf(“%s”,bin); len=strlen(bin);//求二進制數的長度 dec=4-len%4; if(len%4)//處理頭幾位，后移dec位，使得變成4的整數倍，前面補0 { for(i=len;i>=0;i--) bin[i+dec]=bin[i]; for(i=0;i bin[i]='0'; len+=dec; } for(i=0;i printf(“%X”,(bin[i+3]-'0')+(bin[i+2]-'0')*2+(bin[i+1]-'0')*4+(bin[i]-'0')*8); printf(“n”); } return 0;} //參考代碼2： #include int main(){ int i, j, t, tp, p;charstr[maxn], str_rev[maxn];char res[maxn/4], tmp[6], tmp_rev[6];while(scanf(“%d”, &t)!=EOF){ while(t--){ p = 0;scanf(“%s”, &str);intlen = strlen(str);for(i = lenii;strncpy(tmp, str_rev + i, k);for(j = kj-1] = tmp[j];sscanf(tmp_rev, “%d”, &tp);//printf(“k = %d tp = %d tmp = %s tmp_rev = %sn”, k, tp, tmp, tmp_rev);switch(tp){ case 0: res[p++] = '0';break;case 1: res[p++] = '1';break;case 10: res[p++] = '2';break;case 11: res[p++] = '3';break;case 100: res[p++] = '4';break;case 101: res[p++] = '5';break;case 110: res[p++] = '6';break;case 111: res[p++] = '7';break;case 1000: res[p++] = '8';break;case 1001: res[p++] = '9';break;case 1010: res[p++] = 'A';break;case 1011: res[p++] = 'B';break;case 1100: res[p++] = 'C';break;case 1101: res[p++] = 'D';break;case 1110: res[p++] = 'E';break;case 1111: res[p++] = 'F';break;default: break;} i += 4; } for(i = p-1;i >= 0;i--)printf(“%c”, res[i]);printf(“n”);} } return 0;} 算法分塊總結 為備戰2005年11月4日成都一戰，特將已經做過的題目按算法分塊做一個全面詳細的總結，主要突出算法思路，盡量選取有代表性的題目，盡量做到算法的全面性，不漏任何ACM可能涉及的算法思路。算法設計中，時刻都要牢記要減少冗余，要以簡潔高效為追求目標。另外當遇到陌生的問題時，要想方設法進行模型簡化，轉化，轉化成我們熟悉的東西。 圖論模型的應用 分層圖思想的應用： 用此思想可以建立起更簡潔、嚴謹的數學模型，進而很容易得到有效算法。重要的是，新建立的圖有一些很好的性質： 由于層是由復制得到的，所以所有層都非常相似，以至于我們只要在邏輯上分出層的概念即可，根本不用在程序中進行新層的存儲，甚至幾乎不需要花時間去處理。由于層之間的相似性，很多計算結果都是相同的。所以我們只需對這些計算進行一次，把結果存起來，而不需要反復計算。如此看來，雖然看起來圖變大了，但實際上問題的規模并沒有變大。層之間是拓撲有序的。這也就意味著在層之間可以很容易實現遞推等處理，為發現有效算法打下了良好的基礎。 這些特點說明這個分層圖思想還是很有潛力的，尤其是各層有很多公共計算結果這一點，有可能大大消除冗余計算，進而降低算法時間復雜度。二分圖最大及完備匹配的應用： ZOJ place the robots: 二分圖最優匹配的應用： 最大網絡流算法的應用：典型應用就求圖的最小割。最小費用最大流的應用： 容量有上下界的最大流的應用： 歐拉路以及歐拉回路的應用：主要利用求歐拉路的套圈算法。最小生成樹： 求最小生成樹，比較常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使復雜度降為O(Vlog2V+E)，后者一般應用于稀疏圖，其時間復雜度為O(Elog2V)。最小K度限制生成樹： 抽象成數學模型就是： 設G=(V,E,ω)是連通的無向圖，v0 ∈V是特別指定的一個頂點,k為給定的一個正整數。首先考慮邊界情況。先求出問題有解時k 的最小值：把v0點從圖中刪去后，圖中可能會出 現m 個連通分量，而這m 個連通分量必須通過v0來連接，所以，在圖G 的所有生成樹中 dT(v0)≥m。也就是說，當k 首先，將 v0和與之關聯的邊分別從圖中刪去，此時的圖可能不再連通，對各個連通分量，分別求最小生成樹。接著，對于每個連通分量V’，求一點v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，則該連通分量通過邊(v1,v0)與v0相連。于是，我們就得到了一個m度限制生成樹，不難證明，這就是最小m度限制生成樹。這一步的時間復雜度為O(Vlog2V+E)我們所求的樹是無根樹，為了解題的簡便，把該樹轉化成以v0為根的有根樹。 假設已經得到了最小p度限制生成樹，如何求最小p+1 度限制生成樹呢？在原先的樹中加入一條與v0相關聯的邊后，必定形成一個環。若想得到一棵p+1 度限制生成樹，需刪去一條在環上的且與v0無關聯的邊。刪去的邊的權值越大，則所得到的生成樹的權值和就越小。動態規劃就有了用武之地。設Best(v)為路徑v0—v上與v0無關聯且權值最大的邊。定義father(v)為v的父結點，動態轉移方程：Best(v)=max(Best(father(v)),(father(v),v))，邊界條件為Best[v0]=-∞，Best[v’]=-∞|(v0,v’)∈E(T)。 狀態共|V|個，狀態轉移的時間復雜度O(1)，所以總的時間復雜度為O(V)。故由最小p度限制生成樹得到最小p+1度限制生成樹的時間復雜度為O(V)。1 先求出最小m度限制生成樹； 2由最小m度限制生成樹得到最小m+1度限制生成樹;3 當dT(v0)=k時停止。 加邊和去邊過程，利用動態規劃優化特別值得注意。 次小生成樹： 加邊和去邊很值得注意。 每加入一條不在樹上的邊，總能形成一個環，只有刪去環上的一條邊，才能保證交換后仍然是生成樹，而刪去邊的權值越大，新得到的生成樹的權值和越小。具體做法： 首先做一步預處理，求出樹上每兩個結點之間的路徑上的權值最大的邊，然后，枚舉圖中不在樹上的邊，有了剛才的預處理，我們就可以用O(1)的時間得到形成的環上的權值最大的邊。如何預處理呢？因為這是一棵樹，所以并不需要什么高深的算法，只要簡單的BFS 即可。 最短路徑的應用： Dijkstra 算法應用： Folyed 算法應用： Bellman-Ford 算法的應用： 差分約束系統的應用： 搜索算法 搜索對象和搜索順序的選取最為重要。一些麻煩題，要注意利用數據有序化，要找一個較優的搜索出發點，凡是能用高效算法的地方盡量爭取用高效算法。基本的遞歸回溯深搜，記憶化搜索，注意剪枝： 廣搜（BFS）的應用： 枚舉思想的應用： ZOJ 1252 island of logic A*算法的應用： IDA*算法的應用，以及跳躍式搜索探索： 限深搜索，限次： 迭代加深搜索： 部分搜索+高效算法（比如二分匹配，動態規劃）： ZOJ milk bottle data: 剪枝優化探索： 可行性剪枝，最優性剪枝，調整搜索順序是常用的優化手段。 動態規劃 動態規劃最重要的就是狀態的選取，以及狀態轉移方程，另外還要考慮高效的預處理（以便更好更快的實現狀態轉移）。最常用的思想就是用枚舉最后一次操作。 狀態壓縮DP，又叫帶集合的動態規劃：題目特點是有一維的維數特別小。類似TSP問題的DP： 狀態劃分比較困難的題目： 樹形DP： 四邊形不等式的應用探索：四邊形不等式通常應用是把O(n^3)復雜度O(n^2) 高檔數據結構的應用 并查集的應用： 巧用并查集中的路徑壓縮思想： 堆的利用： 線段樹的應用： 總結用線段樹解題的方法 根據題目要求將一個區間建成線段樹，一般的題目都需要對坐標離散。建樹時，不要拘泥于線段樹這個名字而只將線段建樹，只要是表示區間，而且區間是由單位元素(可以是一個點、線段、或數組中一個值)組成的，都可以建線段樹；不要拘泥于一維，根據題目要求可以建立面積樹、體積樹等等 樹的每個節點根據題目所需，設置變量記錄要求的值 用樹形結構來維護這些變量：如果是求總數，則是左右兒子總數之和加上本節點的總數，如果要求最值，則是左右兒子的最大值再聯系本區間。利用每次插入、刪除時，都只對O(logL)個節點修改這個特點，在O(logL)的時間內維護修改后相關節點的變量。 在非規則刪除操作和大規模修改數據操作中，要靈活的運用子樹的收縮與葉子節點的釋放，避免重復操作。 Trie的應用：； Trie圖的應用探索： 后綴數組的應用研究： 在字符串處理當中，后綴樹和后綴數組都是非常有力的工具，其中后綴樹了解得比較多，關于后綴數組則很少見于國內的資料。其實后綴數組是后綴樹的一個非常精巧的替代品，它比后綴樹容易編程實現，能夠實現后綴樹的很多功能而時間復雜度也不太遜色，并且，它比后綴樹所占用的空間小很多。 樹狀數組的應用探索：； 計算幾何 掌握基本算法的實現。凸包的應用：； 半平面交算法的應用：； 幾何+模擬類題目：幾何設計好算法，模擬控制好精度。掃描法：； 轉化法：ZOJ 1606 將求所圍的格子數，巧妙的轉化為求多邊形的面積。離散法思想的應用：； 經典算法：找平面上的最近點對。 貪心 矩形切割 二分思想應用 活用經典算法 利用歸并排序算法思想求數列的逆序對數： 利用快速排序算法思想，查詢N個數中的第K小數： 博弈問題 博弈類題目通常用三類解法：第一類推結論； 第二類遞推，找N位置，P位置； 第三類SG函數的應用。第四類極大極小法，甚至配合上αβ剪枝。最難掌握的就是第四類極大極小法。 第一類：推結論。典型題目： 第二類：遞推。典型題目： 比如有向無環圖類型的博弈。在一個有向圖中，我們把選手I有必勝策略的初始位置稱為N位置(Next player winning)，其余的位置被稱為P位置(Previous player winning)。很顯然，P位置和N位置應該具有如下性質： 1． 所有的結束位置都是P位置。 2． 對于每一個N位置，至少存在一種移動可以將棋子移動到一個P位置。3． 對于每一個P位置，它的每一種移動都會將棋子移到一個N位置。 這樣，獲勝的策略就是每次都把棋子移動到一個P位置，因為在一個P位置，你的對手只能將棋子移動到一個N位置，然后你總有一種方法再把棋子移動到一個P位置。一直這樣移動，最后你一定會將棋子移動到一個結束位置（結束位置是P位置），這時你的對手將無法在移動棋子，你便贏得了勝利。 與此同時，得到了這些性質，我們便很容易通過倒退的方法求出哪些位置是P位置，哪些位置是N位置，具體的算法為： 1． 將所有的結束位置標為P位置。 2． 將所有能一步到達P位置的點標為N位置。 3． 找出所有只能到達N位置的點，將它們標為P位置。 4． 如果在第三步中沒有找到新的被標為P位置的點，則算法結束，否則轉到步驟2。這樣我們便確定了所有位置，對于題目給出的任一初始位置，我們都能夠很快確定出是選手I獲勝還是選手II獲勝了。第三類：SG函數的應用。 關于SG函數的基本知識：對于一個有向圖(X, F)來說，SG函數g是一個在X上的函數，并且它返回一個非負整數值，具體定義為 g(x)?min{n?0,n?g(y)對于所有y?F(x)} 1． 對于所有的結束位置x，g(x)= 0。 2． 對于每一個g(x)≠ 0的位置x，在它可以一步到達的位置中至少存在一個位置y使得g(y)= 0。 3．對于每一個g(x)＝ 0的位置x，所有可以由它一步到達的位置y都有g(y)≠ 0。 定理 如果g(xi)是第i個有向圖的SG函數值，i = 1,…,n，那么在由這n個有向圖組成的狀態的SG函數值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn) 第四類：極大極小法。 典型題目：ZOJ 1155：Triangle War ZOJ 1993：A Number Game 矩陣妙用 矩陣最基本的妙用就是利用快速乘法O（logn）來求解遞推關系（最基本的就是求Fibonacci數列的某項）和各種圖形變換，以及利用高斯消元法變成階梯矩陣。典型題目： 數學模型舉例 向量思想的應用： UVA 10089：注意降維和向量的規范化 ； 利用復數思想進行向量旋轉。 UVA 10253： 遞推 數代集合 數代集合的思想： ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一題：Intuitionistic Logic 用枚舉+數代集合思想優化，注意到題中有一句話：“You may assume that the number H = |H| of elements of H?doesn't exceed 100”，這句話告訴我們H的元素個數不會超過100，因此可以考慮用一個數代替一個集合，首先把所有的運算結果都用預處理算出來，到計算的時候只要用O(1)的復雜度就可以完成一次運算。 組合數學 Polya定理則是解決同構染色計數問題的有力工具。 補集轉化思想 ZOJ 單色三角形： 字符串相關 擴展的KMP算法應用：；最長回文串； 最長公共子串； 最長公共前綴； 填充問題 高精度運算 三維空間問題專題 無論什么問題，一旦擴展到三難空間，就變得很有難度了。三維空間的問題，很考代碼實現能力。 其它問題的心得 解決一些判斷同構問題的方法：同構的關鍵在于一一對應，而如果枚舉一一對應的關系，時間復雜度相當的高，利用最小表示，就能把一個事物的本質表示出來。求最小表示時，我們一定要仔細分析，將一切能區分兩個元素的條件都在最小表示中體現，而且又不能主觀的加上其他條件。得到最小表示后，我們往往還要尋求適當的、高效的匹配算法（例如KMP字符匹配之類的），來比較最小表示是否相同，這里常常要將我們熟悉的高效算法進行推廣第五篇：算法總結
點擊咨詢 