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

1、安徽科技學(xué)院理學(xué)院教 學(xué) 大 綱課程名稱：算法設(shè)計適用專業(yè)：計算機科學(xué)與技術(shù)（本科）計算機科學(xué)技術(shù)專業(yè)教研室制2006.6算法設(shè)計理論課教學(xué)大綱 課程名稱：算法設(shè)計（Algrithm Design）課程編號：課程類別：選修課學(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è)計分析的理論與方法.上海

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

4、第一章 算法基礎(chǔ)目的要求1. 了解算法與程序的概念；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.掌握合并排序

5、和快速排序算法；10.了解線性時間選擇算法；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.凸

7、多邊形最優(yōu)三角剖分； 重點難點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.貪心算法的

8、概念、思想；2.貪心算法的基本要素； 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完全