《算法設(shè)計與分析》課程教學(xué)大綱

1、PAGE PAGE 6算法設(shè)計與分析 教學(xué)大綱（71022408）一、說明（一）課程性質(zhì) 本課程是一門面向算法設(shè)計的計算機科學(xué)與技術(shù)專業(yè)的專業(yè)必修課程。通過對這門課程的學(xué)習(xí)和研究，掌握算法設(shè)計的主要方法，培養(yǎng)對算法的計算復(fù)雜性正確分析的能力，為獨立設(shè)計算法和對算法進行復(fù)雜性分析奠定堅實的理論基礎(chǔ)。（二）教學(xué)目的算法是計算機科學(xué)的核心。算法設(shè)計與分析是計算機科學(xué)與技術(shù)專業(yè)的重要必修課程。 通過該課程的學(xué)習(xí)，使學(xué)生在算法設(shè)計、算法優(yōu)化與算法分析等方面受到嚴(yán)格、系統(tǒng)的訓(xùn)練，從而能設(shè)計合適的算法解決實際問題，為后續(xù)專業(yè)課程的學(xué)習(xí)打下基礎(chǔ)。 本課程于必修課程程序設(shè)計和數(shù)據(jù)結(jié)構(gòu)之后開設(shè)，學(xué)生經(jīng)過這兩門課程

2、的學(xué)習(xí)已掌握常用的數(shù)據(jù)結(jié)構(gòu)和基本算法，也具備了編寫程序?qū)崿F(xiàn)算法的能力。 本課程將一步深化先修課程所學(xué)的內(nèi)容，強化學(xué)生的理論基礎(chǔ)和動手實踐能力；同時也適當(dāng)介紹若干算法研究領(lǐng)域的前沿課題，培養(yǎng)學(xué)生對算法研究的興趣。（三）教學(xué)內(nèi)容 課程的主要內(nèi)容包括： 算法分析的基本知識，漸進復(fù)雜度和大O記號，分治算法和遞歸關(guān)系，圖的搜索，最短路、最大團算法，貪心算法，動態(tài)規(guī)劃算法及其優(yōu)化，NP完全問題的搜索算法和近似算法等。 （四）教學(xué)時數(shù)講授: 54學(xué)時 實驗: 36學(xué)時總學(xué)時: 90學(xué)時（五）教學(xué)方式 講授為主, 討論與實驗為輔。二、本文理論部分第1章 算法概述教學(xué)要點：理解算法的概念。理解什么是程序，程序與

3、算法的區(qū)別和內(nèi)在聯(lián)系。掌握算法的計算復(fù)雜性概念。掌握算法漸近復(fù)雜性的數(shù)學(xué)表述。教學(xué)時數(shù)： 6學(xué)時教學(xué)內(nèi)容：1.1 算法與程序 （2學(xué)時） 介紹算法的基本特征：有限步、無歧義、可實現(xiàn)；講解描述算法的方式：偽代碼、流程圖和程序；給出簡單的算法例子：計算斐波那契數(shù)列前n項的算法；介紹算法與程序的區(qū)別與內(nèi)在聯(lián)系。1.2 算法復(fù)雜性分析 （4學(xué)時） 詳解算法時間復(fù)雜度和空間復(fù)雜度的概念；介紹最壞復(fù)雜度和平均復(fù)雜度的概念；詳解漸進復(fù)雜度的概念；給出大O記號的嚴(yán)格數(shù)學(xué)定義；通過不同復(fù)雜度算法運行時間的巨大差異來闡明降低算法復(fù)雜度的重要意義；詳解分析遞歸算法復(fù)雜度的主要方法：解遞歸方程；以計算斐波那契數(shù)列的兩

4、種算法為例，使學(xué)生對多項式時間算法和指數(shù)時間算法有直觀的認識。第2章 遞歸與分治策略教學(xué)要點：理解遞歸的概念。掌握設(shè)計有效算法的分治策略。 通過下面的范例學(xué)習(xí)分治策略設(shè)計技巧。（1）二分搜索技術(shù)； （2）大整數(shù)乘法；（3）Strassen矩陣乘法；（4）棋盤覆蓋；（5）合并排序和快速排序；（6）最接近點對問題；教學(xué)時數(shù)： 6學(xué)時教學(xué)內(nèi)容：2.1 分治算法的基本步驟 （2學(xué)時） 介紹分治算法的三個步驟：分解原問題為子問題，遞歸求解子問題，由子問題的解得到原問題的解。 詳解整數(shù)乘法的兩個算法：小學(xué)生算法和分治算法。 分析用分治策略進行乘法運算的時間復(fù)雜度。2.2 求解遞歸方程的通用算法 （1學(xué)時）

