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

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

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

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

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

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

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

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

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

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

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

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

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

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

14、驗(yàn)習(xí)題，以對給定問題設(shè)計(jì)分支限界算法。 實(shí)驗(yàn)項(xiàng)目6、就0-1背包這一NP難問題設(shè)計(jì)多個(gè)算法，并通過實(shí)驗(yàn)比較算法的優(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版），北京：機(jī)械工業(yè)出版社，2006，ISBN 7-111-18777-62、Algorithm Design（影印版）/（美