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

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

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

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

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

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

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

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

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

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