5、 介紹遞歸方程的概念。 介紹Master定理并分情況舉例其在求解遞歸方程上的應(yīng)用。2.3 分治算法的典型實例（3學(xué)時） 講解二分搜索、合并排序和快速排序算法、基于分治策略的矩陣乘法算法和基于分治策略的最接近點對算法，分析算法的時間復(fù)雜度。 第3章 動態(tài)規(guī)劃教學(xué)要點：理解動態(tài)規(guī)劃算法的概念。掌握動態(tài)規(guī)劃算法的基本要素（1）最優(yōu)子結(jié)構(gòu)性質(zhì)（2）重疊子問題性質(zhì) 掌握設(shè)計動態(tài)規(guī)劃算法的步驟。(1)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。(2)遞歸地定義最優(yōu)值。(3)以自底向上的方式計算出最優(yōu)值。(4)根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解教學(xué)時數(shù)： 10學(xué)時教學(xué)內(nèi)容：3.1 動態(tài)規(guī)劃算法的基本概念 （2學(xué)

6、時） 以計算斐波那契數(shù)列第n項為例講解“重復(fù)子問題”的概念；講解動態(tài)規(guī)劃算法的目標(biāo)：避免重復(fù)對子問題進行計算；以有向無環(huán)圖的最短路為例詳解最優(yōu)子結(jié)構(gòu)、狀態(tài)和狀態(tài)轉(zhuǎn)移方程的概念；講解動態(tài)規(guī)劃算法復(fù)雜度分析的方法。3.2 序列上的動態(tài)規(guī)劃 （4學(xué)時）詳解最長上升子序列問題的動態(tài)規(guī)劃算法及其復(fù)雜度分析；詳解字符串編輯距離問題的動態(tài)規(guī)劃算法及其復(fù)雜度分析；詳解背包問題及其變種（可重復(fù)背包等）的動態(tài)規(guī)劃算法及其復(fù)雜度分析；詳解矩陣連乘問題的動態(tài)規(guī)劃算法及其復(fù)雜度分析。3.3 動態(tài)規(guī)劃算法的優(yōu)化（2學(xué)時） 以最長上升子序列問題為例講解如何利用單調(diào)性優(yōu)化動態(tài)規(guī)劃算法；以最優(yōu)二叉搜索樹為例講解如何利用四邊形不

7、等式優(yōu)化動態(tài)規(guī)劃算法（選講）。3.4 其它結(jié)構(gòu)上的動態(tài)規(guī)劃 （2學(xué)時）以哈密頓路徑為例講解集合上的動態(tài)規(guī)劃；以樹上的獨立集為例講解樹型動態(tài)規(guī)劃；以最優(yōu)三角剖分為例講解凸多邊形上的動態(tài)規(guī)劃（選講）。 第4章 貪心算法教學(xué)要點：理解貪心算法的概念。掌握貪心算法的基本要素 （1）最優(yōu)子結(jié)構(gòu)性質(zhì)（2）貪心選擇性質(zhì) 理解貪心算法與動態(tài)規(guī)劃算法的差異 理解貪心算法的一般理論 通過應(yīng)用范例學(xué)習(xí)貪心設(shè)計策略。（1）活動安排問題；（2）最優(yōu)裝載問題；（3）哈夫曼編碼；（4）單源最短路徑；（5）最小生成樹；教學(xué)時數(shù)： 6學(xué)時教學(xué)內(nèi)容：4.1 貪心算法的策略 （2學(xué)時） 回顧最小生成樹的兩種算法（Kruskal算法

8、和Prim算法）中所采用的貪心策略；證明Kruskal算法和Prim算法的正確性；利用并查集實現(xiàn)Kruskal算法4.2 貪心算法的典型實例 （4學(xué)時）講解哈夫曼編碼的貪心算法及其最優(yōu)性證明；講解活動安排問題、最優(yōu)裝載問題的貪心算法及其正確性證明。 第5章 回溯法教學(xué)要點：理解回溯法的深度優(yōu)先搜索策略。掌握用回溯法解題的算法框架（1）遞歸回溯（2）迭代回溯（3）子集樹算法框架（4）排列樹算法框架 教學(xué)時數(shù)： 7學(xué)時教學(xué)內(nèi)容：5.1 回溯算法的策略 （2學(xué)時） 以n皇后問題為例，介紹回溯算法的基本思想及算法框架5.2 回溯算法的典型實例 （5學(xué)時）講解0-1背包問題的回溯算法及其與動態(tài)規(guī)劃算法的

9、比較；講解旅行售貨員問題、圖的著色問題和最大團問題的回溯算法及其效率分析。 第6章 分支限界法教學(xué)要點：理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架（1）隊列式(FIFO)分支限界法（2）優(yōu)先隊列式分支限界法 通過應(yīng)用范例學(xué)習(xí)分支限界法的設(shè)計策略。（1）單源最短路徑問題（2）裝載問題；（3）布線問題（4）0-1背包問題；（5）最大團問題；（6）旅行售貨員問題教學(xué)時數(shù)： 7學(xué)時教學(xué)內(nèi)容：6.1 分支限界的基本思想 （2學(xué)時） 以單源最短路徑問題為例，介紹分支限界算法的基本思想及算法框架，詳解分支限界算法中上界和下界的概念；以哈密頓回路問題為例詳解局部搜索算法；介紹局部搜索算法中跳出局部

