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

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

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

3、現(xiàn)象。學會是指能模仿或在教師指導下獨立地完成某些教學知識和技能的操作任務(wù)，或能識別操作中的一般差錯。教學內(nèi)容和要求表中的“”號表示教學知識和技能的教學要求層次。本標準中打“*”號的內(nèi)容可作為自學，教師可根據(jù)實際情況確定要求或不布置要求。教學內(nèi)容及教學要求表教學內(nèi)容知道理解掌握學會1 算法概述1.1 算法與程序1.2 算法復雜性分析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課時。課時安排及教學方法表教學內(nèi)容課時建議教與學的方法建議理論/實驗（44/10）1 算法概述1.1 算法與程序1.2 算

6、法復雜性分析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. 盧開澄 . 計算機算法導引：設(shè)計與分析北京：清華大學出版社，19963. Bruno R . Preiss 數(shù)據(jù)結(jié)構(gòu)與算法 . 胡廣斌等譯 . 北京：電子工業(yè)出版社，2000六、課程評價1這門學科的評價依據(jù)是本課程標準規(guī)定的課程目標、教學內(nèi)容和要求。2考試時間：120分鐘。3這門學科的評價依據(jù)是本課程標準規(guī)定的課程目標、教學內(nèi)容和要求。考試時間：120分鐘?？荚嚪绞?、分制與分數(shù)解釋：采用開卷、筆試的方式，以百分制評分，60分為及格，滿分為100分。建議題型比例：計算題20%；算法的時間復雜度函數(shù)12%；根據(jù)給定的算法求出問題的解6小題48% 綜合分析題20%。樣題與目標定位示例A. 計算題：（著重考查學生運用數(shù)學知識求解遞歸方程的能力）例：給定一個遞推方程，要求求解后用O、表示。B算法的時間復雜度函數(shù)：（著重考查學生對簡單算法的理解程度）例： 給定一個具體的算法，要求寫出算法的