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