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

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