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

1、算法設(shè)計與分析教學(xué)大綱一、課程概述算法設(shè)計是計算機科學(xué)的一門分支學(xué)科，是軟件技術(shù)的一個重要方向。算法設(shè)計既是軟件設(shè)計的關(guān)鍵，也是培養(yǎng)學(xué)生成為未來軟件工程師所不可或缺的一門專業(yè)知識。算法設(shè)計與分析課程將高級語言程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)和計算方法等內(nèi)容緊密地結(jié)合在一起，全面培養(yǎng)學(xué)生分析問題、解決問題的能力。這門學(xué)科的重點是在培養(yǎng)和培訓(xùn)學(xué)生學(xué)會經(jīng)典算法方面的知識與應(yīng)用，因此它對學(xué)生的專業(yè)發(fā)展具有極其重要的意義。算法設(shè)計與分析的先修課程是高級語言程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)、高等數(shù)據(jù)、組合數(shù)學(xué)。二、課程目標1. 知道算法設(shè)計與分析這門學(xué)科的性質(zhì)、地位和獨立價值。知道這門學(xué)科的研究范圍、分析框架、研究方法、學(xué)科進展和未

2、來方向。2. 理解這門學(xué)科的主要概念，尤其是算法的時間復(fù)雜度和空間復(fù)雜度。3. 初步學(xué)會運用數(shù)學(xué)的方法推導(dǎo)和證明算法的時間復(fù)雜度和空間復(fù)雜度。4. 掌握常用的經(jīng)典算法，培養(yǎng)學(xué)生在軟件設(shè)計時對算法設(shè)計的重視，并能夠把所學(xué)的知識應(yīng)用到具體的軟件設(shè)計實踐中去。三、課程內(nèi)容和要求這門學(xué)科的知識與技能要求分為知道、理解、掌握、學(xué)會四個層次。這四個層次的一般涵義表述如下：知道是指對這門學(xué)科和教學(xué)現(xiàn)象的認知。理解是指對這門學(xué)科涉及到的概念、原理、策略與技術(shù)的說明和解釋，能提示所涉及到的教學(xué)現(xiàn)象演變過程的特征、形成原因以及教學(xué)要素之間的相互關(guān)系。掌握是指運用已理解的教學(xué)概念和原理說明、解釋、類推同類教學(xué)事件和

3、現(xiàn)象。學(xué)會是指能模仿或在教師指導(dǎo)下獨立地完成某些教學(xué)知識和技能的操作任務(wù)，或能識別操作中的一般差錯。教學(xué)內(nèi)容和要求表中的“”號表示教學(xué)知識和技能的教學(xué)要求層次。本標準中打“*”號的內(nèi)容可作為自學(xué)，教師可根據(jù)實際情況確定要求或不布置要求。教學(xué)內(nèi)容及教學(xué)要求表教學(xué)內(nèi)容知道理解掌握學(xué)會1 算法概述1.1 算法與程序1.2 算法復(fù)雜性分析2 遞歸與策略2.1 遞歸的概念2.2 分治法的基本思想2.3 二分搜索技術(shù)2.4 大整數(shù)的乘法2.5 Strassen矩陣乘法2.6 棋盤覆蓋2.7 合并排序2.8 快速排序2.9 線性時間選擇2.10 最接近點對問題2.11 循環(huán)賽日程表3 動態(tài)規(guī)劃3.1 矩陣連

4、乘問題3.2 動態(tài)規(guī)劃算法的基本要素3.3 最長公共子序列3.4 最大子段和3.5 凸多邊形最優(yōu)三角剖分3.6 多邊形游戲3.7 圖像壓縮3.8 電路布線3.9 流水作業(yè)調(diào)度3.10 0-1背包問題3.11 最優(yōu)二叉搜索樹3.12 動態(tài)規(guī)劃加速原理4 貪心算法4.1 活動安排問題4.2 貪心算法的基本要素4.3 最優(yōu)裝載4.4 哈夫曼編碼單源最短路徑最小生成樹多機調(diào)度問題貪心算法的理論基礎(chǔ)5 回溯法5.1 回溯法的算法框架5.2 裝載問題5.3 批處理作業(yè)調(diào)度5.4 符號三角形問題5.5 n后問題5.6 0-1背包問題5.7 最大團問題5.8 圖的m著色問題5.9 旅行售貨員問題5.10 圓排

