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

1、算法設(shè)計Algorithm Design一、課程基本情況課程類別：專業(yè)任選課課程學(xué)分：2 學(xué)分課程總學(xué)時：32 學(xué)時，其中講課： 20學(xué)時，實(shí)驗(yàn)（含上機(jī)）： 12 學(xué)時課程性質(zhì)：選修開課學(xué)期：第4學(xué)期先修課程：數(shù)據(jù)結(jié)構(gòu) 適用專業(yè)：計算機(jī)科學(xué)與技術(shù)，軟件工程教 材：王曉東，計算機(jī)算法設(shè)計與分析(第四版)，電子工業(yè)出版社，2013開課單位：計算機(jī)與軟件學(xué)院 軟件工程系二、課程性質(zhì)、教學(xué)目標(biāo)和任務(wù)隨著計算機(jī)的廣泛應(yīng)用，對計算機(jī)算法的研究變得日益重要。本課程將覆蓋計算機(jī)軟件實(shí)現(xiàn)中的大部分算法，并具有一定的深度和廣度，使學(xué)生對計算機(jī)常用算法有一個全盤的了解；本課程首先介紹計算復(fù)雜性的定義和算法分析的基本

2、方法，結(jié)合計算機(jī)科學(xué)及應(yīng)用領(lǐng)域中常見的有代表性的非數(shù)值算法，介紹了幾種重要的算法設(shè)計方法：分治法、動態(tài)規(guī)劃、貪心法、回溯法、分支限界法以及NP完全問題。使學(xué)生在掌握各種算法的同時，掌握算法分析的基本方法和技巧。本課程的任務(wù)是：培養(yǎng)學(xué)生具有針對給定問題設(shè)計和實(shí)現(xiàn)高效算法的能力。主要包括以下三個方面：1.通過對常用的、有代表性的算法的研究，讓學(xué)生理解并掌握算法設(shè)計的基本技術(shù)；2.培養(yǎng)學(xué)生分析算法復(fù)雜度的初步能力，鍛煉其邏輯思維能力和想象力，并使之了解算法理論的發(fā)展；3.鼓勵學(xué)生運(yùn)用算法知識解決各自學(xué)科的實(shí)際問題，培養(yǎng)他們的獨(dú)立科研能力和理論聯(lián)系實(shí)際的能力。三、教學(xué)內(nèi)容和要求第1章 算法概述（2學(xué)時

3、）1.1算法問題求解基礎(chǔ)（1學(xué)時）（1）了解算法與程序的概念；（2）了解為什么學(xué)習(xí)算法； （3）理解問題求解過程； （4）理解系統(tǒng)生命周期；重點(diǎn)：問題求解過程、系統(tǒng)生命周期；難點(diǎn)：系統(tǒng)生命周期；1.2算法復(fù)雜度（1學(xué)時）（1）了解影響程序運(yùn)行時間的因素； （2）理解使用程序步分析算法； （3）理解算法的空間復(fù)雜度；（3）理解算法的空間復(fù)雜度；（3）掌握使用大O記號、W記號、Q記號表示算法復(fù)雜度的方法；重點(diǎn)：根據(jù)程序步推算該算法的時間漸近復(fù)雜度；難點(diǎn)：程序步的統(tǒng)計以及根據(jù)程序步如何推算該算法的時間漸近復(fù)雜度；第2章 遞歸與分治策略（4學(xué)時）2.1遞歸與分治（2學(xué)時）（1）了解遞歸的概念； （2）

4、理解分治法的基本思想； （3）掌握分析遞歸算法時間復(fù)雜度的計算方法；重點(diǎn)：掌握分析遞歸算法時間復(fù)雜度的計算方法；難點(diǎn)：掌握分析遞歸算法時間復(fù)雜度的計算方法；2.2分治策略設(shè)計技巧（2學(xué)時）（1）掌握用分治策略求最大最小元問題； （2）掌握用分治策略進(jìn)行二分搜索； （3）掌握用分治策略進(jìn)行合并排序和快速排序；（4）掌握用分治策略完成Strassen矩陣乘法；重點(diǎn)：用分治策略進(jìn)行合并排序和快速排序，用分治策略完成Strassen矩陣乘法；難點(diǎn)：用分治策略完成Strassen矩陣乘法。第3章 動態(tài)規(guī)劃（4學(xué)時）3.1動態(tài)規(guī)劃基本概念（2學(xué)時）（1）了解動態(tài)規(guī)劃算法的概念與步驟； （2）理解動態(tài)規(guī)劃算

