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

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

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

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

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

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

6、0/1背包問(wèn)題的算法設(shè)計(jì)與分析；掌握最長(zhǎng)公共子序列問(wèn)題的算法設(shè)計(jì)與分析。第4章 貪心算法（3學(xué)時(shí)）4.1貪心算法概念（1學(xué)時(shí)）（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è)計(jì)范例（2學(xué)時(shí)）（3）掌握最優(yōu)裝載問(wèn)題的算法分析；（4）掌握哈夫曼編碼的算法分析；（5）掌握單源最短路徑的Dijkstra算法的設(shè)計(jì)與分析；（6）掌握最小生成樹(shù)的Prim和Kruskal算法的設(shè)計(jì)與分析；重點(diǎn)：掌握最優(yōu)裝載問(wèn)題的算法分析；掌握單源最短

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

8、析； （3）掌握旅行售貨員問(wèn)題的算法設(shè)計(jì)與分析；重點(diǎn)：掌握旅行售貨員問(wèn)題的算法設(shè)計(jì)與分析；難點(diǎn)：掌握旅行售貨員問(wèn)題的算法設(shè)計(jì)與分析；第7章 隨機(jī)化算法（1學(xué)時(shí)）（1）了解隨機(jī)化算法的特征； （2）理解隨機(jī)化算法的4種分類(lèi)； （3）掌握產(chǎn)生偽隨機(jī)數(shù)的算法；重點(diǎn)：掌握產(chǎn)生偽隨機(jī)數(shù)的算法；難點(diǎn)：理解隨機(jī)化算法的4種分類(lèi)；第8章 NP完全問(wèn)題（2學(xué)時(shí)）（1）了解NP完全性問(wèn)題的概念； （2）了解P類(lèi)問(wèn)題和NP類(lèi)問(wèn)題； （3）了解NP完全問(wèn)題；（4）了解一些典型的NP完全問(wèn)題；（5）典型的NP完全（或NP難度）問(wèn)題的證明；重點(diǎn)：典型的NP完全（或NP難度）問(wèn)題的證明；難點(diǎn)：典型的NP完全（或NP難度）問(wèn)題的證明；四、課程考核（1）作業(yè)等：作業(yè)：5 次；（2）考核方式：課程論文（3）總評(píng)成績(jī)計(jì)算方式：（平時(shí)成績(jī)*0.3+課程論文成績(jī)*0.7=綜合成績(jī)）五、參考書(shū)目1.陳慧南. HYPERLINK /11055510.html 算法設(shè)計(jì)與分析：C+語(yǔ)言描述（第2版）.電子工業(yè)出版社.2012；2.呂國(guó)英.算法分析與設(shè)計(jì).清華大學(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 羅伯特.塞奇