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

1、算法分析與設(shè)計課程教學(xué)大綱、課程基本信息課程代碼： 110426課程名稱：算法分析與設(shè)計英文名稱： Analysis and Design of Algorithms 課程類別：專業(yè)基礎(chǔ)課學(xué) 時： 45學(xué) 分： 2適用對象 : 信息與計算科學(xué)專業(yè)本科生 考核方式：考試（平時成績占總成績的 30） 先修課程：數(shù)學(xué)分析、高級語言程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)二、課程簡介中文簡介算法分析與設(shè)計 是軟件開發(fā)人員必修專業(yè)課， 軟件的效率和穩(wěn)定性取決 于軟件中所采用的算法； 對于一般程序員和軟件類專業(yè)學(xué)生， 學(xué)習(xí)算法設(shè)計與分 析課程，可以開闊編程思路，編寫出優(yōu)質(zhì)程序。英文簡介Analysis and Design o

2、f Algorithms is a compulsory specialty course for software developer. Efficiency and stability of software depends on algorithms used in it. For commoncoders and software relative students, learning this course could expand their programming vision and help them programming high quality codes.三、課程性質(zhì)

3、與教學(xué)目的通過對常用的、 有代表性的算法的研究， 讓學(xué)生理解并掌握算法設(shè)計的基本 技術(shù)。培養(yǎng)學(xué)生分析算法復(fù)雜度的初步能力， 鍛煉其邏輯思維能力和想象力， 并 使之了解算法理論的發(fā)展。 鼓勵學(xué)生運用算法知識解決各自學(xué)科的實際問題， 培養(yǎng)學(xué)生的獨立科研的能力和理論聯(lián)系實踐的能力。四、教學(xué)內(nèi)容及要求第一章 算法概述 （ 一 ） 目的與要求 掌握算法，算法復(fù)雜度的基本概念，及時間復(fù)雜度的估算方法。 （ 二 ） 教學(xué)內(nèi)容1. 主要內(nèi)容算法，算法復(fù)雜度的基本概念，及時間復(fù)雜度2. 基本概念和知識點 算法，算法復(fù)雜度的基本概念，及時間復(fù)雜度。3. 問題與應(yīng)用（能力要求） 掌握算法，算法復(fù)雜度的基本概念，及時

4、間復(fù)雜度的估算方法。（ 三 ） 課后練習(xí) 函數(shù)的漸進表達式。（ 四 ） 教學(xué)方法與手段 課堂講授為主，結(jié)合課堂分組討論。第二章 遞歸與分治法一）目的與要求1. 掌握遞歸的概念，學(xué)會用遞歸方法解決實際問題；2. 熟練掌握利用分治法解決問題的基本思想， 會用某高級語言對算 法進行描述，并對算法復(fù)雜度（時間和空間）進行分析。二）教學(xué)內(nèi)容1主要內(nèi)容 遞歸概念，分治法基本思想，二分搜索技術(shù)，大整數(shù)乘法，矩陣 乘法，棋盤覆蓋，合并排序，快速排序，線性時間選擇，最接近 點對問題，循環(huán)賽日程表。2基本概念和知識點 遞歸概念，分治法，二分搜索，大整數(shù)乘法，矩陣乘法，棋盤覆 蓋，合并排序，快速排序。3問題與應(yīng)用（

5、能力要求） 掌握遞歸的概念，學(xué)會用遞歸方法解決實際問題，熟練掌握利用 分治法解決問題的基本思想，會用某高級語言對算法進行描述， 并對算法復(fù)雜度（時間和空間）進行分析。三）課后練習(xí)Hanoi 塔問題的非遞歸算法。四）教學(xué)方法與手段課堂講授為主，結(jié)合課堂分組討論。第三章 動態(tài)規(guī)劃一）目的與要求 1熟練掌握利用動態(tài)規(guī)劃方法解決問題的基本思想； 2學(xué)會如何將問題化為多階段圖的方法； 3能對具體問題寫出正確的遞推公式。二）教學(xué)內(nèi)容1主要內(nèi)容 動態(tài)規(guī)劃的基本要素， 矩陣連乘， 最長公共子序列， 最大子段和， 凸多邊形最優(yōu)三角剖分，多邊形游戲，圖像壓縮，電路布線，流 水作業(yè)調(diào)度， 0-1 背包問題，最優(yōu)二叉

6、搜索樹。2基本概念和知識點 動態(tài)規(guī)劃的基本要素，最長公共子序列，最大子段和，凸多邊形 最優(yōu)三角剖分 ,0-1 背包問題，最優(yōu)二叉搜索樹。3問題與應(yīng)用（能力要求） 熟練掌握利用動態(tài)規(guī)劃方法解決問題的基本思想。三）課后練習(xí)最長單調(diào)遞增子序列。四）教學(xué)方法與手段課堂講授為主，結(jié)合分組課堂討論。第四章 貪心算法一）目的與要求1掌握利用貪心算法解決問題的基本思想； 2會用某高級語言編寫用貪心算法解決問題的程序， 并能對算法的 復(fù)雜度，可靠性進行分析。二）教學(xué)內(nèi)容1主要內(nèi)容 貪心算法的基本要素，活動安排問題，最優(yōu)裝載，哈夫曼編碼， 單源最短路徑，最小生成樹，多機調(diào)度。2基本概念和知識點 貪心算法，哈夫曼編

