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

1、算法設(shè)計(jì)與分析課程教學(xué)大綱課程名稱：算法設(shè)計(jì)與分析英文名稱：The Design and Analysis of Algorithm課程編號(hào)：x2050121學(xué) 時(shí) 數(shù)：48其中實(shí)驗(yàn)學(xué)時(shí)數(shù)：16 課外學(xué)時(shí)數(shù)：0學(xué) 分 數(shù)：3.0適用專業(yè)：軟件工程、軟件工程（金融方向）、軟件工程（物流方向）、信息與計(jì)算科學(xué)一、課程的性質(zhì)和任務(wù)算法設(shè)計(jì)與分析是軟件工程、軟件工程（金融方向）、軟件工程（物流方向）和信息與計(jì)算科學(xué)等專業(yè)的一門專業(yè)基礎(chǔ)課。軟件的效率和穩(wěn)定性取決于軟件中所采用的算法；對(duì)于一般程序員和計(jì)算機(jī)專業(yè)學(xué)生，學(xué)習(xí)算法設(shè)計(jì)與分析課程，可以開(kāi)闊編程思路，編寫出優(yōu)質(zhì)程序。通過(guò)本課程的學(xué)習(xí)，學(xué)生要掌握幾種

2、常用的算法設(shè)計(jì)策略，包括遞歸與分治策略、動(dòng)態(tài)規(guī)劃算法、貪心算法、回溯法、分支限界法、概率算法、線性規(guī)劃和網(wǎng)絡(luò)流法和NP完全性理論與近似算法等，并會(huì)分析算法的效率，能夠用所學(xué)方法解決實(shí)際問(wèn)題。二、課程教學(xué)內(nèi)容的基本要求、重點(diǎn)和難點(diǎn)（一）算法概述掌握算法，算法復(fù)雜度的基本概念，及時(shí)間復(fù)雜度的估算方法。（二）遞歸與分治法掌握遞歸的概念，學(xué)會(huì)用遞歸方法解決實(shí)際問(wèn)題，熟練掌握利用分治法解決問(wèn)題的基本思想，會(huì)用某高級(jí)語(yǔ)言對(duì)算法進(jìn)行描述，并對(duì)算法復(fù)雜度（時(shí)間和空間）進(jìn)行分析。主要內(nèi)容：遞歸概念，分治法基本思想，二分搜索技術(shù)，大整數(shù)乘法，矩陣乘法，棋盤覆蓋，合并排序，快速排序，線性時(shí)間選擇，最接近點(diǎn)對(duì)問(wèn)題，循

3、環(huán)賽日程表。重點(diǎn)：遞歸，分治法的基本思想。難點(diǎn)：遞歸赫分治法的應(yīng)用。（三）動(dòng)態(tài)規(guī)劃熟練掌握利用動(dòng)態(tài)規(guī)劃方法解決問(wèn)題的基本思想，學(xué)會(huì)如何將問(wèn)題化為多階段圖的方法，并能對(duì)具體問(wèn)題寫出正確的遞推公式。主要內(nèi)容：動(dòng)態(tài)規(guī)劃的基本要素，矩陣連乘，最長(zhǎng)公共子序列，最大子段和，凸多邊形最優(yōu)三角剖分，多邊形游戲，圖像壓縮，電路布線，流水作業(yè)調(diào)度，0-1背包問(wèn)題，最優(yōu)二叉搜索樹(shù)。重點(diǎn)：動(dòng)態(tài)規(guī)劃算法的基本要素。難點(diǎn)：動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)。（四）貪心算法掌握利用貪心算法解決問(wèn)題的基本思想，會(huì)用某高級(jí)語(yǔ)言編寫用貪心算法解決問(wèn)題的程序，并能對(duì)算法的復(fù)雜度，可靠性進(jìn)行分析。主要內(nèi)容：貪心算法的基本要素，活動(dòng)安排問(wèn)題，最優(yōu)裝載

4、，哈夫曼編碼，單源最短路徑，最小生成樹(shù)，多機(jī)調(diào)度。重點(diǎn)：貪心算法的基本要素。難點(diǎn)：貪心算法的具體應(yīng)用。（五）回溯法掌握利用回溯法解決問(wèn)題的基本思想，會(huì)用回溯法解決：n個(gè)皇后問(wèn)題，圖的m著色問(wèn)題，批處理作業(yè)調(diào)度問(wèn)題等，并能準(zhǔn)確地分析回溯法的效率及穩(wěn)定性。主要內(nèi)容：回溯法的算法框架、符號(hào)，三角形問(wèn)題，n個(gè)皇后問(wèn)題，最大團(tuán)問(wèn)題，圖的m著色問(wèn)題，旅行售貨員問(wèn)題，圓排列問(wèn)題，連續(xù)郵資問(wèn)題，電路板排列問(wèn)題。重點(diǎn)：回溯法的基本思想，回溯法的效率分析。難點(diǎn)：回溯法的設(shè)計(jì)。（六）分支限界法掌握利用分支限界法解決問(wèn)題的基本思想，能用多種不同方法解法同一問(wèn)題，并分析各方法的效率。主要內(nèi)容：分支限界的基本思想，單源最

