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

1、課程編號：“算法設(shè)計與分析”課程教學(xué)大綱algorithm design and analysis course outline50學(xué)時 2.5學(xué)分一、本課程的性質(zhì)、目的、任務(wù)算法設(shè)計與分析是計算機科學(xué)的重要基礎(chǔ),介紹常用設(shè)計算法的策略:分治,貪心,規(guī)劃,回溯等,通過本課程的學(xué)習(xí)使學(xué)生掌握基本算法的分析,設(shè)計技能和方法。通過算法設(shè)計與分析的學(xué)習(xí)和研究，能掌握算法設(shè)計的主要方法，培養(yǎng)對算法的計算復(fù)雜性正確分析的能力，為獨立設(shè)計算法和對算法進行復(fù)雜性分析奠定堅實的基礎(chǔ)。本課程使學(xué)生能夠切實掌握算法設(shè)計與分析的基本知識,掌握常用算法的設(shè)計策略，包括：遞歸與分治法，動態(tài)規(guī)劃，貪心算法與回溯法。掌握計算

2、機領(lǐng)域中常用的非數(shù)值計算算法，并學(xué)會用這些算法解決實際問題。二、適用專業(yè)計算機科學(xué)與技術(shù)三、先修課程c+面向程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)四、課程的基本要求通過本課程的學(xué)習(xí)，學(xué)生應(yīng)能達到下列要求：1理解算法的定義及特性，了解算法與程序的區(qū)別，熟悉算法復(fù)雜性的分析。2 理解遞歸的概念，掌握遞歸方程求解方法，掌握分治算法的設(shè)計策略。3 了解動態(tài)規(guī)劃算法的基本要素，了解態(tài)規(guī)劃算法的設(shè)計方法。4理解貪心算法的基本性質(zhì)，掌握貪心算法的設(shè)計原則。5 熟悉問題的解空間、解空間樹的概念，用問題的約束條件對解空間樹進行修剪、遞歸回溯；掌握回溯算法的設(shè)計方法。6了解分支限界法的基本思想。五、課程的教學(xué)內(nèi)容（一）課堂講授的教學(xué)

3、內(nèi)容：1算法概述算法與程序，算法復(fù)雜性的分析。2 遞歸與分治策略遞歸的概念，遞歸方程求解方法，二分搜索技術(shù)，大數(shù)的乘法，strassen矩陣相乘，棋盤覆蓋算法3 動態(tài)規(guī)劃矩陣連乘問題，動態(tài)規(guī)劃算法的基本要素，最長公共子序列，)凸多邊形的最優(yōu)三角剖分，0-1背包問題。4貪心算法動安排問題，貪心算法的基本性質(zhì)，最優(yōu)裝載，哈夫曼編碼，單源最短路徑，多機調(diào)度5 回溯法回溯法的算法框架，裝載問題，n后問題，圖的著色算法，批處理作業(yè)調(diào)度，符號三角問題，旅行商問題。6分支限界法分支限界法的基本思想，單源最短路徑，布線問題，旅行售貨問題。(二) 課堂討論的教學(xué)內(nèi)容下列內(nèi)容可以安排討論課：1 貪心算法的基本應(yīng)用

4、2 回溯算法的基本應(yīng)用(三)實驗的教學(xué)內(nèi)容1 棋盤覆蓋算法 2學(xué)時2 矩陣連乘算法 3學(xué)時3 最小生成樹 3學(xué)時4 騎士巡游 3學(xué)時5 tsp算法并討論算法的加速 3學(xué)時 共 14學(xué)時六、學(xué)時分配表內(nèi) 容講 課討 論實 驗小 計1算法概述222 遞歸與分治策略82103 動態(tài)規(guī)劃6394貪心算法613105 回溯法816156分支限界法44合 計3421450七、主要參考書1計算機算法設(shè)計與分析 王曉東編著 電子工業(yè)出版社 2計算與算法導(dǎo)引 盧開登編著 清華大學(xué)出版社 3計算機算法基礎(chǔ) 余祥宣編著 華中理工大學(xué)出版社4c 常用算法程序 徐士良編著 清華大學(xué)出版社八、評價方式（包括作業(yè)、測驗、考試等）考核方式：課程