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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上算法分析與設(shè)計(jì)課程教學(xué)大綱一、課程基本信息課程代碼：課程名稱(chēng)：算法分析與設(shè)計(jì)英文名稱(chēng)：Analysis and Design of Algorithms課程類(lèi)別：專(zhuān)業(yè)基礎(chǔ)課學(xué) 時(shí)：45學(xué)分：2適用對(duì)象: 信息與計(jì)算科學(xué)專(zhuān)業(yè)本科生考核方式：考試（平時(shí)成績(jī)占總成績(jī)的30）先修課程：數(shù)學(xué)分析、高級(jí)語(yǔ)言程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)二、課程簡(jiǎn)介中文簡(jiǎn)介算法分析與設(shè)計(jì)是軟件開(kāi)發(fā)人員必修專(zhuān)業(yè)課，軟件的效率和穩(wěn)定性取決于軟件中所采用的算法；對(duì)于一般程序員和軟件類(lèi)專(zhuān)業(yè)學(xué)生，學(xué)習(xí)算法設(shè)計(jì)與分析課程，可以開(kāi)闊編程思路，編寫(xiě)出優(yōu)質(zhì)程序。英文簡(jiǎn)介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.三、課程性質(zhì)與教學(xué)目的通過(guò)

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

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

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

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

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

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

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

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

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

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