5、列問題5.11 電路板排列問題5.12 連續(xù)郵資問題5.13 回溯法的效率分析6 分支限界法6.1 分支限界法的基本思想6.2 單源最短路徑問題6.3 裝載問題6.4 布線問題6.5 0-1背包問題6.6 最大團問題6.7 旅行售貨員問題6.8 電路板排列問題6.9 批處理作業(yè)調(diào)度7 線性規(guī)劃與網(wǎng)絡(luò)流7.1 線性規(guī)劃問題和單純形算法7.2 最大網(wǎng)絡(luò)流問題7.3 最小費用問題四、課程實施數(shù)據(jù)庫系統(tǒng)是計算機專業(yè)和通信工程專業(yè)的必修課。一般情況下，計算機專業(yè)為54課時，函授為36課時。課時安排及教學(xué)方法表教學(xué)內(nèi)容課時建議教與學(xué)的方法建議理論/實驗（44/10）1 算法概述1.1 算法與程序1.2 算

6、法復(fù)雜性分析4/0講述2 遞歸與策略2.1 遞歸的概念2.2 分治法的基本思想2.3 二分搜索技術(shù)2.4 大整數(shù)的乘法2.5 Strassen矩陣乘法2.6 棋盤覆蓋2.7 合并排序2.8 快速排序2.9 線性時間選擇2.10 最接近點對問題2.11 循環(huán)賽日程表8/2講述、實驗3 動態(tài)規(guī)劃3.1 矩陣連乘問題3.2 動態(tài)規(guī)劃算法的基本要素3.3 最長公共子序列3.4 最大子段和3.5 凸多邊形最優(yōu)三角剖分3.6 多邊形游戲3.7 圖像壓縮3.8 電路布線3.9 流水作業(yè)調(diào)度3.10 0-1背包問題3.11 最優(yōu)二叉搜索樹3.12 動態(tài)規(guī)劃加速原理6/2講述、實驗4 貪心算法4.1 活動安排問

7、題4.2 貪心算法的基本要素4.3 最優(yōu)裝載4.4 哈夫曼編碼4.5 單源最短路徑4.6 最小生成樹4.7 多機調(diào)度問題4.8 貪心算法的理論基礎(chǔ)6/2講述、實驗5 回溯法5.1 回溯法的算法框架5.2 裝載問題5.3 批處理作業(yè)調(diào)度5.4 符號三角形問題5.5 n后問題5.6 0-1背包問題5.7 最大團問題5.8 圖的m著色問題5.9 旅行售貨員問題5.10 圓排列問題5.11 電路板排列問題5.12 連續(xù)郵資問題5.13 回溯法的效率分析8/2講述、實驗6 分支限界法6.1 分支限界法的基本思想6.2 單源最短路徑問題6.3 裝載問題6.4 布線問題6.5 0-1背包問題6.6 最大團問

8、題6.7 旅行售貨員問題6.8 電路板排列問題6.9 批處理作業(yè)調(diào)度6/2講述、實驗7 線性規(guī)劃與網(wǎng)絡(luò)流7.1 線性規(guī)劃問題和單純形算法7.2 最大網(wǎng)絡(luò)流問題7.3 最小費用問題6/0講述五、教材和參考書目1. 王曉東. 計算機算法設(shè)計與分析（第3版）北京：電子工業(yè)出版社，20072. 盧開澄 . 計算機算法導(dǎo)引：設(shè)計與分析北京：清華大學(xué)出版社，19963. Bruno R . Preiss 數(shù)據(jù)結(jié)構(gòu)與算法 . 胡廣斌等譯 . 北京：電子工業(yè)出版社，2000六、課程評價1這門學(xué)科的評價依據(jù)是本課程標準規(guī)定的課程目標、教學(xué)內(nèi)容和要求。2考試時間：120分鐘。3這門學(xué)科的評價依據(jù)是本課程標準規(guī)定的課程目標、教學(xué)內(nèi)容和要求?？荚嚂r間：120分鐘。考試方式、分制與分數(shù)解釋：采用開卷、筆試的方式，以百分制評分，60分為及格，滿分為100分。建議題型比例：計算題20%；算法的時間復(fù)雜度函數(shù)12%；根據(jù)給定的算法求出問題的解6小題48% 綜合分析題20%。樣題與目標定位示例A. 計算題：（著重考查學(xué)生運用數(shù)學(xué)知識求解遞歸方程的能力）例：給定一個遞推方程，要求求解后用O、表示。B算法的時間復(fù)雜度函數(shù)：（著重考查學(xué)生對簡單算法的理解程度）例： 給定一個具體的算法，要求寫出算法的