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

算法設(shè)計與分析課程教學(xué)大綱【課程編碼】 JSZX0490【適用專業(yè)】 計算機(jī)科學(xué)與技術(shù)【課 時】理論課時：54，實(shí)驗(yàn)課時：16【學(xué) 分】3【課程性質(zhì)、目標(biāo)和要求】《算法設(shè)計與分析》 是計算機(jī)科學(xué)與技術(shù)專業(yè)的專業(yè)課。 無論是計算科學(xué)還是計算實(shí)踐， 算法都在其中扮演著重要角色。 本課程的教學(xué)目的是講授在計算機(jī)應(yīng)用中常常遇到的實(shí)際問題的解法，講授設(shè)計和分析各種算法的基本原理、 方法和技術(shù)，培養(yǎng)學(xué)生對算法復(fù)雜性進(jìn)行正確分析的能力。課程基本要求是⑴掌握算法分析的基本概念和理論。⑵掌握算法設(shè)計技術(shù)和分析算法以及算法復(fù)雜性。【教學(xué)時間安排】本課程計3 學(xué)分，理論課時 54+實(shí)驗(yàn)課時 16, 學(xué)時分配如下：序號課程內(nèi)容/實(shí)驗(yàn)名稱實(shí)驗(yàn)類型課時備注1算法引論理論課時42遞歸與分治策略/分治法實(shí)驗(yàn)設(shè)計理論課時6+實(shí)驗(yàn)課時83動態(tài)規(guī)劃/動態(tài)規(guī)劃實(shí)驗(yàn)設(shè)計理論課時8+實(shí)驗(yàn)課時84貪心算法理論課時65回溯法理論課時66分支限界法理論課時67概率算法理論課時68NP完全性理論理論課時49 近似算法 理論課時 410算法優(yōu)化策略理論課時4合計理論課時54+實(shí)驗(yàn)課時16【教學(xué)內(nèi)容要點(diǎn)】第一章 算法引論一、學(xué)習(xí)目的要求1．了解算法的計算復(fù)雜性分析方法2．理解算法分析的基本理論3．掌握算法分析的基本概念二、主要教學(xué)內(nèi)容1.算法的基本概念2.表達(dá)算法的抽象機(jī)制3.采用Java語言與自然語言相結(jié)合的方式描述算法的方法.算法的計算復(fù)雜性分析方法第二章 遞歸與分治策略一、學(xué)習(xí)目的要求1．理解典型范例中遞歸與分治策略應(yīng)用技巧2．掌握遞歸與分治策略3．掌握數(shù)學(xué)歸納法證明算法正確性方法二、主要教學(xué)內(nèi)容1.遞歸的概念2.分治法的基本思想3.二分搜索技術(shù).大整數(shù)的乘法.Strassen陣乘法.棋盤覆蓋.合并排序8.快速排序9.線性時間選擇10.最接近點(diǎn)對問題11.循環(huán)賽日程表第三章 動態(tài)規(guī)劃一、學(xué)習(xí)目的要求1．理解典型范例中動態(tài)規(guī)劃算法的設(shè)計思想2．掌握動態(tài)規(guī)劃算法的基本要求以及算法的設(shè)計要點(diǎn)二、主要教學(xué)內(nèi)容1.矩陣連乘問題2.動態(tài)規(guī)劃算法的基本要素3.最長公共子序列.最大子段和.凸多邊形最優(yōu)三角剖分.多邊形游戲7.圖像壓縮8.電路布線9.流水作業(yè)調(diào)度10. 0—l背包問題11.最優(yōu)二叉搜索樹12.動態(tài)規(guī)劃加速原理三、課堂討論選題1.最長公共子序列2. 0—l背包問題第四章 貪心算法一、學(xué)習(xí)目的要求1．了解貪心算法的理論基礎(chǔ)及基本要素理解典型范例中貪心算法的設(shè)計思想掌握貪心算法的設(shè)計要點(diǎn)二、主要教學(xué)內(nèi)容1.活動安排問題2.貪心算法的基本要素3.最優(yōu)裝載.哈夫曼編碼.單源最短路徑.最小生成樹.多機(jī)調(diào)度問題.貪心算法的理論基礎(chǔ)三、課堂討論選題1.最優(yōu)裝載2.單源最短路徑第五章 回溯法一、學(xué)習(xí)目的要求1．理解回溯法的效率分析方法2．掌握回溯法的算法框架和應(yīng)用技巧二、主要教學(xué)內(nèi)容1.回溯法的算法框架2.裝載問題3.批處理作業(yè)調(diào)度.符號三角形問題.n后問題.0—l背包問題.最大團(tuán)問題8.圖的m著色問題9.旅行售貨員問題10.圓排列問題11.電路板排列問題12.連續(xù)郵資問題13.回溯法的效率分三、課堂討論選題1. 0—l背包問題2.圖的m著色問題第六章 分支限界法一、學(xué)習(xí)目的要求1．理解分支限界法的基本思想2．掌握典型范例中分支限界法的應(yīng)用技巧二、主要教學(xué)內(nèi)容1.分支限界法的基本思想2.單源最短路徑問題3.裝載問題.布線問題.0-1背包問題.最大團(tuán)問題.旅行售貨員問題.電路板排列問題9.批處理作業(yè)調(diào)度三、課堂討論選題1. 0-1背包問題2.批處理作業(yè)調(diào)度第七章 概率算法一、學(xué)習(xí)目的要求1．理解概率算法的基本思想2．掌握典型范例中概率算法的應(yīng)用技巧二、主要教學(xué)內(nèi)容1.隨機(jī)數(shù)2.數(shù)值概率算法3.舍伍德算法.拉斯維加斯算法.蒙特卡羅算法第八章 NP完全性理論一、學(xué)習(xí)目的要求1．了解P類與NP類問題2．了解典型的 NP完全問題二、主要教學(xué)內(nèi)容1.計算模型2. P類與NP類問題3. NP完全問題.一些典型的NP完全問題第九章 近似算法一、學(xué)習(xí)目的要求1．掌握近似算法的基本思想2．掌握常用近似算法的應(yīng)用二、主要教學(xué)內(nèi)容1.近似算法的性能2.頂點(diǎn)覆蓋問題的近似算法3.旅行售貨員問題近似算法.集合覆蓋問題的近似算法.子集和問題的近似算法第十章 算法優(yōu)化策略一、學(xué)習(xí)目的要求1．掌握算法優(yōu)化策略2．掌握算法優(yōu)化的基本方法二、主要教學(xué)內(nèi)容1.算法優(yōu)化策略的比較與選擇2.動態(tài)規(guī)劃加速原理3.問題的算法特征.優(yōu)化數(shù)據(jù)結(jié)構(gòu).優(yōu)化搜索策略【教學(xué)（實(shí)驗(yàn)）內(nèi)容要點(diǎn)】算法設(shè)計與分析實(shí)驗(yàn)是算法設(shè)計與分析課的一個實(shí)踐性教學(xué)環(huán)節(jié)。 通過實(shí)驗(yàn)使學(xué)生加深對基本算法設(shè)計方法的理解， 增強(qiáng)學(xué)生對解決問題的不同算法運(yùn)行時間不同的感性認(rèn)識， 使學(xué)生在算法設(shè)計方法和編程技能等方面得到系統(tǒng)的訓(xùn)練， 使學(xué)生養(yǎng)成設(shè)計良好算法的習(xí)慣， 為今后從事軟件開發(fā)和軟件理論研究打下良好的實(shí)驗(yàn)基礎(chǔ)。一、（實(shí)驗(yàn)1）分治法實(shí)驗(yàn)1.實(shí)驗(yàn)?zāi)康囊髴?yīng)用分治法算法解決實(shí)際問題 ，并編程實(shí)現(xiàn)。2.實(shí)驗(yàn)主要內(nèi)容寫出并調(diào)試二分檢索的遞歸程序并調(diào)試通過。寫出并調(diào)試"由底向上"的歸并分類程序，從而取消對?？臻g的需求。、實(shí)驗(yàn)儀器設(shè)備PC兼容機(jī)二、（實(shí)驗(yàn)2）動態(tài)規(guī)劃實(shí)驗(yàn)1.實(shí)驗(yàn)?zāi)康囊蟀褎討B(tài)規(guī)劃算法應(yīng)用到 求貨郎擔(dān)問題和矩陣乘法問題，并編程實(shí)現(xiàn)。2.實(shí)驗(yàn)主要內(nèi)容1）寫出并調(diào)試用動態(tài)規(guī)劃方法求貨郎擔(dān)問題的程序。2）寫出并調(diào)試用動態(tài)規(guī)劃方法求矩陣乘法的程序。3.實(shí)驗(yàn)儀器設(shè)備PC兼容機(jī)。【成績考核方式】1.成績評定總則全面考核學(xué)生在課程學(xué)習(xí)各個環(huán)節(jié)的理解、掌握和參與情況2.平時成績評定平時成績＝考勤成績＋作業(yè)成績 +課堂討論成績3.期末考核評定課程成績＝平時成績 (10%)+實(shí)驗(yàn)成績(20%)+期末成績(70%)【教材與參考書目】指定教材：《算法設(shè)計與分析》王曉東編著

2003年1月第

1版

清華大學(xué)出版社參考書目：1.《算法設(shè)計與分析》周培德編著

1991

年

1月第

1版

機(jī)械工業(yè)出版社2.《算法設(shè)計與分析》曹新譜編著

1984

年

11月第

1版湖南科技出版社3.