算法設(shè)計(jì)教學(xué)大綱詳解

1、安徽科技學(xué)院理學(xué)院教學(xué)大綱課程名稱：算法設(shè)計(jì)適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)（本科）計(jì)算機(jī)科學(xué)技術(shù)專業(yè)教研室制2006.6算法設(shè)計(jì)理論課教學(xué)大綱課程名稱：算法設(shè)計(jì)（AlgrithmDesign）課程編號：課程類別：選修課學(xué)時(shí)：36學(xué)時(shí)（理論36學(xué)時(shí)）學(xué)分：2學(xué)分考核方式：考試適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)本科專業(yè)前修課程：高等數(shù)學(xué)離散數(shù)學(xué)線形代數(shù)C語言程序設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)建設(shè)開課學(xué)期：第6學(xué)期一、課程性質(zhì)、目的任務(wù)隨著計(jì)算機(jī)的廣泛應(yīng)用，對計(jì)算機(jī)算法的研究變得日益重要。算法設(shè)計(jì)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門選修課，本課程將覆蓋計(jì)算機(jī)軟件實(shí)現(xiàn)中的大部分算法，并具有一定的深度和廣度，使學(xué)生對計(jì)算機(jī)常用算法有一個(gè)全盤

2、的了解；本課程的任務(wù)是：培養(yǎng)學(xué)生具有針對給定問題設(shè)計(jì)和實(shí)現(xiàn)高效算法的能力。二、教學(xué)基本要求通過本課程教學(xué)，應(yīng)使學(xué)生：1）熟悉、掌握課堂教學(xué)中所學(xué)的大部分算法設(shè)計(jì)思想2）具有針對所給的問題設(shè)計(jì)和實(shí)現(xiàn)高效算法的能力。三、教學(xué)內(nèi)容與學(xué)時(shí)分配教學(xué)內(nèi)容學(xué)時(shí)第一章算法基礎(chǔ)3第二章遞歸與分治策略10第三章動(dòng)態(tài)規(guī)劃8第四章貪心法7第五章回溯法4第六章分支限界法4第七章NP完全性問題0四、參考教材及圖書資料1. 王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析.北京:電子工業(yè)出版社2. 盧開澄.計(jì)算機(jī)算法導(dǎo)引設(shè)計(jì)與分析.北京:清華大學(xué)出版社3. 顧立堯.霍義興.算法設(shè)計(jì)分析的理論與方法.上海:上海交通大學(xué)出版社4. 霍紅衛(wèi).分布式

3、算法導(dǎo)論.北京:機(jī)械工業(yè)出版社五、教學(xué)方法與考核1. 教學(xué)方法為充分發(fā)揮學(xué)生的積極性、主動(dòng)性，啟發(fā)引導(dǎo)、培養(yǎng)學(xué)生具有自我開拓和獲得知識的能力，在內(nèi)容的講授上本著“少而精”的原則，突出重點(diǎn)，分解難點(diǎn)，深入淺出，舉一反三，著重培養(yǎng)學(xué)生分析問題和解決問題能力。并就課程的各部分內(nèi)容，分別采用細(xì)講法，培養(yǎng)學(xué)生的基本功；采用精講法，培養(yǎng)學(xué)生主動(dòng)獲取知識的能力；采用引導(dǎo)啟發(fā)式，培養(yǎng)學(xué)生分析問題、解決問題的能力。另不同程度采取課堂討論式、自學(xué)提問式。2課程考核方法主要有：理論課考查、作業(yè)評定。平時(shí)占20%:理論課考查、作業(yè)評定；期末考試占80%：綜合筆試。六、大綱正文第一章算法基礎(chǔ)目的要求1. 了解算法與程序

4、的概念；2. 掌握算法復(fù)雜性分析及其有關(guān)的概念；基本內(nèi)容1. 算法的定義、特征,算法與程序；2. 冒泡排序；3. 偽代碼使用約定；4. 算法復(fù)雜度分析；5. 算法的運(yùn)行時(shí)間；重點(diǎn)難點(diǎn)1重點(diǎn)：算法的定義與特征、冒泡排序、算法復(fù)雜度分析2. 難點(diǎn)：算法復(fù)雜度分析課時(shí)安排建議：3學(xué)時(shí)。第二章遞歸與分治策略目的要求1. 理解遞歸的概念；2. 掌握遞歸方程構(gòu)建的思想；3. 掌握遞歸方程的求解方法；4. 了解分治法的基本思想；5. 掌握二叉查找算法；6. 掌握用分治法求最大值與最小值的算法；7. 掌握Strassen矩陣算法；8. 理解整數(shù)相乘算法；9. 掌握合并排序和快速排序算法；10. 了解線性時(shí)間選

5、擇算法；11. 了解最近點(diǎn)對問題算法基本內(nèi)容1. 遞歸的概念；2. 遞歸方程構(gòu)建的思想；3. 遞歸方程的求解方法（遞歸樹與主方法）；4. 分治法的基本思想；5. 二叉查找算法；6. 用分治法求最大值與最小值的算法；7.Strassen矩陣算法；8. 整數(shù)相乘算法；9. 合并排序和快速排序算法；10. 線性時(shí)間選擇算法；11. 最近點(diǎn)對問題算法重點(diǎn)難點(diǎn)1重點(diǎn)：遞歸方程的求解方法（遞歸樹與主方法）、二叉查找算法、Strassen矩陣算法、合并排序和快速排序算法2. 難點(diǎn)：遞歸方程構(gòu)建、遞歸方程的求解方法（遞歸樹與主方法）Strassen矩陣算法、合并排序和快速排序算法、線性時(shí)間選擇算法、最近點(diǎn)對問

