算法分析與設計課程教學大綱

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

2、thms is a compulsory specialty course for software developer. Efficiency and stability of software depends on algorithms used in it. For common coders and software relative students, learning this course could expand their programming vision and help them programming high quality codes.三、課程性質與教學目的通過

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

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

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

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

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

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

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

10、 線性規(guī)劃和網絡流（自學）（一） 目的與要求1. 了解線性規(guī)劃模型的特點、線性規(guī)劃問題的標準型及退化處理；2. 掌握線性規(guī)劃問題解的概念、有關解的基本定理；3. 掌握單純形法的的原理和求解方法；4. 掌握實踐中常見問題的建模方法；5. 掌握最大網絡流問題的求解方法和最小費用流問題的求解方法。 （二） 教學內容1 主要內容線性規(guī)劃的基本概念、定理及單純形算法，最大網絡流和最小費用流問題的解法。2 基本概念和知識點線性規(guī)劃概念、定理及單純形算法，最大網絡流和最小費用流問題的解法。3. 應用（能力要求）掌握線性規(guī)劃問題解的概念、有關解的基本定理；掌握單純形法的的原理和求解方法；掌握實踐中常見問題的建

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

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