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