10、最優(yōu)的策略6.2 分支限界法的典型實例 （5學(xué)時）講解0-1背包問題的分支限界算法及其與動態(tài)規(guī)劃算法、回溯算法的比較；講解旅行售貨員問題、裝載問題和最大團問題的回溯算法及其效率分析。 第7章 概率算法教學(xué)要點：理解產(chǎn)生偽隨機數(shù)的算法掌握數(shù)值隨機化算法的設(shè)計思想 掌握蒙特卡羅算法的設(shè)計思想 掌握拉斯維加斯算法的設(shè)計思想 掌握舍伍德算法的設(shè)計思想教學(xué)時數(shù)： 4學(xué)時教學(xué)內(nèi)容：7.1 隨機數(shù) （0.5學(xué)時） 介紹線性同余法產(chǎn)生偽隨機數(shù)。7.2 數(shù)值概率算法 （0.5學(xué)時）以隨機投點法計算值為例介紹數(shù)值概率算法的思想。7.3 舍伍德（Sherwood）算法 （1學(xué)時） 以快速排序算法為例，介紹舍伍德算法

11、的思想。7.4 拉斯維加斯（Las Vegas）算法（1學(xué)時） 以n皇后問題為例，介紹拉斯維加斯算法思想及特點。7.5 蒙特卡羅（Monte Carlo）算法（1學(xué)時）以素數(shù)測試問題為例，介紹蒙特卡羅算法的思想及特點。 第8章 NP完全性理論與近似算法教學(xué)要點：掌握P、NP和NPC類問題基本概念了解一些典型的NPC問題了解處理NPC問題的方法教學(xué)時數(shù)： 8學(xué)時教學(xué)內(nèi)容：8.1 NP問題的基本概念 （3學(xué)時） 回顧多項式時間算法和指數(shù)時間算法的概念；詳解多項式時間歸約的概念；介紹多項式時間歸約的例子；詳解多項式時間驗證解的概念；詳解P問題和NP問題的概念；詳解NP完全和NP難的概念；介紹第一個被

12、證明為NP完全的問題：SAT問題。8.2 NP完全問題的典型實例 （2學(xué)時） 講解3-SAT問題的NP完全性及如何將SAT問題歸約為3-SAT問題；講解圖論中的完全子圖（團）問題及如何將完全子圖問題歸約為3-SAT問題；講解頂點覆蓋問題及如何將其歸約為頂點覆蓋問題；講解哈密頓回路問題及如何將其歸約為頂點覆蓋問題。8.3 處理NP完全問題的方法 （3學(xué)時） 詳解頂點覆蓋問題和哈密頓回路問題的近似算法，并給出其近似程度的證明。實驗部分（一）基本要求牢固掌握算法設(shè)計的基本策略，體會每一種具體算法的設(shè)計要點，以期達到融會貫通的效果，可以綜合應(yīng)用多種策略，設(shè)計合適的算法有效的解決實際問題。（二）實驗項目

13、總表序號實驗項目名稱學(xué)時數(shù)項目類別項目類型1遞歸與分治算法設(shè)計6設(shè)計必做2動態(tài)規(guī)劃算法設(shè)計8設(shè)計必做3貪心算法設(shè)計4設(shè)計必做4回溯算法設(shè)計6設(shè)計必做5分支限界算法設(shè)計6設(shè)計必做60-1背包問題算法設(shè)計6綜合設(shè)計必做（三）實驗項目內(nèi)容及要求 實驗項目1、布置至少3道課后實驗習(xí)題，內(nèi)容覆蓋遞歸與分治算法的設(shè)計。 實驗項目2、布置2次，每次至少3道課后實驗習(xí)題，題目以對給定問題設(shè)計動態(tài)規(guī)劃算法為主，內(nèi)容應(yīng)覆蓋多種類型的動態(tài)規(guī)劃。 實驗項目3、布置至少2道課后實驗習(xí)題，內(nèi)容主要是對給出的問題設(shè)計貪心算法。 實驗項目4、布置至少3道課后實驗習(xí)題，以對給定問題設(shè)計回溯算法。 實驗項目5、布置至少3道課后實

14、驗習(xí)題，以對給定問題設(shè)計分支限界算法。 實驗項目6、就0-1背包這一NP難問題設(shè)計多個算法，并通過實驗比較算法的優(yōu)劣。三、參考書目1、T. Cormen， C. Leiserson， R. Rivest and C. Stein. Introduction to Algorithms, 2th Ed. The MIT Press, 2001, ISBN 0-262-33293-3影印版：算法導(dǎo)論（第2版），北京：高等教育出版社，2007，ISBN 7-040-11050-0中譯版：潘金貴等譯，算法導(dǎo)論（第2版），北京：機械工業(yè)出版社，2006，ISBN 7-111-18777-62、Algorithm Design（影印版）/（美