算法導論學習報告參考

算法導論學習報告參考

第一部分 學習內容歸納

“計算機算法是以一步接一步的方式來詳細描述計算機如何將輸入轉化爲所要求的輸出的過程，或者說，算法是對計算機上執行的計算過程的具體描述。”（參考文獻：百度百科）《算法設計與分析》是一門面向設計，在計算機科學中處於核心地位的課程。這門課程主要講授了在計算機應用中經常遇到的問題和求解的方法，分治法、動態規劃法、隨機算法等設計算法的基本原理、技巧和算法複雜性的分析，以及計算理論簡介。

第一部分“概論和數學準備”在簡單瞭解了算法的基本概念和複雜性、研究步驟等幾個重要知識點後，着重學習了算法的數學基礎，包括生成函數、差方方程的求解等，主要適用於求解算法的時間複雜性。

“任何可以用計算機求解的問題所需要的計算時間都與其規模有關：問題的規模越小，解題所需的計算時間往往也越短，從而也就比較容易處理。”（參考文獻：《計算機算法設計與分析（第3版）》）而第二部分介紹的算法常用技術之首——分治法就運用了這樣的思想。分治法的要領在於Divide（子問題的劃分）-Conquer（子問題的求解）-Combine（子問題解的組合）。由於子問題和原問題是同類的，遞歸的思想在分治法中顯得尤其重要，它們經常同時運用在算法設計中。這部分內容從Select（求第k小元）算法，尋找最近點對算法和快速傅立葉變換FFT等實際應用中深化對分治法思想的理解，同時也強調了平衡思想的重要性。

第三部分“動態規劃”與分治法類似，同樣是把問題層層分解成規模越來越小的同類型的子問題。但與分治法不同的是，分治法中的子問題通常是相互獨立的，而動態規劃法中的子問題很多都是重複的，因此通常採用遞推的方法以避免重複計算。然而，也不是所有的情況下都採用遞推法，當有大量的子問題無需求解時，更好的方式是採用動態規劃法的變形——備忘錄方法。通常需要用到動態規劃法求解的問題都具有子問題的高度重複性和最優子結構性質兩大特徵，這也是我們分析問題和設計算法時的關鍵點。最長公共子序列LCS問題和最優二分搜尋樹就是從動態規劃法的兩個主要特徵角度分析問題，進而設計出相應的解決算法的。而這部分內容中的另一個問題——流水作業調度，則告訴我們採用動態規劃時偶爾也得不到高效的算法，我們要學會將已有的知識靈活運用，適當加工。

第四部分“集合算法”中首先介紹了一種分析算法複雜度的手法——平攤分析（Amortized Analysis）。與之前我們所接觸的算法分析方法即逐一考慮執行每條指令所需的時間複雜度再進行累加的方法不同，平攤分析是對若干條指令從整體角度考慮其時間複雜度，透過這樣的方法獲得的時間複雜度更加貼近實際的情況。平攤分析的主要方法有聚集方法，會計方法和勢能方法。聚集方法將指令的時間複雜度分類計算再相加；會計方法採用了耗費提前計算的思想；勢能方法引入了勢函數的概念，從每步操作的數據結構狀態和勢函數的關係角度分析得出操作的平攤代價。“集合算法”這一部分主要分析了Union（合併集合）和Find（給出元素所在集合名）這兩種運算。從上學期的《數據結構》課程的學習中，我們就已經發現集合和樹之間的關係是密不可分的，我們經常用樹結構來表示集合。而2-3樹是一種特殊的每個內結點都只有2個或3個兒子的樹，廣泛的應用於可實現Member（查找）、Insert（插入）、Delete（刪除）操作的數據結構——字典，可實現Insert、Delete、Union和Min（查找最小葉結點）的數據結構——可並堆，可實現Insert、Delete、Find、Concatenate（保序合併）和Split（分裂）的數據結構——可連接隊列等。

之前討論的算法中每一步計算步驟都是確定的，然而第五部分“隨機算法”中所討論的隨機化算法允許算法在執行的過程中隨機的選擇下一個執行步驟。“在許多情況下，當算法在執行過程中面臨一個選擇時，隨機性選擇常比最優選擇省時。因此隨機化算法可在很大程度上降低算法的複雜度。”（參考文獻：《計算機算法設計與分析（第3版）》）隨機化算法對問題用同一輸入算法求解時可能會得到完全不同的效果，這是它的基本特徵——算法在執行時產生真正隨機的結果。一般情況下，隨即算法分爲兩大類——Las Vegas算法和Monte Carlo算法。Las Vegas算法不會得到不準確的結果，但有時卻會找不到解，這時就需要重複調用算法進行計算。而Monte Carlo算法用來求取問題的準確解。它能保證求得一個截但無法保證其正確性，這是Monte Carlo算法的主要缺點。不過由於每次執行的算法都是獨立的，透過反覆執行算法可以有效的將發生錯誤的概率大大降低。另外，對於一個已經有了平均性質較好的確定性算法的問題，透過Sherwood隨機化方法可將確定性算法改成隨機算法，以解決其在最壞情況下效率不高的問題，提高了算法的性能。隨機化算法爲很多用確定性算法難以很好的解決的難解問題提供了高效的解決途徑，具有很高的實用價值。

第六部分“NP完全性理論與近似算法”首先介紹了計算模型、確定性和非確定性圖靈（Turing）機。“在進行問題的計算複雜性分析之前，首先必須建立求解問題所用的計算模型，包括定義該計算模型中所用的基本運算，其目的是使問題的計算複雜性分析有一個共同的客觀尺度。”（參考文獻：《計算機算法設計與分析（第3版）》）隨機存取機RAM（Random Access Machine）、隨機存取存儲程序機RASP（Random Access Stored Program Machine）和圖靈機（Turing Machine）是三種基本的計算模型。RAM和RASP的相同處在於都有各種尋址指令且時間複雜性數量級相同，不同處在於RAM程序的不允許修改和RASP程序的可修改性。RAM程序和RASP程序之間可以相互模擬。圖靈機可以計算函數部分的遞歸函數，涉及到遞歸可枚舉集、遞歸集、原始遞歸集、部分遞歸函數、完全遞歸函數和原始遞歸函數。確定性圖靈機DTM和非確定性圖靈機NDTM的差別在於，NDTM的每一步動作允許有若干個選擇，且它的ID序列通常是由樹描述的，而DTM的ID序列是線性的。這部分接着又進一步深入介紹NP完全性理論和解NP難問題的近似算法。NP是能在多項式時間內被一臺NDTM所接受的語言。NP完全問題是當前計算機算法領域的熱點研究課題。

　第二部分 學習心得

學習之初剛開始看到那些函數以及一大堆數學公式的時候都覺得頭大，一時都摸不清這些複雜的式子是用來幹什麼的，甚至都以爲學的不是算法而是高數了。後來在接觸到分治法等算法思想後，在老師講解的例子中學會了對那些式子的應用。課後也在實際的應用中真正掌握了第一部分所講的數學知識，懂得了那些數學基礎對算法研究的重要性。所以說，只有當自己學會在問題中運用了，纔算是真正學會了那些知識。

算法的思想看着都似乎簡單易懂，就算思路複雜的只要認真研究也比較容易理解，但要真正的在實驗中、在實際問題的解決過程中運用出來就不是那麼容易的一件事了。對於同一個問題，往往都有好幾種不同的算法，就像要求分別運用。