算法設計與分析 教案學時分配 第1-9章 緒論-NP完全問題

算法設計與分析基礎第第1章概論PAGE8PAGE7算法設計與分析課程教案總課堂學時：44目前各個高校都存在算法設計與分析課程學時少、內(nèi)容多的情況，老師可以針對實際情況調(diào)整知識點，建議如下。（1）學時少于36：教學中主要講授五大算法策略，包括第1章，第4～8章，重點為各種經(jīng)典算法的設計思路，少講算法實現(xiàn)細節(jié)。（2）學時為36～52：教學中可以選擇部分經(jīng)典算法進行講授，相關實戰(zhàn)題等可以引導學生自學，但要注意知識點的完整性，例如重點講授采用各種算法策略求解0/1背包問題，讓學生體會各種算法策略的要點。（3）學時多于52：教學中講授盡可能多的知識點，但要突出重點，同一個知識點重點講授兩個左右的經(jīng)典算法，可以適當講授一些實戰(zhàn)題（特別是LeetCode題目），激發(fā)學生在線編程的興趣。建議：引導學生（或者學生小組）做一些專題研究，特別是利用LeetCode中相關題目做驗證工作，例如：（1）求無序序列中第k小元素的算法設計。（2）二分查找算法及其應用。（3）歸并排序算法及其應用。（4）優(yōu)先隊列及其在算法設計中的應用。（5）采用各種算法策略求0/1背包問題。（6）采用各種算法策略求貨郎擔問題。（7）采用各種算法策略求任務分配問題。（8）求冪集問題的各種算法設計。（9）求全排列問題的各種算法設計。（10）為什么采用貪心法求0/1背包問題是錯誤的。（11）基于子集樹框架的問題求解。（12）基于排列樹框架的問題求解。（13）廣度優(yōu)先算法及其應用。（14）利用剪支提高算法性能。（15）求最短路徑問題的研究（LeetCode網(wǎng)站有大量的類似應用題目）。（16）基于0/1背包問題的問題求解（LeetCode網(wǎng)站有大量的類似應用題目）。（17）基于完全背包問題的問題求解（如零錢兌換LeetCode332等）。第1章緒論（共2學時）課次：1（2學時）（1）對應章：第1章概論。（2）教學內(nèi)容：算法的概念和算法時空分析。（3）教學方式：課堂講授。（4）教學重點：算法時空分析。（5）教學難點：算法時間復雜度漸進符號O、和。（6）教學過程：以若干示例為基礎講授算法時間和空間分析方法。（7）作業(yè)：概論部分的若干問答題和算法分析題。第2章常用數(shù)據(jù)結(jié)構(gòu)及其應用（共4學時）課次：2（2學時）（1）對應章：第2章常用數(shù)據(jù)結(jié)構(gòu)及其應用。（2）教學內(nèi)容：線性表、字符串、棧、隊列、雙端隊列、二叉樹、優(yōu)先隊列、樹和并查集以及圖。（3）教學方式：課堂講授+自學。（4）教學重點：STL中vector、string、deque、stack、queue、priority_queue等數(shù)據(jù)結(jié)構(gòu)容器的應用。（5）教學難點：如何利用上述容器設計求解相關問題的算法設計。（6）教學過程：以若干示例為基礎講授數(shù)據(jù)結(jié)構(gòu)應用算法設計。由于時間限制，可以重點講授vector、stack和priority_queue等數(shù)據(jù)結(jié)構(gòu)容器和相關示例，其他引導學生自學。（7）作業(yè)：無。課次：3（2學時）（1）對應章：第2章常用數(shù)據(jù)結(jié)構(gòu)及其應用。（2）教學內(nèi)容：二叉排序樹、平衡二叉樹和哈希表，設計好的數(shù)據(jù)結(jié)構(gòu)。（3）教學方式：課堂講授+自學。（4）教學重點：set、map和unordered_map等數(shù)據(jù)結(jié)構(gòu)容器的應用。（5）教學難點：map和unordered_map的應用場合，如何利用數(shù)據(jù)結(jié)構(gòu)容器高效地設計求解相關問題的算法。（6）教學過程：以若干示例為基礎講授利用數(shù)據(jù)結(jié)構(gòu)求解問題的方法。由于時間限制，可以重點講授map和unordered_map以及設計好的數(shù)據(jù)結(jié)構(gòu)的相關示例，其他引導學生自學。（7）作業(yè)：本章若干問答題和算法設計題。（8）實驗：根據(jù)學生層次選擇本章若干隨機實驗題，可以適當選擇一些在線編程題目。第3章基本算法設計方法（共4學時）課次：4（2學時）（1）對應章：第3章基本算法設計方法。（2）教學內(nèi)容：窮舉法、歸納法和迭代法。（3）教學方式：課堂講授+自學。（4）教學重點：窮舉法、歸納法和迭代法求解問題的思路。（5）教學難點：如何優(yōu)化窮舉法算法和利用歸納法建立求解問題的遞推關系。（6）教學過程：通過示例講授三種基本算法設計方法。由于時間限制，可以重點講授求最大連續(xù)子序列和、樓梯問題和求冪集等示例，其他引導學生自學。（7）作業(yè)：無課次：5（2學時）（1）對應章：第3章基本算法設計方法。（2）教學內(nèi)容：遞歸法和遞推式計算。（3）教學方式：課堂講授+自學。（4）教學重點：如何建立求解問題的遞歸模型。（5）教學難點：遞歸算法分析。（6）教學過程：通過示例講授遞歸算法設計方法及其時間復雜度分析。由于時間限制，可以重點講授求全排列示例，其他引導學生自學。（7）作業(yè)：本章若干問答題和算法設計題。（8）實驗：根據(jù)學生層次選擇本章若干隨機實驗題，可以適當選擇一些在線編程題目。第4章分治法（共6學時）課次：6（2學時）（1）對應章：第4章分治法。（2）教學內(nèi)容：分治法概述，求解排序問題。（3）教學方式：課堂講授。（4）教學重點：分治法的基本策略和框架，快速排序和歸并排序。（5）教學難點：各種分治排序算法的應用。（6）教學過程：通過示例講授分治法在排序問題中的應用。（7）作業(yè)：無課次：7（2學時）（1）對應章：第4章分治法。（2）教學內(nèi)容：求解查找問題，求解組合問題。（3）教學方式：課堂講授+自學。（4）教學重點：二分查找，查找假幣問題（三分查找），最大連續(xù)子序列和，棋盤覆蓋問題。（5）教學難點：各種分治查找算法的應用。（6）教學過程：通過示例講授分治法在查找問題中的應用。由于時間限制，可以重點講授二分查找，查找假幣問題（三分查找）示例，其他引導學生自學。（7）作業(yè)：無課次：8（2學時）（1）對應章：第4章分治法。（2）教學內(nèi)容：求解組合問題，求xn和An問題。（3）教學方式：課堂講授。（4）教學重點：循環(huán)日程安排問題，求最近點對距離，求xn和An問題。（5）教學難點：各種分治組合算法的應用和快速冪算法。（6）教學過程：通過示例講授分治法在組合問題中的應用，及其快速冪算法的應用。（7）作業(yè)：本章若干問答題和算法設計題。（8）實驗：根據(jù)學生層次選擇本章若干隨機實驗題，可以適當選擇一些在線編程題目。第5章回溯法（共6學時）課次：9（2學時）（1）對應章：第5章回溯法。（2）教學內(nèi)容：問題的解空間，回溯法框架。（3）教學方式：課堂講授。（4）教學重點：解空間的兩種類型（子集樹和排列樹）及其框架。（5）教學難點：子集樹框架和排列樹框架。（6）教學過程：通過示例講授子集樹框架和排列樹框架執(zhí)行過程。（7）作業(yè)：無。課次：10（2學時）（1）對應章：第5章回溯法。（2）教學內(nèi)容：基于子集樹框架的問題求解。（3）教學方式：課堂講授+自學。（4）教學重點：基于子集樹框架求解子集和問題，簡單裝載問題，0/1背包問題，n皇后問題和任務分配問題。（5）教學難點：子集樹框架中的剪支操作。（6）教學過程：從子集和問題的左右剪支到0/1背包問題的左右剪支講授如何設計剪支操作。由于時間限制，簡單裝載問題和n皇后問題引導學生自學。（7）作業(yè)：無。課次：11（2學時）（1）對應章：第5章回溯法。（2）教學內(nèi)容：基于排列樹框架的問題求解。（3）教學方式：課堂講授。（4）教學重點：基于排列樹框架求解任務分配問題和貨郎擔問題。（5）教學難點：理解子集樹框架和排列樹框架的不同點，排列樹中的剪支操作。（6）教學過程：從排列樹框架求解任務分配問題與子集樹框架求解任務分配問題的對比講授兩種框架的不同點。（7）作業(yè)：本章若干問答題和算法設計題。（8）實驗：根據(jù)學生層次選擇本章若干隨機實驗題，可以適當選擇一些在線編程題目。第6章分支限界法（共6學時）課次：12（2學時）（1）對應章：第6章分支限界法。（2）教學內(nèi)容：分支限界法概述，限界函數(shù)設計，廣度優(yōu)先搜索。（3）教學方式：課堂講授。（4）教學重點：基本廣度優(yōu)先搜索，分層次的廣度優(yōu)先搜索和多起點廣度優(yōu)先搜索。（5）教學難點：如何利用廣度優(yōu)先搜索求解最優(yōu)解問題。（6）教學過程：通過抓牛問題（POJ3278）、推箱子（HDU1254）和腐爛的橘子（LeetCode994）3個實戰(zhàn)題講授廣度優(yōu)先搜索的應用。（7）作業(yè)：無課次：13（2學時）（1）對應章：第6章分支限界法。（2）教學內(nèi)容：隊列式分支限界法。（3）教學方式：課堂講授。（4）教學重點：隊列式分支限界法概述，圖的單源最短路徑和0/1背包問題。（5）教學難點：隊列式分支限界法中的限界函數(shù)設計。（6）教學過程：通過圖的單源最短路徑和0/1背包問題講授隊列式分支限界法的應用方法。（7）作業(yè)：無課次：14（2學時）（1）對應章：第6章分支限界法。（2）教學內(nèi)容：優(yōu)先隊列式分支限界法。（3）教學方式：課堂講授+自學。（4）教學重點：優(yōu)先隊列式分支限界法概述，圖的單源最短路徑，0/1背包問題，任務分配問題和貨郎擔問題。（5）教學難點：優(yōu)先隊列式分支限界法與隊列式分支限界法的不同點。（6）教學過程：通過圖的單源最短路徑和0/1背包問題講授優(yōu)先隊列式分支限界法的應用方法。由于時間限制，可以引導學生自學任務分配問題和貨郎擔問題。（7）作業(yè)：本章若干問答題和算法設計題。（8）實驗：根據(jù)學生層次選擇本章若干隨機實驗題，可以適當選擇一些在線編程題目。第7章貪心法（共6學時）課次：15（2學時）（1）對應章：第7章貪心法。（2）教學內(nèi)容：貪心法原理和要點，貪心法框架，求解組合問題。（3）教學方式：課堂講授。（4）教學重點：活動安排問題Ⅰ和背包問題。（5）教學難點：貪心法的正確性證明。（6）教學過程：通過活動安排問題Ⅰ和背包問題講授貪心法應用方法。（7）作業(yè)：無。課次：16（2學時）（1）對應章：第7章貪心法。（2）教學內(nèi)容：求解圖問題。（3）教學方式：課堂講授。（4）教學重點：Prim算法、Kruskal算法和Dijkstra算法。（5）教學難點：3個算法中如何體現(xiàn)貪心法的特點。（6）教學過程：通過3個圖算法講授貪心法應用方法。（7）作業(yè)：無。課次：17（2學時）（1）對應章：第7章貪心法。（2）教學內(nèi)容：求解調(diào)度問題和哈夫曼編碼。（3）教學方式：課堂講授。（4）教學重點：不帶懲罰的調(diào)度問題和帶懲罰的調(diào)度問題。（5）教學難點：帶懲罰的調(diào)度問題。（6）教學過程：通過調(diào)度問題求解講授貪心法應用方法。由于時間限制，可以簡要介紹哈夫曼編碼，引導學生自學。（7）作業(yè)：本章若干問答題和算法設計題。（8）實驗：根據(jù)學生層次選擇本章若干隨機實驗題，可以適當選擇一些在線編程題目。第8章動態(tài)規(guī)劃（共8學時）課次：18（2學時）（1）對應章：第8章動態(tài)規(guī)劃。（2）教學內(nèi)容：動態(tài)規(guī)劃原理和要點，一維動態(tài)規(guī)劃。（3）教學方式：課堂講授。（4）教學重點：最大連續(xù)子序列和，最長遞增子序列。（5）教學難點：動態(tài)規(guī)劃求解問題的性質(zhì)和步驟，如何設計動態(tài)規(guī)劃數(shù)組。（6）教學過程：通過最大連續(xù)子序列和以及最長遞增子序列講授動態(tài)規(guī)劃算法設計方法。（7）作業(yè)：無。課次：19（2學時）（1）對應章：第8章動態(tài)規(guī)劃。（2）教學內(nèi)容：二維動態(tài)規(guī)劃，三維動態(tài)規(guī)劃。（3）教學方式：課堂講授。（4）教學重點：三角形最小路徑和，F(xiàn)loyd算法。（5）教學難點：動態(tài)規(guī)劃算法中的空間優(yōu)化。（6）教學過程：通過三角形最小路徑和講授如何優(yōu)化動態(tài)規(guī)劃數(shù)組空間。（7）作業(yè)：無。課次：20（2學時）（1）對應章：第8章動態(tài)規(guī)劃。（2）教學內(nèi)容：字符串動態(tài)規(guī)劃，背包動態(tài)規(guī)劃。（3）教學方式：課堂講授+自學。（4）教學重點：最長公共子序列，編輯距離，0/1背包問題，完全背包問題。（5）教學難點：動態(tài)規(guī)劃算法中的空間優(yōu)化和動態(tài)規(guī)劃數(shù)組的計算順序。（6）教學過程：從0/1背包問題到完全背包問題講授動態(tài)規(guī)劃數(shù)組的計算順序。由于時間限制，字符串動態(tài)規(guī)劃實際上是二維動態(tài)規(guī)劃的應用，這部分可以少講。（7）作業(yè)：無。課次：21（2學時）（1）對應章：第8章動態(tài)規(guī)劃。（2）教學內(nèi)容：樹形動態(tài)規(guī)劃，區(qū)間動態(tài)規(guī)劃。（3）教學方式：課堂講授+自學。（4）教學重點：慶祝晚會（HDU1520），找礦（LeetCode337），戳氣球（LeetCode312），最長回文子串（LeetCode5）。（5）教學難點：樹形和區(qū)間動態(tài)規(guī)劃的基本原理。（6）教學過程：通過慶祝晚會（HDU1520）和戳氣球（