課程代碼:* * * *

課程負(fù)責(zé)人:* * * *

課程中文名稱(chēng):算法設(shè)計(jì)與分析

課程的英文名稱(chēng):算法設(shè)計(jì)與分析

課程類(lèi)別:必選

課程分?jǐn)?shù):3

課時(shí):54

教學(xué)目標(biāo):計(jì)算機(jī)科學(xué)與技術(shù)及相關(guān)專(zhuān)業(yè)本科

本課程的主導(dǎo)課程:高等數(shù)學(xué)、離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)

一、教學(xué)目的(Bold號(hào))

本課程是計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)的必修課。本課程的目的是培養(yǎng)學(xué)生分析問(wèn)題和解決問(wèn)題的能力，使學(xué)生掌握算法設(shè)計(jì)的基本技能和方法，熟悉算法分析的基本技術(shù)，熟練運(yùn)用一些常用算法，解決一些綜合性問(wèn)題，為學(xué)生進(jìn)一步學(xué)習(xí)后續(xù)課程打下良好的基礎(chǔ)。

二、教學(xué)要求(黑體5號(hào))

通過(guò)課堂教學(xué)、課堂實(shí)踐與討論互動(dòng)、課后作業(yè)和計(jì)算機(jī)實(shí)驗(yàn)，系統(tǒng)介紹了計(jì)算機(jī)算法的概念和算法設(shè)計(jì)的基本技巧。使學(xué)生掌握計(jì)算機(jī)算法的基本概念和特點(diǎn)，了解算法分析和設(shè)計(jì)技巧在計(jì)算機(jī)相關(guān)學(xué)科中的重要性，掌握算法時(shí)間復(fù)雜度的分析方法和基本算法設(shè)計(jì)策略，并結(jié)合具體實(shí)例使學(xué)生重點(diǎn)關(guān)注分而治之法、蠻力法、回溯法、分支定界法、貪心法、動(dòng)態(tài)規(guī)劃法、網(wǎng)絡(luò)流、幾何計(jì)算、概率算法、近似算法等常見(jiàn)算法設(shè)計(jì)策略，了解計(jì)算復(fù)雜度的基本理論，并有靈活運(yùn)用所學(xué)知識(shí)的能力。

三.課程內(nèi)容和時(shí)間分配(粗體5號(hào))

1.算法設(shè)計(jì)與分析導(dǎo)論。本文介紹了算法的概念、算法分析方法以及STL在算法設(shè)計(jì)中的應(yīng)用。

2.遞歸算法設(shè)計(jì)技術(shù)。介紹了遞歸的概念、遞歸算法的設(shè)計(jì)方法及相關(guān)實(shí)例、遞歸算法到非遞歸算法的轉(zhuǎn)換以及遞歸公式的計(jì)算。

3.分而治之。介紹了分治法的策略和求解過(guò)程，討論了分治法求解排序問(wèn)題、搜索問(wèn)題、最大連續(xù)子序列和問(wèn)題、大整數(shù)乘法問(wèn)題和矩陣乘法問(wèn)題的典型算法，并簡(jiǎn)要介紹了并行計(jì)算的概念。

4.暴力方法。介紹了蠻力方法的特點(diǎn)、蠻力方法的基本應(yīng)用實(shí)例、遞歸在蠻力方法中的應(yīng)用實(shí)例以及圖的深度優(yōu)先和廣度優(yōu)先遍歷算法。

5.追溯法。介紹了solution 空的概念和回溯法的算法框架，討論了用回溯法求解0/1背包問(wèn)題、裝載問(wèn)題、子集與問(wèn)題、N皇后問(wèn)題、圖的M著色問(wèn)題、任務(wù)分配問(wèn)題、活動(dòng)安排問(wèn)題和流水車(chē)間調(diào)度問(wèn)題的典型算法。

6.分支定界法。介紹了分支定界法、隊(duì)列型分支定界法和優(yōu)先級(jí)隊(duì)列型分支定界法的特點(diǎn)和算法框架，討論了求解0/1背包問(wèn)題、圖的單源最短路徑、任務(wù)分配問(wèn)題和流水車(chē)間調(diào)度問(wèn)題的典型算法。

7.貪婪法。介紹了貪心法求解問(wèn)題的策略、求解過(guò)程和性質(zhì)，討論了用貪心法求解活動(dòng)調(diào)度問(wèn)題、背包問(wèn)題、最優(yōu)裝載問(wèn)題、田忌賽馬問(wèn)題、多機(jī)調(diào)度問(wèn)題、霍夫曼編碼和流水車(chē)間調(diào)度問(wèn)題的典型算法。

8.動(dòng)態(tài)規(guī)劃。介紹了動(dòng)態(tài)規(guī)劃的原理和求解步驟，討論了求解整數(shù)分裂問(wèn)題、最大連續(xù)子序列和問(wèn)題、三角形最小路徑問(wèn)題、最長(zhǎng)公共子序列問(wèn)題、最長(zhǎng)遞增子序列問(wèn)題、編輯距離問(wèn)題、0/1背包問(wèn)題、完全背包問(wèn)題、資源分配問(wèn)題、會(huì)議安排問(wèn)題和滾動(dòng)數(shù)組問(wèn)題的典型算法。

9.圖形算法設(shè)計(jì)。討論了構(gòu)造圖的最小生成樹(shù)的兩種算法(Prim和Kruskal算法，以及搜索集的應(yīng)用)和尋找圖的最短路徑的四種算法(Dijkstra、Bellman-Ford、SPFA和Floyd)，并采用五種算法求解旅行商問(wèn)題(TSP問(wèn)題)。最后，介紹了網(wǎng)絡(luò)流的相關(guān)概念以及求最大流和最小費(fèi)用最大流的算法。

10.幾何計(jì)算。介紹了幾何計(jì)算中常用的向量運(yùn)算，以及求解凸包問(wèn)題、最近點(diǎn)對(duì)問(wèn)題和最遠(yuǎn)點(diǎn)對(duì)問(wèn)題的典型算法。

11.計(jì)算復(fù)雜性理論介紹。介紹了圖靈機(jī)計(jì)算模型、P類(lèi)和NP類(lèi)問(wèn)題以及NPC問(wèn)題。

12.概率算法和近似算法。介紹了這兩種算法的特點(diǎn)和基本算法設(shè)計(jì)方法。

課程內(nèi)容和課時(shí)分配表

內(nèi)在內(nèi)容

學(xué)習(xí)時(shí)間

1.算法設(shè)計(jì)與分析導(dǎo)論

四

2.遞歸算法設(shè)計(jì)技術(shù)

四

3.分而治之

四

4.強(qiáng)力法

四

5.追溯方法

六

6.分支定界法

四

7.貪婪方法

四

8.動(dòng)態(tài)規(guī)劃

六

9.圖形算法設(shè)計(jì)

八

10.幾何計(jì)算

四

11.計(jì)算復(fù)雜性理論導(dǎo)論

三

12、概率算法和近似算法

三

四、考核方法(加粗五項(xiàng))

課堂練習(xí)，課后作業(yè)，期末考試，計(jì)算機(jī)實(shí)驗(yàn)。

動(dòng)詞 （verb的縮寫(xiě)）推薦書(shū)籍

算法設(shè)計(jì)與分析(第二版)

其他相關(guān)教材