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

課程編號：“算法設(shè)計(jì)與分析”課程教學(xué)大綱Algorithm Design and Analysis Course Outline50學(xué)時(shí) 2.5學(xué)分一、本課程的性質(zhì)、目的、任務(wù)算法設(shè)計(jì)與分析是計(jì)算機(jī)科學(xué)的重要基礎(chǔ),介紹常用設(shè)計(jì)算法的策略:分治,貪心,規(guī)劃,回溯等,通過本課程的學(xué)習(xí)使學(xué)生掌握基本算法的分析,設(shè)計(jì)技能和方法。通過算法設(shè)計(jì)與分析的學(xué)習(xí)和研究，能掌握算法設(shè)計(jì)的主要方法，培養(yǎng)對算法的計(jì)算復(fù)雜性正確分析的能力，為獨(dú)立設(shè)計(jì)算法和對算法進(jìn)行復(fù)雜性分析奠定堅(jiān)實(shí)的基礎(chǔ)。本課程使學(xué)生能夠切實(shí)掌握算法設(shè)計(jì)與分析的基本知識,掌握常用算法的設(shè)計(jì)策略，包括：遞歸與分治法，動(dòng)態(tài)規(guī)劃，貪心算法與回溯法。掌握計(jì)算機(jī)領(lǐng)域中常用的非數(shù)值計(jì)算算法，并學(xué)會(huì)用這些算法解決實(shí)際問題。二、適用專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)三、先修課程C+面向程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)四、課程的基本要求通過本課程的學(xué)習(xí)，學(xué)生應(yīng)能達(dá)到下列要求：1理解算法的定義及特性，了解算法與程序的區(qū)別，熟悉算法復(fù)雜性的分析。2 理解遞歸的概念，掌握遞歸方程求解方法，掌握分治算法的設(shè)計(jì)策略。3 了解動(dòng)態(tài)規(guī)劃算法的基本要素，了解態(tài)規(guī)劃算法的設(shè)計(jì)方法。4理解貪心算法的基本性質(zhì)，掌握貪心算法的設(shè)計(jì)原則。5 熟悉問題的解空間、解空間樹的概念，用問題的約束條件對解空間樹進(jìn)行修剪、遞歸回溯；掌握回溯算法的設(shè)計(jì)方法。6了解分支限界法的基本思想。五、課程的教學(xué)內(nèi)容（一）課堂講授的教學(xué)內(nèi)容：1算法概述算法與程序，算法復(fù)雜性的分析。2 遞歸與分治策略遞歸的概念，遞歸方程求解方法，二分搜索技術(shù)，大數(shù)的乘法，Strassen矩陣相乘，棋盤覆蓋算法3 動(dòng)態(tài)規(guī)劃矩陣連乘問題，動(dòng)態(tài)規(guī)劃算法的基本要素，最長公共子序列，)凸多邊形的最優(yōu)三角剖分，0-1背包問題。4貪心算法動(dòng)安排問題，貪心算法的基本性質(zhì)，最優(yōu)裝載，哈夫曼編碼，單源最短路徑，多機(jī)調(diào)度5 回溯法回溯法的算法框架，裝載問題，n后問題，圖的著色算法，批處理作業(yè)調(diào)度，符號三角問題，旅行商問題。6分支限界法分支限界法的基本思想，單源最短路徑，布線問題，旅行售貨問題。(二) 課堂討論的教學(xué)內(nèi)容下列內(nèi)容可以安排討論課：1 貪心算法的基本應(yīng)用2 回溯算法的基本應(yīng)用(三)實(shí)驗(yàn)的教學(xué)內(nèi)容1 棋盤覆蓋算法 2學(xué)時(shí)2 矩陣連乘算法 3學(xué)時(shí)3 最小生成樹 3學(xué)時(shí)4 騎士巡游 3學(xué)時(shí)5 TSP算法并討論算法的加速 3學(xué)時(shí) 共 14學(xué)時(shí)六、學(xué)時(shí)分配表內(nèi) 容講 課討 論實(shí) 驗(yàn)小 計(jì)1算法概述222 遞歸與分治策略82103 動(dòng)態(tài)規(guī)劃6394貪心算法613105 回溯法816156分支限界法44合 計(jì)3421450七、主要參考書1計(jì)算機(jī)算法設(shè)計(jì)與分析 王曉東編著 電子工業(yè)出版社 2計(jì)算與算法導(dǎo)引 盧開登編著 清華大學(xué)出版社 3計(jì)算機(jī)算法基礎(chǔ) 余祥宣編著 華中理工大學(xué)出版社4C 常用算法程序 徐士良編著 清華大學(xué)出版社八、評價(jià)方式（包括作業(yè)、測驗(yàn)、考試等）考核方式：課程結(jié)束采用開卷考試結(jié)合平時(shí)成績（出勤、作業(yè)和實(shí)驗(yàn)）的方法進(jìn)行考核。大綱制訂者：劉建國 大綱審訂者： 大綱批準(zhǔn)者： 二五年九月五日