5、法與分治法、貪心法的異同；（3）掌握動態(tài)規(guī)劃算法的基本要素最優(yōu)子結(jié)構(gòu)性質(zhì)；重疊子問題性質(zhì)；（4）掌握設(shè)計動態(tài)規(guī)劃算法的步驟；重點(diǎn)：掌握動態(tài)規(guī)劃算法的基本要素：最優(yōu)子結(jié)構(gòu)性質(zhì)；重疊子問題性質(zhì)；掌握設(shè)計動態(tài)規(guī)劃算法的步驟；難點(diǎn)：理解并掌握動態(tài)規(guī)劃算法的基本要素：最優(yōu)子結(jié)構(gòu)性質(zhì)；重疊子問題性質(zhì)。3.2動態(tài)規(guī)劃算法應(yīng)用（2學(xué)時）（1）掌握多段圖問題、關(guān)鍵路徑問題算法的設(shè)計與分析；（2）掌握最長公共子序列問題的算法設(shè)計與分析；（3）掌握每對結(jié)點(diǎn)間的最短路徑問題的算法設(shè)計與分析；（4）掌握0/1背包問題的算法設(shè)計與分析；重點(diǎn)：掌握關(guān)鍵路徑問題算法的設(shè)計與分析；掌握0/1背包問題的算法設(shè)計與分析；難點(diǎn)：掌握

6、0/1背包問題的算法設(shè)計與分析；掌握最長公共子序列問題的算法設(shè)計與分析。第4章 貪心算法（3學(xué)時）4.1貪心算法概念（1學(xué)時）（1）了解貪心算法的概念； （2）理解貪心算法的基本要素最優(yōu)子結(jié)構(gòu)性質(zhì)；貪心選擇性質(zhì)； 重點(diǎn)：理解貪心算法的基本要素：最優(yōu)子結(jié)構(gòu)性質(zhì)；貪心選擇性質(zhì)；難點(diǎn)：理解貪心算法的基本要素：最優(yōu)子結(jié)構(gòu)性質(zhì)；貪心選擇性質(zhì)；4.2貪心算法設(shè)計范例（2學(xué)時）（3）掌握最優(yōu)裝載問題的算法分析；（4）掌握哈夫曼編碼的算法分析；（5）掌握單源最短路徑的Dijkstra算法的設(shè)計與分析；（6）掌握最小生成樹的Prim和Kruskal算法的設(shè)計與分析；重點(diǎn)：掌握最優(yōu)裝載問題的算法分析；掌握單源最短

7、路徑的Dijkstra算法的設(shè)計與分析；難點(diǎn)：掌握單源最短路徑的Dijkstra算法的設(shè)計與分析；第5章 回溯法（2學(xué)時）（1）了解回溯法的思想； （2）理解回溯法的算法框架； （3）掌握裝載問題、批處理作業(yè)調(diào)度問題、符號三角形問題、0-1背包問題、圖的著色問題的算法設(shè)計與分析方法；（4）掌握n后問題、最大團(tuán)問題的回溯法的算法設(shè)計與分析；重點(diǎn)：掌握批處理作業(yè)調(diào)度問題、0-1背包問題、圖的著色問題的算法設(shè)計與分析方法；難點(diǎn)：掌握批處理作業(yè)調(diào)度問題、圖的著色問題的算法設(shè)計與分析方法；第6章 分支限界法（2學(xué)時）（1）了解分支限界法的基本思想； （2）理解單源最短路問題、0-1背包問題的分支限界法分

8、析； （3）掌握旅行售貨員問題的算法設(shè)計與分析；重點(diǎn)：掌握旅行售貨員問題的算法設(shè)計與分析；難點(diǎn)：掌握旅行售貨員問題的算法設(shè)計與分析；第7章 隨機(jī)化算法（1學(xué)時）（1）了解隨機(jī)化算法的特征； （2）理解隨機(jī)化算法的4種分類； （3）掌握產(chǎn)生偽隨機(jī)數(shù)的算法；重點(diǎn)：掌握產(chǎn)生偽隨機(jī)數(shù)的算法；難點(diǎn)：理解隨機(jī)化算法的4種分類；第8章 NP完全問題（2學(xué)時）（1）了解NP完全性問題的概念； （2）了解P類問題和NP類問題； （3）了解NP完全問題；（4）了解一些典型的NP完全問題；（5）典型的NP完全（或NP難度）問題的證明；重點(diǎn)：典型的NP完全（或NP難度）問題的證明；難點(diǎn)：典型的NP完全（或NP難度）問題的證明；四、課程考核（1）作業(yè)等：作業(yè)：5 次；（2）考核方式：課程論文（3）總評成績計算方式：（平時成績*0.3+課程論文成績*0.7=綜合成績）五、參考書目1.陳慧南. HYPERLINK /11055510.html 算法設(shè)計與分析：C+語言描述（第2版）.電子工業(yè)出版社.2012；2.呂國英.算法分析與設(shè)計.清華大學(xué)出版社.2006；3. HYPERLINK /writer/%E7%BD%97%E4%BC%AF%E7%89%B9%60%E5%A1%9E%E5%A5%87%E5%A8%81%E5%85%8B_1.html t _blank 羅伯特.塞奇