算法導論學(xué)習報告參考
算法導論學(xué)習報告參考
第一部分 學(xué)習內容歸納
“計算機算法是以一步接一步的方式來(lái)詳細描述計算機如何將輸入轉化為所要求的輸出的過(guò)程，或者說(shuō)，算法是對計算機上執行的計算過(guò)程的具體描述。”（參考文獻：百度百科）《算法設計與分析》是一門(mén)面向設計，在計算機科學(xué)中處于核心地位的課程。這門(mén)課程主要講授了在計算機應用中經(jīng)常遇到的問(wèn)題和求解的方法，分治法、動(dòng)態(tài)規劃法、隨機算法等設計算法的基本原理、技巧和算法復雜性的分析，以及計算理論簡(jiǎn)介。
第一部分“概論和數學(xué)準備”在簡(jiǎn)單了解了算法的基本概念和復雜性、研究步驟等幾個(gè)重要知識點(diǎn)后，著(zhù)重學(xué)習了算法的數學(xué)基礎，包括生成函數、差方方程的求解等，主要適用于求解算法的時(shí)間復雜性。
“任何可以用計算機求解的問(wèn)題所需要的計算時(shí)間都與其規模有關(guān)：?jiǎn)?wèn)題的規模越小，解題所需的計算時(shí)間往往也越短，從而也就比較容易處理。”（參考文獻：《計算機算法設計與分析（第3版）》）而第二部分介紹的算法常用技術(shù)之首——分治法就運用了這樣的思想。分治法的要領(lǐng)在于Divide（子問(wèn)題的劃分）-Conquer（子問(wèn)題的求解）-Combine（子問(wèn)題解的組合）。由于子問(wèn)題和原問(wèn)題是同類(lèi)的，遞歸的思想在分治法中顯得尤其重要，它們經(jīng)常同時(shí)運用在算法設計中。這部分內容從Select（求第k小元）算法，尋找最近點(diǎn)對算法和快速傅立葉變換FFT等實(shí)際應用中深化對分治法思想的理解，同時(shí)也強調了平衡思想的重要性。
第三部分“動(dòng)態(tài)規劃”與分治法類(lèi)似，同樣是把問(wèn)題層層分解成規模越來(lái)越小的同類(lèi)型的子問(wèn)題。但與分治法不同的是，分治法中的子問(wèn)題通常是相互獨立的，而動(dòng)態(tài)規劃法中的子問(wèn)題很多都是重復的，因此通常采用遞推的方法以避免重復計算。然而，也不是所有的情況下都采用遞推法，當有大量的子問(wèn)題無(wú)需求解時(shí)，更好的方式是采用動(dòng)態(tài)規劃法的變形——備忘錄方法。通常需要用到動(dòng)態(tài)規劃法求解的問(wèn)題都具有子問(wèn)題的高度重復性和最優(yōu)子結構性質(zhì)兩大特征，這也是我們分析問(wèn)題和設計算法時(shí)的關(guān)鍵點(diǎn)。最長(cháng)公共子序列LCS問(wèn)題和最優(yōu)二分搜索樹(shù)就是從動(dòng)態(tài)規劃法的兩個(gè)主要特征角度分析問(wèn)題，進(jìn)而設計出相應的解決算法的。而這部分內容中的另一個(gè)問(wèn)題——流水作業(yè)調度，則告訴我們采用動(dòng)態(tài)規劃時(shí)偶爾也得不到高效的算法，我們要學(xué)會(huì )將已有的知識靈活運用，適當加工。
第四部分“集合算法”中首先介紹了一種分析算法復雜度的手法——平攤分析（Amortized Analysis）。與之前我們所接觸的算法分析方法即逐一考慮執行每條指令所需的時(shí)間復雜度再進(jìn)行累加的方法不同，平攤分析是對若干條指令從整體角度考慮其時(shí)間復雜度，通過(guò)這樣的方法獲得的時(shí)間復雜度更加貼近實(shí)際的情況。平攤分析的主要方法有聚集方法，會(huì )計方法和勢能方法。聚集方法將指令的時(shí)間復雜度分類(lèi)計算再相加；會(huì )計方法采用了耗費提前計算的思想；勢能方法引入了勢函數的概念，從每步操作的數據結構狀態(tài)和勢函數的關(guān)系角度分析得出操作的平攤代價(jià)。“集合算法”這一部分主要分析了Union（合并集合）和Find（給出元素所在集合名）這兩種運算。從上學(xué)期的《數據結構》課程的學(xué)習中，我們就已經(jīng)發(fā)現集合和樹(shù)之間的關(guān)系是密不可分的，我們經(jīng)常用樹(shù)結構來(lái)表示集合。而2-3樹(shù)是一種特殊的每個(gè)內結點(diǎn)都只有2個(gè)或3個(gè)兒子的樹(shù)，廣泛的應用于可實(shí)現Member（查找）、Insert（插入）、Delete（刪除）操作的數據結構——字典，可實(shí)現Insert、Delete、Union和Min（查找最小葉結點(diǎn)）的數據結構——可并堆，可實(shí)現Insert、Delete、Find、Concatenate（保序合并）和Split（分裂）的數據結構——可連接隊列等。
之前討論的算法中每一步計算步驟都是確定的，然而第五部分“隨機算法”中所討論的隨機化算法允許算法在執行的過(guò)程中隨機的選擇下一個(gè)執行步驟。“在許多情況下，當算法在執行過(guò)程中面臨一個(gè)選擇時(shí)，隨機性選擇常比最優(yōu)選擇省時(shí)。因此隨機化算法可在很大程度上降低算法的復雜度。”（參考文獻：《計算機算法設計與分析（第3版）》）隨機化算法對問(wèn)題用同一輸入算法求解時(shí)可能會(huì )得到完全不同的效果，這是它的基本特征——算法在執行時(shí)產(chǎn)生真正隨機的結果。一般情況下，隨即算法分為兩大類(lèi)——Las Vegas算法和Monte Carlo算法。Las Vegas算法不會(huì )得到不準確的結果，但有時(shí)卻會(huì )找不到解，這時(shí)就需要重復調用算法進(jìn)行計算。而Monte Carlo算法用來(lái)求取問(wèn)題的準確解。它能保證求得一個(gè)截但無(wú)法保證其正確性，這是Monte Carlo算法的主要缺點(diǎn)。不過(guò)由于每次執行的算法都是獨立的，通過(guò)反復執行算法可以有效的將發(fā)生錯誤的概率大大降低。另外，對于一個(gè)已經(jīng)有了平均性質(zhì)較好的確定性算法的問(wèn)題，通過(guò)Sherwood隨機化方法可將確定性算法改成隨機算法，以解決其在最壞情況下效率不高的問(wèn)題，提高了算法的性能。隨機化算法為很多用確定性算法難以很好的解決的難解問(wèn)題提供了高效的解決途徑，具有很高的實(shí)用價(jià)值。
第六部分“NP完全性理論與近似算法”首先介紹了計算模型、確定性和非確定性圖靈（Turing）機。“在進(jìn)行問(wèn)題的計算復雜性分析之前，首先必須建立求解問(wèn)題所用的計算模型，包括定義該計算模型中所用的基本運算，其目的是使問(wèn)題的計算復雜性分析有一個(gè)共同的客觀(guān)尺度。”（參考文獻：《計算機算法設計與分析（第3版）》）隨機存取機RAM（Random Access Machine）、隨機存取存儲程序機RASP（Random Access Stored Program Machine）和圖靈機（Turing Machine）是三種基本的計算模型。RAM和RASP的相同處在于都有各種尋址指令且時(shí)間復雜性數量級相同，不同處在于RAM程序的不允許修改和RASP程序的可修改性。RAM程序和RASP程序之間可以相互模擬。圖靈機可以計算函數部分的遞歸函數，涉及到遞歸可枚舉集、遞歸集、原始遞歸集、部分遞歸函數、完全遞歸函數和原始遞歸函數。確定性圖靈機DTM和非確定性圖靈機NDTM的差別在于，NDTM的每一步動(dòng)作允許有若干個(gè)選擇，且它的ID序列通常是由樹(shù)描述的，而DTM的ID序列是線(xiàn)性的。這部分接著(zhù)又進(jìn)一步深入介紹NP完全性理論和解NP難問(wèn)題的近似算法。NP是能在多項式時(shí)間內被一臺NDTM所接受的語(yǔ)言。NP完全問(wèn)題是當前計算機算法領(lǐng)域的熱點(diǎn)研究課題。
第二部分 學(xué)習心得
學(xué)習之初剛開(kāi)始看到那些函數以及一大堆數學(xué)公式的時(shí)候都覺(jué)得頭大，一時(shí)都摸不清這些復雜的式子是用來(lái)干什么的，甚至都以為學(xué)的不是算法而是高數了。后來(lái)在接觸到分治法等算法思想后，在老師講解的例子中學(xué)會(huì )了對那些式子的應用。課后也在實(shí)際的應用中真正掌握了第一部分所講的數學(xué)知識，懂得了那些數學(xué)基礎對算法研究的重要性。所以說(shuō)，只有當自己學(xué)會(huì )在問(wèn)題中運用了，才算是真正學(xué)會(huì )了那些知識。
算法的思想看著(zhù)都似乎簡(jiǎn)單易懂，就算思路復雜的只要認真研究也比較容易理解，但要真正的在實(shí)驗中、在實(shí)際問(wèn)題的解決過(guò)程中運用出來(lái)就不是那么容易的一件事了。對于同一個(gè)問(wèn)題，往往都有好幾種不同的算法，就像要求分別運用。
【算法導論學(xué)習報告參考】相關(guān)文章：
學(xué)習報告的格式參考04-12
超聲報告模板參考02-15
測試報告參考范例02-15
關(guān)于公文報告的格式參考12-24
社區任職報告參考范文03-19
關(guān)于 期貨報告范文參考03-07
《中西醫結合導論》的學(xué)習心得體會(huì )（精選10篇）11-06
學(xué)校工作報告參考03-25
高中英語(yǔ)結題報告_參考02-15