《算法分析與設(shè)計(jì)》教學(xué)大綱
課程名稱：
| 算法分析與設(shè)計(jì)
| 算法分析與設(shè)計(jì)
| 算法分析與設(shè)計(jì)
|
課程編號(hào)：
| 436416
| 408415
| 420416
|
適用專業(yè)：
| 軟件工程
| 計(jì)算機(jī)科學(xué)與技術(shù)
| 網(wǎng)絡(luò)工程
|
課程類別：
| 專業(yè)任選課
| 專業(yè)任選課
| 專業(yè)任選課
|
課程學(xué)分：
| 3
| 3
| 3
|
總學(xué)時(shí)：
| 48
| 48
| 48
|
其中：理論
| 32
| 32
| 32
|
實(shí)驗(yàn)
| 16
| 16
| 16
|
先修課程：
| C語言程序設(shè)計(jì)
|
一、課程的性質(zhì)、目的與任務(wù)
《算法分析與設(shè)計(jì)》是一門理論性與實(shí)踐性兼顧的課程，是軟件工程、計(jì)算機(jī)科學(xué)與技術(shù)、網(wǎng)絡(luò)工程及相關(guān)專業(yè)的基礎(chǔ)課程。課程是“編譯原理”和“軟件工程”等專業(yè)核心課程的基礎(chǔ)課，為學(xué)習(xí)專業(yè)課程及提高軟件設(shè)計(jì)水平打下良好的基礎(chǔ)。
本課程向?qū)W生系統(tǒng)講述軟件設(shè)計(jì)中常用的算法設(shè)計(jì)與分析方法。學(xué)生通過對(duì)算法設(shè)計(jì)策略的系統(tǒng)學(xué)習(xí)與研究，理解和掌握算法設(shè)計(jì)的主要方法，鍛煉獨(dú)立分析問題和解決問題的能力，為開發(fā)高效的軟件系統(tǒng)及相關(guān)領(lǐng)域的研究工作奠定堅(jiān)實(shí)的基礎(chǔ)。
通過本課程的學(xué)習(xí)，要求學(xué)生理解計(jì)算機(jī)算法效率分析與設(shè)計(jì)所涉及的基本概念和基礎(chǔ)知識(shí)，掌握基本的算法分析方法和常見的算法設(shè)計(jì)方法，能熟練應(yīng)用課程介紹的算法設(shè)計(jì)方法來解決軟件開發(fā)中的實(shí)際問題。通過對(duì)算法實(shí)例的分析，進(jìn)一步加深對(duì)算法設(shè)計(jì)方法的認(rèn)識(shí)和理解。
二、課程教學(xué)基本內(nèi)容與要求
第一章 概述
（一）基本教學(xué)內(nèi)容
1.1 算法和程序
1.2 算法復(fù)雜性算法效率
（二）基本要求
教學(xué)目的：理解算法的概念、算法的時(shí)間復(fù)雜性和空間復(fù)雜性；掌握求解問題的基本步驟；掌握算法運(yùn)行時(shí)間的估計(jì)。
教學(xué)重點(diǎn)：求解問題的基本步驟、算法的概念、程序與算法的區(qū)別、算法效率的分析。
教學(xué)難點(diǎn)：算法時(shí)間復(fù)雜性和空間復(fù)雜性的度量、算法運(yùn)行時(shí)間的估計(jì)。
第二章 遞歸與分治策略
（一）基本教學(xué)內(nèi)容
2.1 遞歸的概念
2.2 分治法的基本思想
2.3 二分搜索技術(shù)
2.4 大整數(shù)的乘法
2.5 矩陣乘法
2.6 棋盤覆蓋
2.7合并排序
2.8快速排序
2.9線性時(shí)間選擇
2.10最接近點(diǎn)對(duì)問題
2.11循環(huán)賽日程表
（二）基本要求
教學(xué)目的：掌握遞歸的概念與的基本原理；理解分治策略的基本原理和效率分析，掌握設(shè)計(jì)有效算法的分治策略。
教學(xué)重點(diǎn)：分治策略的基本原理與應(yīng)用、遞歸算法的效率分析。
教學(xué)難點(diǎn)：分治策略的基本原理與應(yīng)用、遞歸算法的效率分析。
第三章 動(dòng)態(tài)規(guī)劃
（一）基本教學(xué)內(nèi)容
3.1 矩陣連乘問題
3.2 動(dòng)態(tài)規(guī)劃算法的基本要素
3.3 最長公共子序列
3.4 最大子段和
3.5 凸多邊形最優(yōu)三角剖分
3.6 多邊形游戲
3.7 圖像壓縮
3.8 電路布線
3.9 流水作業(yè)調(diào)度
3.10 0-1背包問題
3.11 最優(yōu)二叉搜索樹
3.12 動(dòng)態(tài)規(guī)劃加速原理
（二）基本要求
教學(xué)目的：理解動(dòng)態(tài)規(guī)劃算法的概念；掌握動(dòng)態(tài)規(guī)劃算法的基本要素；掌握設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟以及典型問題的應(yīng)用與分析。
教學(xué)重點(diǎn)：動(dòng)態(tài)規(guī)劃算法的基本思想、動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)策略。
教學(xué)難點(diǎn)：動(dòng)態(tài)規(guī)劃典型問題的應(yīng)用。
第四章 貪心算法
（一）基本教學(xué)內(nèi)容
4.1 活動(dòng)安排問題
4.2 貪心算法的基本要素
4.3 最優(yōu)裝載
4.4 哈夫曼編碼
4.5 單源最短路徑
4.6 最小生成樹
4.7 多機(jī)調(diào)度問題
（二）基本要求
教學(xué)目的：理解貪心算法的基本思想、適用條件；掌握貪心算法的設(shè)計(jì)策略，掌握貪心算法典型問題的應(yīng)用與分析。
教學(xué)重點(diǎn)：貪心策略的基本思想、適用條件及其應(yīng)用、適用條件及其應(yīng)用。
教學(xué)難點(diǎn)：貪心算法典型問題的解決方法及時(shí)間復(fù)雜性的分析。
第五章 回溯法
（一）基本教學(xué)內(nèi)容
5.1 回溯法的算法框架
5.2 裝載問題
5.3 批處理作業(yè)調(diào)度
5.4 符號(hào)三角形問題
5.5 n后問題
5.6 0-1背包問題
5.7 最大團(tuán)問題
5.8 圖的m著色問題
5.9 旅行售貨員問題
5.1 0 圓排列問題
5.1 1 電路板排列問題
5.1 2 連續(xù)郵資問題
5.1 3 回溯法的效率分析
（二）基本要求
教學(xué)目的：理解回溯法的基本思想及效率估計(jì)，限界函數(shù)；掌握回溯法在典型問題的應(yīng)用及分析。
教學(xué)重點(diǎn)：回溯法的基本思想、限界函數(shù)、效率估計(jì)、適用條件及其應(yīng)用。
教學(xué)難點(diǎn)：回溯法的典型問題的解決方法及時(shí)間復(fù)雜性的分析。
第六章 分支限界法
（一）基本教學(xué)內(nèi)容
6.1 分支限界法的基本思想
6.2 單源最短路徑問題
6.3 裝載問題
6.4 布線問題
6.5 0-1背包問題
6.6 最大團(tuán)問題
6.7 旅行售貨員問題
6.8 電路板排列問題
6.9 批處理作業(yè)調(diào)度
（二）基本要求
教學(xué)目的：理解分支限界法的基本思想及效率估計(jì)；掌握分支限界法的算法框架；掌握分支限界法在典型問題的應(yīng)用。
教學(xué)重點(diǎn)：分支限界法的搜索策略、算法框架、典型問題的設(shè)計(jì)策略。
教學(xué)難點(diǎn)：分支限界法典型問題的設(shè)計(jì)策略。
第七章 隨機(jī)化算法
（一）基本教學(xué)內(nèi)容
7.1 隨機(jī)數(shù)
7.2 數(shù)值隨機(jī)化算法
7.3 舍伍德(Sherwood)算法
7.4 拉斯維加斯(Las Vegas)算法
7.5 蒙特卡羅(Monte Carlo)算法
（二）基本要求
教學(xué)目的：理解產(chǎn)生偽隨機(jī)數(shù)的算法；掌握數(shù)值概率算法的設(shè)計(jì)思想；掌握蒙特卡羅算法、拉斯維加斯算法和舍伍德算法的設(shè)計(jì)思想。
教學(xué)重點(diǎn)：數(shù)值概率算法、蒙特卡羅算法、拉斯維加斯算法和舍伍德算法。
教學(xué)難點(diǎn)：概率算法的設(shè)計(jì)策略。
第八章 線性規(guī)劃與網(wǎng)絡(luò)流
（一）基本教學(xué)內(nèi)容
8.1線性規(guī)劃問題和單純形算法
8.2最大網(wǎng)絡(luò)流問題
8.3最小費(fèi)用流問題
（二）基本要求
教學(xué)目的：理解線性規(guī)劃算法的模型，理解網(wǎng)絡(luò)與網(wǎng)絡(luò)流的基本概念；掌握線性規(guī)劃問題的單純形算法；掌握網(wǎng)絡(luò)最大流的增廣路算法與預(yù)流推進(jìn)算法；掌握網(wǎng)絡(luò)最小費(fèi)用流的消圈算法、最小費(fèi)用路算法與單純形算法。
教學(xué)重點(diǎn)：線性規(guī)劃問題的單純形算法、網(wǎng)絡(luò)最大流的算法、網(wǎng)絡(luò)最小費(fèi)用流算法。
教學(xué)難點(diǎn)：網(wǎng)絡(luò)最大流的算法、網(wǎng)絡(luò)最小費(fèi)用流算法。
第九章 NP完全性理論與近似算法
（一）基本教學(xué)內(nèi)容
9.1 計(jì)算模型
9.2 P類與NP類問題
9.3 NP完全問題
9.4 NP完全問題的近似算法
（二）基本要求
教學(xué)目的：理解RAM、RASP和圖靈機(jī)的計(jì)算模型，理解非確定圖靈機(jī)的概念；理解NP完全問題的概念；理解近似算法的性能比及多項(xiàng)式時(shí)間近似格式的概念；掌握近似算法在典型問題的應(yīng)用。
教學(xué)重點(diǎn)：計(jì)算模型、NP完全問題、近似算法的性能比與典型應(yīng)用。
教學(xué)難點(diǎn)：近似算法在典型問題的應(yīng)用。
三、課程各章節(jié)學(xué)時(shí)分配
序號(hào)
| 內(nèi)容
| 理論學(xué)時(shí)
| 實(shí)驗(yàn)學(xué)時(shí)
|
計(jì)科
| 網(wǎng)工
| 軟工
| 計(jì)科
| 網(wǎng)工
| 軟工
|
1
| 算法概述
| 2
| 2
| 2
|
|
|
|
2
| 遞歸與分治策略
| 4
| 4
| 4
| 4
| 4
| 4
|
3
| 動(dòng)態(tài)規(guī)劃
| 6
| 6
| 6
| 4
| 4
| 4
|
4
| 貪心算法
| 4
| 4
| 4
| 2
| 2
| 2
|
5
| 回溯法
| 4
| 4
| 4
| 2
| 2
| 2
|
6
| 分支限界法
| 2
| 2
| 2
| 2
| 2
| 2
|
7
| 概率算法
| 2
| 2
| 2
|
|
|
|
8
| 線性規(guī)劃與網(wǎng)絡(luò)流
| 4
| 4
| 4
| 2
| 2
| 2
|
9
| NP完全理論與近似算法
| 4
| 4
| 4
|
|
|
|
合計(jì)
| 32
| 32
| 32
| 16
| 16
| 16
|
四、本課程課外學(xué)習(xí)與修學(xué)指導(dǎo)
本課程是“編譯原理”和“軟件工程”等專業(yè)核心課程的基礎(chǔ)課，具有很強(qiáng)的實(shí)踐性。要學(xué)好本課程，必須做到理論與實(shí)踐緊密結(jié)合。要求學(xué)生多參閱相關(guān)書籍，特別是多做練習(xí)，多上機(jī)實(shí)驗(yàn)，掌握常用算法的基本原理與設(shè)計(jì)方法。為配合課程教學(xué)，將在學(xué)校的程序設(shè)計(jì)在線平臺(tái)上開設(shè)算法分析與設(shè)計(jì)課程的專題練習(xí)。
五、本課程考核方式及成績?cè)u(píng)定標(biāo)準(zhǔn)
考核方式：閉卷考試
成績?cè)u(píng)定方法：本課程的考核是平時(shí)成績、實(shí)驗(yàn)成績和期終考試成績相結(jié)合。具體比例為：上課出勤、作業(yè)占20%，實(shí)驗(yàn)占20%，期末考試成績占60%。
其中期未考試總分100分，基礎(chǔ)題占50%，中等難度題占40%，較難題占10%。考試題型主要有：選擇題、填空題、判斷題、程序填空題、程序分析題、編寫程序題等。
六、教材及參考書
[1] 王曉東.《計(jì)算機(jī)算法分析與設(shè)計(jì)（第4版）》.北京：電子工業(yè)出版社，2012.
[2] 趙端陽 編著.《算法分析與設(shè)計(jì)》.北京：清華大學(xué)出版社，2012.
[3] 石志國，劉冀偉，姚亦飛 編著.《算法分析與設(shè)計(jì)（C++描述）》.北京：清華大學(xué)出版社，2010.
[4] 霍紅衛(wèi) 譯.《算法分析與設(shè)計(jì)》.北京：人民郵電出版社，2006.
[5] 吳偉旭 方世昌譯.《算法分析與設(shè)計(jì)》.北京：電子工業(yè)出版社，2004.
大綱撰寫人： 袁輝勇
大綱審閱人： 羅如為
教學(xué)副主任：易葉青
編寫日期：2012年6月