7、碼，單源最短路徑，最小生成樹。3問題與應(yīng)用（能力要求） 掌握利用貪心算法解決問題的基本思想。三）實踐環(huán)節(jié)與課后練習(xí)活動安排問題的貪心選擇算法。四）教學(xué)方法與手段課堂講授為主，結(jié)合課堂分組討論。第五章 回溯法一）目的與要求1掌握利用回溯法解決問題的基本思想；2會用回溯法解決：n個皇后問題，圖的m著色問題，批處理作業(yè) 調(diào)度問題等，并能準確地分析回溯法的效率及穩(wěn)定性。二）教學(xué)內(nèi)容1. 主要內(nèi)容回溯法的算法框架、符號，三角形問題， n 個皇后問題，最大團 問題，圖的m著色問題，旅行售貨員問題，圓排列問題，連續(xù)郵 資問題，電路板排列問題。2. 基本概念和知識點回溯法，三角形問題，n個皇后問題，最大團問題

8、，圖的 m著色 問題，旅行售貨員問題。3. 問題與應(yīng)用（能力要求） 掌握利用回溯法解決問題的基本思想。三）課后練習(xí)裝載問題的改進回溯法。四）教學(xué)方法與手段課堂講授為主，結(jié)合課堂分組討論。第六章 分支限界法一）目的與要求1. 掌握利用分支限界法解決問題的基本思想；2. 能用多種不同方法解法同一問題，并分析各方法的效率。二）教學(xué)內(nèi)容1主要內(nèi)容 分支限界的基本思想， 單源最短路徑， 布線問題， 01 背包問題， 批處理作業(yè)調(diào)度問題。2基本概念和知識點 分支限界，單源最短路徑，布線問題， 01 背包問題，批處理作 業(yè)調(diào)度問題。3. 問題與應(yīng)用（能力要求） 掌握分支限界法解決問題的基本思想， 能用多種不

9、同方法解法同 一問題，并分析各方法的效率。三）實踐環(huán)節(jié)0-1 背包問題的棧式分支限界法。四）教學(xué)方法與手段課堂講授為主，結(jié)合課堂分組討論。第七章 概率算法（選學(xué)）一）目的與要求1. 掌握利用概率算法的基本思想；2. 會用概率算法解決有關(guān)問題。二）教學(xué)內(nèi)容1主要內(nèi)容 概率算法的基本思想，隨機數(shù)，數(shù)值概率算法，舍伍德算法，拉 斯維加斯算法，蒙特卡羅算法。2基本概念和知識點 概率算法，隨機數(shù)，數(shù)值概率算法，舍伍德算法，拉斯維加斯算 法，蒙特卡羅算法。3. 問題與應(yīng)用（能力要求）掌握利用概率算法的基本思想 , 會用概率算法解決有關(guān)問題。三）實踐環(huán)節(jié)與課后練習(xí)模擬正態(tài)分布隨機變量。四）教學(xué)方法與手段 課

10、堂講授為主，結(jié)合課堂分組討論。第八章 線性規(guī)劃和網(wǎng)絡(luò)流（自學(xué)）一）目的與要求1. 了解線性規(guī)劃模型的特點、線性規(guī)劃問題的標準型及退化處理；2. 掌握線性規(guī)劃問題解的概念、有關(guān)解的基本定理；3. 掌握單純形法的的原理和求解方法；4. 掌握實踐中常見問題的建模方法；5. 掌握最大網(wǎng)絡(luò)流問題的求解方法和最小費用流問題的求解方法。二）教學(xué)內(nèi)容1主要內(nèi)容線性規(guī)劃的基本概念、定理及單純形算法，最大網(wǎng)絡(luò)流和最小費 用流問題的解法。2基本概念和知識點 線性規(guī)劃概念、定理及單純形算法，最大網(wǎng)絡(luò)流和最小費用流問 題的解法。3. 應(yīng)用（能力要求） 掌握線性規(guī)劃問題解的概念、有關(guān)解的基本定理；掌握單純形法 的的原理和

11、求解方法；掌握實踐中常見問題的建模方法。掌握最 大網(wǎng)絡(luò)流問題的求解方法和最小費用流問題的求解方法。三）實踐環(huán)節(jié)與課后練習(xí)單源最短路徑與線性規(guī)劃。四）教學(xué)方法與手段 課堂講授為主，結(jié)合課堂分組討論。第九章 NP 完全性理論與近似算法（選學(xué)）一）目的與要求1了解NP完全性問題；2掌握P類與NP類問題的劃分；3掌握利用近似算法解決問題的基本思想，能對其可靠性進行分 析。二）教學(xué)內(nèi)容1 主要內(nèi)容計算模型，P類與NP類問題，NP完全問題，合取范式（CNF頂點覆蓋問題，哈密頓回路問題；近似算法的基本思想及性能，頂點覆蓋問題的近似算法，集合覆蓋問題的近似算法，子集合問題 的近似算法。2. 基本概念和知識點計

12、算模型，P類與NP類問題，NP完全問題，合取范式（CNF頂 點覆蓋問題，哈密頓回路問題。3. 問題與應(yīng)用（能力要求了解NP完全性問題，掌握P類與NP類問題的劃分。掌握利用近 似算法解決問題的基本思想，能對其可靠性進行分析。（三）實踐環(huán)節(jié)與課后練習(xí)RAM和 RASP程序。（四）教學(xué)方法與手段課堂講授為主，結(jié)合課堂分組討論。五、各教學(xué)環(huán)節(jié)學(xué)時分配、教學(xué)環(huán)節(jié)教學(xué)時數(shù)課程內(nèi)容講課習(xí) 題 課討論課實驗其他教學(xué)環(huán)節(jié)小計氏代 第一早算法概述300003第二早遞歸與分治法600006第三章動態(tài)規(guī)劃600309第四章貪心算法600006第五早回溯法600309第六章分支限法600006第七章概率算法300003第八章線性規(guī)劃和網(wǎng)絡(luò)流000000第九章算法NP完全性理論與近似300003課程設(shè) 計一周合計39006045六、推薦教材和教學(xué)參考資源推薦教材：2004。第二卷王曉東