1、算法分析與設計課程教 學 大 綱課程代碼：03020280算法分析與設計課程教學大綱（總學時數：48（408），學分數：3）一、課程的性質、任務和目的以算法設計策略為知識單元系統地介紹計算機算法的設計方法和分析方法。在教學中除介紹算法的基本概念、計算復雜性分析以外，重點介紹遞歸算法、分治算法、貪心算法、動態規劃算法、回溯算法和分支定界算法的基本思想及應用，為計算機專業的學生提供一個廣泛扎實的計算機算法知識基礎。 二、課程的基本內容和要求（一）算法概述 教學內容：1. 算法與程序2. 算法分析的基本概念和理論3. 簡單程序的算法復雜性分析教學要求：了解算法的基本概念，算法在程序設計中的重要性。掌

2、握程序復雜度度量的基本方法。（二）遞歸的基本概念 教學內容：1. 遞歸的概念2. 階乘函數3. fibonacci數列4. ackerman函數5. hanoi塔問題6. 整數劃分問題教學要求：掌握遞歸程序復雜度的計算方法，了解經典遞歸問題解法。學會使用遞歸方法分析解決實際問題。（三）分治策略 教學內容：1. 分治法的基本思想2. 遞歸方程解的展開方法3. 二分搜索技術4. 大整數的乘法5. strassen矩陣乘法6. 合并排序7. 快速排序8. 棋盤覆蓋問題9. 循環賽日程表教學要求：掌握分治策略的基本思想以及用分治法解決問題的一般技巧。重點掌握二分搜索技術。（四）動態規劃法 教學內容：1

3、. 動態規劃算法的基本思想2. 動態規劃算法的基本要素3. 矩陣連乘問題4. 最長公共子序列5. 最大子段和問題6. 0/1背包問題7. 流水作業調度8. 圖像壓縮問題9. 凸多邊形最優三角剖分10. 動態規劃的加速原理*教學要求：掌握動態規劃解決問題的一般過程，掌握矩陣連乘問題的計算技巧。學會使用動態規劃解決實際問題。（五）貪心算法 教學內容：1. 找零錢問題2. 貪心算法的基本要素3. 機器調度問題4. 活動安排問題5. 最優裝載問題6. 單源最短路徑問題7. 哈夫曼編碼8. 最小生成樹9. 貪心算法的理論基礎*教學要求：掌握貪心法解決問題的一般步驟，掌握貪心法和動態規劃方法的異同。學會使

4、用貪心法解決實際問題。（六）回溯法 教學內容：1. 回溯法的基本框架2. 0/1背包問題3. 迷宮老鼠4. 裝載問題5. n后問題6. 騎士遍歷問題7. 批處理作業調度8. 回溯法的效率分析*教學要求：掌握回溯法解決問題的一般步驟，掌握回溯法與貪心法、動態規劃法的異同以及不同算法的效率分析。學會使用回溯法解決實際問題。（七）分支限界法教學內容：1. 分支限界法的基本思想2. 迷宮老鼠問題3. 布線問題4. 0/1背包問題5. 裝載問題6. 批處理作業調度問題教學要求：掌握分支限界法解決問題的基本思想，注意比較與前四種算法的異同，學會使用分支限界法解決實際問題。（八）np完全性理論* 教學內容：

5、1. 計算模型2. p類與np類問題3. np完全問題4. 一些典型的np完全問題教學要求：了解np基本理論，了解np問題和非np問題的異同，研究新方法解決np問題的可能性說明：本章為選修部分，可根據教學情況安排為講授或自學。三、學時分配表序號內容講授實驗小計1算法概述2022遞歸的基本概念2023分治策略4154動態規劃法102125貪心算法8196回溯法6287分支限界法6288np完全性理論*2029其它202小 計40848四、實驗學時分配表序號內 容要 求小計實驗一分治策略掌握分治策略的基本思想以及用分治法解決問題的一般技巧1學時實驗二動態規劃掌握動態規劃解決問題的一般過程，學會使用動態規劃解決實際問題。2學時實驗三貪心算法掌握貪心法解決問題的一般步驟，學會使用貪心法解決實際1學時實驗四回溯法掌握回溯法解決問題的一般步驟，學會使用回溯法解決實際問題。2學時實驗五分支限界法掌握分支限界法解決問題的基本思想，學會使用分支限界法解決實際問題。2學時小計8學時五、有關說明1、 教學建議在教學中安排一定的習題討論時間，使學生鍛煉分析問題的能力。教學中的一些習題建議學生安排上機，這樣才能全面掌握常用算法的分析和設計技術。2、 課程建議教材計算機算法設計與分析王曉東編著電子工業出版社3、 課程建議參考書計算機算法基礎 鄒海明編著華中理工大學出