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

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

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

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分支限界法分支限界法的基本思想，單源最短路徑，布線問題，旅行售貨問題。(二) 課堂討論的教學內(nèi)容下列內(nèi)容可以安排討論課：1 貪心算法的基本應(yīng)用

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