6、題算法課時(shí)安排建議：10學(xué)時(shí)。第三章動(dòng)態(tài)規(guī)劃目的要求1. 掌握動(dòng)態(tài)規(guī)劃算法的概念和步驟；2. 掌握0-1背包問題的算法設(shè)計(jì)和分析；3. 掌握矩陣鏈乘算法設(shè)計(jì)和分析；4. 掌握動(dòng)態(tài)規(guī)劃算法的基本要素；5. 理解備忘錄方法；6. 了解裝配線調(diào)度問題算法設(shè)計(jì)和分析；7. 理解最長公共子序列問題算法設(shè)計(jì)和分析；8. 掌握最優(yōu)二分檢索樹算法設(shè)計(jì)和分析。9. 了解凸多邊形最優(yōu)三角剖分算法；基本內(nèi)容1. 動(dòng)態(tài)規(guī)劃算法的概念和步驟；2.0-1背包問題；3. 矩陣鏈乘；4. 動(dòng)態(tài)規(guī)劃算法的基本要素；5. 備忘錄方法；6. 裝配線調(diào)度問題；7. 最長公共子序列問題；8. 最優(yōu)二分檢索樹。9. 凸多邊形最優(yōu)三角剖分

7、；重點(diǎn)難點(diǎn)1重點(diǎn)：動(dòng)態(tài)規(guī)劃算法的概念和步驟、0-1背包問題、矩陣鏈乘、動(dòng)態(tài)規(guī)劃算法的基本要素、最優(yōu)二分檢索樹2. 難點(diǎn)：0-1背包問題、矩陣鏈乘課時(shí)安排建議：8學(xué)時(shí)。第四章貪心法目的要求1. 掌握貪心算法的概念、思想；2. 掌握貪心算法的基本要素；3. 掌握背包問題的算法設(shè)計(jì)和分析；4. 理解活動(dòng)選擇問題算法設(shè)計(jì)和分析；5. 理解哈夫曼編碼的算法分析；6. 掌握最小生成樹的Prim和Kruskal算法的設(shè)計(jì)與分析；7. 了解最小生成樹的Boruvka算法的設(shè)計(jì)與分析；8. 掌握單源最短路徑的Dijkstra算法的設(shè)計(jì)與分析；9. 理解貪心算法的理論基礎(chǔ)；基本內(nèi)容1. 貪心算法的概念、思想；2.

8、 貪心算法的基本要素；3. 背包問題的算法設(shè)計(jì)和分析；4. 活動(dòng)選擇問題算法設(shè)計(jì)和分析；5. 哈夫曼編碼的算法分析；6. 最小生成樹的Prim、Kruskal算法和Boruvka算法；7. 單源最短路徑的Dijkstra算法；8. 貪心算法的理論基礎(chǔ)；重點(diǎn)難點(diǎn)1重點(diǎn)：貪心算法的概念、思想、貪心算法的基本要素、背包問題、最小生成樹的Prim和Kruskal算法、單源最短路徑的Dijkstra算法、貪心算法的理論基礎(chǔ)2. 難點(diǎn)：貪心算法的思想、背包問題、單源最短路徑的Dijkstra算法、貪心算法的理論基礎(chǔ)課時(shí)安排建議：7學(xué)時(shí)。第五章回溯法目的要求1. 掌握回溯法的概念、思想；2. 掌握子集樹、排

9、列樹、搜索樹的構(gòu)造；3. 理解N皇后問題的算法設(shè)計(jì)和分析；4. 理解子集和數(shù)問題算法設(shè)計(jì)和分析；5. 理解0-1背包問題算法設(shè)計(jì)和分析；6. 了解著色問題算法的設(shè)計(jì)與分析；基本內(nèi)容1. 回溯法的概念、思想；2. 子集樹、排列樹、搜索樹的構(gòu)造；3. N皇后問題；4. 子集和數(shù)問題；5.0-1背包問題；6. 著色問題；重點(diǎn)難點(diǎn)1重點(diǎn)：回溯法的思想、子集樹的構(gòu)造、排列樹的構(gòu)造、搜索樹的構(gòu)造、N皇后問題、子集和數(shù)問題、背包問題2.難點(diǎn)：回溯法的思想、N皇后問題、子集和數(shù)問題、背包問題課時(shí)安排建議：4學(xué)時(shí)。第六章分枝限界法目的要求1. 掌握分枝限界法的概念、思想；2. 理解0-1背包問題算法設(shè)計(jì)和分析；3. 理解作業(yè)調(diào)度問題的算法設(shè)計(jì)和分析；基本內(nèi)容1. 分枝限界法的概念、思想（先進(jìn)先出狀態(tài)空間樹、優(yōu)先隊(duì)列狀態(tài)空間樹）；2.0-1背包問題算法設(shè)計(jì)和分析；3. 作業(yè)調(diào)度問題的算法設(shè)計(jì)和分析；重點(diǎn)難點(diǎn)1重點(diǎn)：分枝限界法的思想、0-1背包問題算法設(shè)計(jì)和分析2. 難點(diǎn)：分枝限界法的思想、0-1背包問題算法設(shè)計(jì)和分析課時(shí)安排建議：4學(xué)時(shí)。第七章NP完全性問題目的要求1. 了解NP完全性問題的概念；2. 了解P類問題和NP類問題；3. 了解NP完全問題；4. 了解一些典型的NP