計算機算法基礎(chǔ)_復(fù)習(xí)要點(華中科技大學(xué)博士)ppt課件

1、復(fù)習(xí)復(fù)習(xí)第一章 導(dǎo)引掌握：1.算法的定義及其性質(zhì)(1.1節(jié))2.算法分析的根底知識(1.2節(jié)) 重要的商定和假設(shè) 關(guān)于O， 的定義了解：3.SPARKS言語(1.3節(jié))4.常用數(shù)據(jù)構(gòu)造(1.4節(jié))5.遞歸與消去遞歸(1.5節(jié))第二章 分治法掌握：1.根本知識 分治法的根本思想：2.1節(jié) 關(guān)系式的化簡： 1遞推關(guān)系式的化簡 作業(yè)題 2常用求和公式 在統(tǒng)計語句的頻率時，求和公式的普通方式為： h(n)i)()(ngif)(2/ ) 1(n21nnini特殊方式)(11knikni)(6/ ) 12)(1(n312nnnini第二章 分治法續(xù)2.重要實例 二分檢索算法及其算法分析：2.2節(jié) 基于PA

2、RTITION的選擇算法：2.6節(jié)3.分類算法及其運用：2.4、2.5節(jié)普通了解：4.找最大和最小元素：2.3節(jié)5.最壞情況時間是O(n)的選擇算法：2.3節(jié)后半部分第三章 貪婪方法掌握：1.根本知識3.1節(jié) 根本概念：約束條件、目的函數(shù)、可行解、 最優(yōu)解 貪婪方法的適用對象：求輸入的一個可行的 子集 貪婪方法的普通戰(zhàn)略：度量規(guī)范 貪婪解是問題最優(yōu)解證明的根本思想第三章 貪婪方法續(xù)2.重要實例背包問題：最優(yōu)度量規(guī)范的選擇、最優(yōu)解的證明 3.2節(jié)帶有限期的作業(yè)排序問題：度量規(guī)范和處置戰(zhàn)略、 作業(yè)集合可行性的斷定3.3節(jié)單源最短途徑：給出一個圖，可以寫出算法的執(zhí)行 軌跡3.6節(jié) 例題和實驗4526

3、311010153104152030迭代選取的結(jié)點S DIST (1) (2) (3) (4) (5) (6) 置初值1234325611,31,3,21,3,2,51,3,2,5,6 0 20 15 + + + 0 19 15 + 25 + 0 19 15 29 25 + 0 19 15 29 25 28 0 19 15 29 25 28 第三章 貪婪方法續(xù)普通了解：3.最優(yōu)歸并方式3.4節(jié)4.最小生成樹算法： 3.5節(jié) Prim 算法堅持連通 Kruskal算法不堅持連通 要求：給出圖例，可以可以畫出相應(yīng)的最小 本錢生成樹 第四章 動態(tài)規(guī)劃掌握：1.根本知識4.1節(jié) 1根本概念 多階段決策

4、過程 最優(yōu)性原理 2動態(tài)規(guī)劃求解的普通戰(zhàn)略： 證明最優(yōu)性原理成立 列出遞推關(guān)系式：向前處置法、向后處置法第四章 動態(tài)規(guī)劃續(xù)2.重要實例多段圖問題：段的定義、 4.2節(jié) 基于多段圖的多階段決策過程、 導(dǎo)出的遞推關(guān)系式及算法最優(yōu)二分檢索樹：最優(yōu)二分檢索樹的定義、 (4.4節(jié)) 最優(yōu)二分檢索樹的多階段決策過程、 遞推關(guān)系式、 基于遞推關(guān)系式的W,C,R的計算 習(xí)題0/1背包問題：0/1背包問題的定義、向后遞推戰(zhàn)略、 (4.5節(jié)) 序偶Si的表示方法及其計算過程 習(xí)題第四章 動態(tài)規(guī)劃續(xù)普通了解：3.每對結(jié)點之間的最短途徑(4.3節(jié))4.最優(yōu)二分檢索樹算法的實現(xiàn)(4.4節(jié))5.0/1背包問題算法的實現(xiàn)(4.5節(jié))第五章 根本檢索和周游方法掌握：1.根本概念：檢索、周游2.圖的檢索算法 寬度優(yōu)先檢索：BFS 深度優(yōu)先檢索：DFS D_SEARCH要求：掌握算法的處置規(guī)那么，對給定的圖，可以寫出各算法檢索的結(jié)點序列。BFS檢測序列： 1 2 3 4 5 6 7 8 DFS檢測序列： 1 2 4 8 5 6 3 7 D_Search檢測序列： 1 3 7 8 5 4