算法設(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ì)（Algrithm Design）課程編號(hào)：課程類別：選修課學(xué) 時(shí)：36 學(xué)時(shí)（理論36學(xué)時(shí)）學(xué) 分：2學(xué)分考核方式：考試適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)本科專業(yè)前修課程：高等數(shù)學(xué) 離散數(shù)學(xué) 線形代數(shù) C語(yǔ)言程序設(shè)計(jì) 數(shù)據(jù)結(jié)構(gòu)建設(shè)開(kāi)課學(xué)期：第6學(xué)期 一、課程性質(zhì)、目的任務(wù)隨著計(jì)算機(jī)的廣泛應(yīng)用，對(duì)計(jì)算機(jī)算法的研究變得日益重要。算法設(shè)計(jì)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門選修課，本課程將覆蓋計(jì)算機(jī)軟件實(shí)現(xiàn)中的大部分算法，并具有一定的深度和廣度，使學(xué)生

2、對(duì)計(jì)算機(jī)常用算法有一個(gè)全盤的了解；本課程的任務(wù)是：培養(yǎng)學(xué)生具有針對(duì)給定問(wèn)題設(shè)計(jì)和實(shí)現(xiàn)高效算法的能力。二、教學(xué)基本要求通過(guò)本課程教學(xué)，應(yīng)使學(xué)生：1）熟悉、掌握課堂教學(xué)中所學(xué)的大部分算法設(shè)計(jì)思想；2）具有針對(duì)所給的問(wèn)題設(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完全性問(wèn)題0四、參考教材及圖書(shū)資料1.王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析.北京:電子工業(yè)出版社2.盧開(kāi)澄.計(jì)算機(jī)算法導(dǎo)引設(shè)計(jì)與分析. 北京:清華大學(xué)出版社3.顧立堯.霍義興.算法設(shè)計(jì)分析的理論與方法.上海

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

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

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

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

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

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

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