5、短路徑，布線問(wèn)題，01背包問(wèn)題，批處理作業(yè)調(diào)度問(wèn)題。重點(diǎn)：分支限界法的基本思想和各方法的效率分析。難點(diǎn)：分支限界法限界函數(shù)的設(shè)計(jì)。（七）概率算法掌握利用概率算法的基本思想，會(huì)用概率算法解決有關(guān)問(wèn)題。主要內(nèi)容：概率算法的基本思想，隨機(jī)數(shù)，數(shù)值概率算法，舍伍德算法，拉斯維加斯算法，蒙特卡羅算法。重點(diǎn)：概率算法的基本思想及準(zhǔn)確應(yīng)用。難點(diǎn)：概率算法的設(shè)計(jì)。（八）線性規(guī)劃和網(wǎng)絡(luò)流了解線性規(guī)劃模型的特點(diǎn)、線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型及退化處理，掌握線性規(guī)劃問(wèn)題解的概念、有關(guān)解的基本定理；掌握單純形法的原理和求解方法；掌握實(shí)踐中常見(jiàn)問(wèn)題的建模方法。掌握最大網(wǎng)絡(luò)流問(wèn)題的求解方法和最小費(fèi)用流問(wèn)題的求解方法。主要內(nèi)容：線

6、性規(guī)劃的基本概念、定理及單純形算法，最大網(wǎng)絡(luò)流和最小費(fèi)用流問(wèn)題的解法。重點(diǎn)：線性規(guī)劃的思想及單純形算法、最大網(wǎng)絡(luò)流問(wèn)題最小費(fèi)用流問(wèn)題的求解方法。難點(diǎn)：算法的具體設(shè)計(jì)技巧。（九）NP完全性理論與近似算法了解NP完全性問(wèn)題，掌握P類與NP類問(wèn)題的劃分。掌握利用近似算法解決問(wèn)題的基本思想，能對(duì)其可靠性進(jìn)行分析。主要內(nèi)容：計(jì)算模型，P類與NP類問(wèn)題，NP完全問(wèn)題，合取范式（CNF）頂點(diǎn)覆蓋問(wèn)題，哈密頓回路問(wèn)題；近似算法的基本思想及性能，頂點(diǎn)覆蓋問(wèn)題的近似算法，集合覆蓋問(wèn)題的近似算法，子集合問(wèn)題的近似算法。重點(diǎn)：NP完全問(wèn)題、近似算法的設(shè)計(jì)與可靠性分析。難點(diǎn)：NP和P類問(wèn)題劃分，近似法設(shè)計(jì)。三、教學(xué)方式

7、及學(xué)時(shí)分配序號(hào)主要內(nèi)容主要教學(xué)方 式學(xué)時(shí)分配輔導(dǎo)答疑比 例一算法概述講授22:1二遞歸與分治法講授+實(shí)驗(yàn)4+22:1三動(dòng)態(tài)規(guī)劃講授+實(shí)驗(yàn)4+22:1四貪心算法講授+實(shí)驗(yàn)4+22:1五回溯法講授+實(shí)驗(yàn)4+22:1六分支限界法講授+實(shí)驗(yàn)4+22:1七概率算法講授+實(shí)驗(yàn)4+22:1八線性規(guī)劃和網(wǎng)絡(luò)流講授+實(shí)驗(yàn)4+22:1九NP完全性理論與近似算法講授+實(shí)驗(yàn)2+22:1四、課程其他教學(xué)環(huán)節(jié)要求（一）實(shí)驗(yàn)環(huán)節(jié)：實(shí)驗(yàn)學(xué)時(shí)數(shù)為16，實(shí)驗(yàn)項(xiàng)目及內(nèi)容詳見(jiàn)實(shí)驗(yàn)教學(xué)大綱。（二）作業(yè)：根據(jù)授課進(jìn)度，布置作業(yè)，每章講授結(jié)束后，收一次作業(yè)，批改后做集體答疑，講解作業(yè)中出現(xiàn)的問(wèn)題。作業(yè)的題型主要是以算法設(shè)計(jì)題為主。（三）課外：充分利用上課的實(shí)驗(yàn)時(shí)間進(jìn)行吸收消化所學(xué)理論，同時(shí)在完成課上布置的作業(yè)外，課下應(yīng)利用業(yè)余時(shí)間進(jìn)行自主學(xué)習(xí)，提高程學(xué)設(shè)計(jì)能力。五、本課程與其他課程的聯(lián)系先修課程是C+程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學(xué)，后續(xù)課程是培養(yǎng)計(jì)劃中的各門專業(yè)課。六、教學(xué)參考書目（授課教材）算