課程教學大綱課程基本信息課程名稱計算機算法設計與分析選用教材王曉東，《計算機算法設計與分析（第6版）》，電子工業(yè)出版社總學時80學時(理論授課：56學時，實驗/習題課：24學時)課程類型專業(yè)核心課先修課程《程序設計基礎》、《數(shù)據(jù)結構》、《離散數(shù)學》、《高等數(shù)學》課程目標序號課程教學目標1掌握算法復雜性分析的基本方法。2理解并掌握五大經(jīng)典算法設計策略（分治、動態(tài)規(guī)劃、貪心、回溯、分支限界）的核心思想、適用條件和實現(xiàn)要點。3能夠運用所學算法策略設計高效算法解決實際應用問題。4了解NP完全性理論、隨機化算法、網(wǎng)絡流、串匹配及數(shù)論算法等高級主題，為后續(xù)學習和研究打下基礎。5通過編程實踐，提升算法實現(xiàn)、調試和優(yōu)化能力。學時分配總表章節(jié)內容理論學時實驗/習題學時總學時第1章算法概述426第2章遞歸與分治策略8412第3章動態(tài)規(guī)劃10414第4章貪心算法6410第5章回溯法8412第6章分支限界法628第7章隨機化算法426第8/9/10章專題選講(網(wǎng)絡流/串算法/數(shù)論算法三選二)426機動與復習課程總結、復習、考核606合計562480教學進度與內容安排章節(jié)教學內容學時第一部分：基礎與核心策略52第1章算法概述理論(4h)：算法定義、特性與程序的區(qū)別；算法時間與空間復雜性分析（重點講解漸進符號O、Ω、θ的意義和用法）；NP完全性理論的基本概念（P、NP、NPC問題，歸約方法簡介）。6實踐(2h)：完成算法實現(xiàn)題1中的題目，使用不同語言實現(xiàn)基礎算法并進行復雜性分析。第2章遞歸與分治策略理論(8h)：遞歸思想與遞歸方程求解（代入法、遞歸樹法、主定理）；分治法框架；重點講解：二分搜索、合并排序、快速排序、線性時間選擇算法。介紹大整數(shù)乘法、Strassen矩陣乘法和棋盤覆蓋等問題。12實踐(4h)：實現(xiàn)快速排序/合并排序，并分析性能；實現(xiàn)線性時間選擇算法；選做棋盤覆蓋或循環(huán)賽日程表。第3章動態(tài)規(guī)劃理論(10h)：動態(tài)規(guī)劃的基本思想（最優(yōu)子結構、重疊子問題）；重點詳解：矩陣連乘、最長公共子序列（LCS）、最大子段和、0-1背包問題、最優(yōu)二叉搜索樹。講解動態(tài)規(guī)劃算法的基本要素。14實踐(4h)：實現(xiàn)矩陣連乘問題的備忘錄和動態(tài)規(guī)劃算法；實現(xiàn)LCS問題；實現(xiàn)0-1背包問題的動態(tài)規(guī)劃解法。這是難點和重點，安排較多實踐時間。第4章貪心算法理論(6h)：貪心算法的基本思想（貪心選擇性質、最優(yōu)子結構）；重點詳解：活動安排問題、哈夫曼編碼、單源最短路徑（Dijkstra算法）、最小生成樹（Prim和Kruskal算法）。對比動態(tài)規(guī)劃與貪心算法的異同。10實踐(4h)：實現(xiàn)哈夫曼編碼并進行文件壓縮/解壓演示；實現(xiàn)Dijkstra算法或Prim算法。第5章回溯法理論(8h)：回溯法的算法框架（解空間樹、深度優(yōu)先搜索、剪枝函數(shù)）；重點詳解：裝載問題、n皇后問題、0-1背包問題（回溯版）、圖的m著色問題、旅行售貨員問題（TSP）。12實踐(4h)：實現(xiàn)n皇后問題的回溯算法并展示所有解；實現(xiàn)回溯法解決0-1背包問題或圖的m著色問題。第6章分支限界法理論(6h)：分支限界法的基本思想（廣度優(yōu)先搜索、FIFO/LIFO/優(yōu)先隊列）；重點詳解：裝載問題（隊列式vs優(yōu)先隊列式）、0-1背包問題、單源最短路徑問題。與回溯法進行對比。8實踐(2h)：實現(xiàn)采用優(yōu)先隊列式分支限界法解決裝載問題或0-1背包問題。第二部分：高級專題選講10第7章隨機化算法理論(4h)：簡介隨機數(shù)生成；概述三類隨機化算法：數(shù)值隨機化算法、舍伍德算法（用于避免最壞情況，如隨機化快速排序）、拉斯維加斯算法（保證正確性，時間隨機）、蒙特卡羅算法（時間確定，可能出錯）。不安排實驗，作為拓展視野。4專題選講理論(4h)：根據(jù)學生專業(yè)方向和興趣，從以下三章中選擇兩章進行概要性講解，重點講清問題、核心思想和經(jīng)典算法，不必深入所有細節(jié)。6選項A(網(wǎng)絡流)：講解最大流問題的Ford-Fulkerson方法及其核心增廣路思想（Edmonds-Karp算法）簡介最小割概念和應用。選項B(串算法)：講解KMP子串搜索算法的核心next數(shù)組構造思想簡介后綴數(shù)組的概念。選項C(數(shù)論算法)：講解歐幾里得算法及其擴展（求解模線性方程）簡介RSA公鑰加密算法原理。實踐(2h)：布置一道綜合性較強的題目，或引導學生閱讀經(jīng)典論文/代碼完成一份小報告。第三部分：復習與考核6課程總結與復習(4學時)：串講所有算法策略，對比總結不同策略的適用場景和優(yōu)缺點。解答學生疑問。期末考試(2學時)：理論筆試，考察對算法思想和分析能力的掌握。考核方式考核項目考核內容成績占比平時成績30%作業(yè)與實驗報告每次實驗后需提交代碼和實驗報告（含復雜度分析、運行結果、心得體會）。20%課堂出勤與參與包括提問、討論等。，10%期末考試（閉卷考試）主要考察對算法設計策略的理解、應用和復雜性分析能力。題型可包括：選擇題、填空題、簡答題、算法設計題、復雜性分析題、證明題等。，70%教學建議序號建議1理論聯(lián)系實際：切忌只講思路和偽代碼。鼓勵學生用熟悉的編程語言（C++/Java/Python）實現(xiàn)核心算法，加深理解。2對比教學：將不同策略用于解決同一問題（如0-1背包問題），引導學生對比分析其異同和優(yōu)劣。3啟發(fā)式教學：講解算法時，多采用“問題引入->初步想法->發(fā)現(xiàn)缺陷->優(yōu)化改進->得到最終算法”的流程，培養(yǎng)學生的算法思維。4利用在線評測（OJ）平臺：推薦學生使用LeetCode、PTA（拼題A）、HDUOJ等平臺練習相應題目，提升代碼實戰(zhàn)能力。5專題報