《算法設(shè)計(jì)與分析基礎(chǔ)》（Python語言描述）教案 李春葆 第1-5章 緒論-回溯法

教案教案PAGE5算法設(shè)計(jì)與分析基礎(chǔ)(Java)PAGE8算法設(shè)計(jì)與分析課程教案總課堂學(xué)時(shí)：44目前各個(gè)高校都存在算法設(shè)計(jì)與分析課程學(xué)時(shí)少、內(nèi)容多的情況，老師可以針對(duì)實(shí)際情況調(diào)整知識(shí)點(diǎn)，建議如下。（1）學(xué)時(shí)少于36：教學(xué)中主要講授五大算法策略，包括第1章，第4～8章，重點(diǎn)為各種經(jīng)典算法的設(shè)計(jì)思路，少講算法實(shí)現(xiàn)細(xì)節(jié)。（2）學(xué)時(shí)為36～52：教學(xué)中可以選擇部分經(jīng)典算法進(jìn)行講授，相關(guān)實(shí)戰(zhàn)題等可以引導(dǎo)學(xué)生自學(xué)，但要注意知識(shí)點(diǎn)的完整性，例如重點(diǎn)講授采用各種算法策略求解0/1背包問題，讓學(xué)生體會(huì)各種算法策略的要點(diǎn)。（3）學(xué)時(shí)多于52：教學(xué)中講授盡可能多的知識(shí)點(diǎn)，但要突出重點(diǎn)，同一個(gè)知識(shí)點(diǎn)重點(diǎn)講授兩個(gè)左右的經(jīng)典算法，可以適當(dāng)講授一些實(shí)戰(zhàn)題（特別是LeetCode題目），激發(fā)學(xué)生在線編程的興趣。建議：引導(dǎo)學(xué)生（或者學(xué)生小組）做一些專題研究，特別是利用LeetCode中相關(guān)題目做驗(yàn)證工作，例如：（1）求無序序列中第k小元素的算法設(shè)計(jì)。（2）二分查找算法及其應(yīng)用。（3）歸并排序算法及其應(yīng)用。（4）優(yōu)先隊(duì)列及其在算法設(shè)計(jì)中的應(yīng)用。（5）采用各種算法策略求0/1背包問題。（6）采用各種算法策略求貨郎擔(dān)問題。（7）采用各種算法策略求任務(wù)分配問題。（8）求冪集問題的各種算法設(shè)計(jì)。（9）求全排列問題的各種算法設(shè)計(jì)。（10）為什么采用貪心法求0/1背包問題是錯(cuò)誤的。（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é)時(shí)）課次：1（2學(xué)時(shí)）（1）對(duì)應(yīng)章：第1章概論。（2）教學(xué)內(nèi)容：算法的概念和算法時(shí)空分析。（3）教學(xué)方式：課堂講授。（4）教學(xué)重點(diǎn)：算法時(shí)空分析。（5）教學(xué)難點(diǎn)：算法時(shí)間復(fù)雜度漸進(jìn)符號(hào)O、和。（6）教學(xué)過程：以若干示例為基礎(chǔ)講授算法時(shí)間和空間分析方法。（7）作業(yè)：概論部分的若干問答題和算法分析題。第2章常用數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用（共4學(xué)時(shí)）課次：2（2學(xué)時(shí)）（1）對(duì)應(yīng)章：第2章常用數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用。（2）教學(xué)內(nèi)容：線性表、字符串、棧、雙端隊(duì)列、隊(duì)列、優(yōu)先隊(duì)列。（3）教學(xué)方式：課堂講授+自學(xué)。（4）教學(xué)重點(diǎn)：Python中列表、字符串、字典、集合、deque、heapq等數(shù)據(jù)類型的應(yīng)用。（5）教學(xué)難點(diǎn)：如何利用各種Python數(shù)據(jù)類型設(shè)計(jì)求解相關(guān)問題的算法。（6）教學(xué)過程：以若干示例為基礎(chǔ)講授數(shù)據(jù)結(jié)構(gòu)應(yīng)用算法設(shè)計(jì)。（7）作業(yè)：無。課次：3（2學(xué)時(shí)）（1）對(duì)應(yīng)章：第2章常用數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用。（2）教學(xué)內(nèi)容：二叉樹、圖、二叉排序樹、平衡二叉樹和哈希表，設(shè)計(jì)好的數(shù)據(jù)結(jié)構(gòu)。（3）教學(xué)方式：課堂講授+自學(xué)。（4）教學(xué)重點(diǎn)：TreeMap、TreeSet、HashMap和HashSet等數(shù)據(jù)結(jié)構(gòu)集合的應(yīng)用。（5）教學(xué)難點(diǎn)：Tree和Hash的應(yīng)用場(chǎng)合，如何利用數(shù)據(jù)結(jié)構(gòu)集合高效地設(shè)計(jì)求解相關(guān)問題的算法。（6）教學(xué)過程：以若干示例為基礎(chǔ)講授利用數(shù)據(jù)結(jié)構(gòu)求解問題的方法。由于時(shí)間限制，可以重點(diǎn)講授TreeMap和HashMap的相關(guān)示例，其他引導(dǎo)學(xué)生自學(xué)。（7）作業(yè)：本章若干問答題和算法設(shè)計(jì)題。（8）實(shí)驗(yàn)：根據(jù)學(xué)生層次選擇一些在線編程題目。第3章基本算法設(shè)計(jì)方法（共4學(xué)時(shí)）課次：4（2學(xué)時(shí)）（1）對(duì)應(yīng)章：第3章基本算法設(shè)計(jì)方法。（2）教學(xué)內(nèi)容：窮舉法、歸納法和迭代法。（3）教學(xué)方式：課堂講授+自學(xué)。（4）教學(xué)重點(diǎn)：窮舉法、歸納法和迭代法求解問題的思路。（5）教學(xué)難點(diǎn)：如何優(yōu)化窮舉法算法和利用歸納法建立求解問題的遞推關(guān)系。（6）教學(xué)過程：通過示例講授三種基本算法設(shè)計(jì)方法。由于時(shí)間限制，可以重點(diǎn)講授求最大連續(xù)子序列和多數(shù)元素示例，其他引導(dǎo)學(xué)生自學(xué)。（7）作業(yè)：無課次：5（2學(xué)時(shí)）（1）對(duì)應(yīng)章：第3章基本算法設(shè)計(jì)方法。（2）教學(xué)內(nèi)容：遞歸法和遞推式計(jì)算。（3）教學(xué)方式：課堂講授+自學(xué)。（4）教學(xué)重點(diǎn)：如何建立求解問題的遞歸模型。（5）教學(xué)難點(diǎn)：遞歸算法分析。（6）教學(xué)過程：通過示例講授遞歸算法設(shè)計(jì)方法及其時(shí)間復(fù)雜度分析。由于時(shí)間限制，可以重點(diǎn)講授求全排列示例，其他引導(dǎo)學(xué)生自學(xué)。（7）作業(yè)：本章若干問答題和算法設(shè)計(jì)題。（8）實(shí)驗(yàn)：根據(jù)學(xué)生層次選擇一些在線編程題目。第4章分治法（共6學(xué)時(shí)）課次：6（2學(xué)時(shí)）（1）對(duì)應(yīng)章：第4章分治法。（2）教學(xué)內(nèi)容：分治法概述，求解排序問題。（3）教學(xué)方式：課堂講授。（4）教學(xué)重點(diǎn)：分治法的基本策略和框架，快速排序和歸并排序。（5）教學(xué)難點(diǎn)：各種分治排序算法的應(yīng)用。（6）教學(xué)過程：通過示例講授分治法在排序問題中的應(yīng)用。（7）作業(yè)：無課次：7（2學(xué)時(shí)）（1）對(duì)應(yīng)章：第4章分治法。（2）教學(xué)內(nèi)容：求解查找問題。（3）教學(xué)方式：課堂講授+自學(xué)。（4）教學(xué)重點(diǎn)：二分查找，二分查找擴(kuò)展，查找假幣問題（三分查找）。（5）教學(xué)難點(diǎn)：各種分治查找算法的應(yīng)用。（6）教學(xué)過程：通過示例講授分治法在查找問題中的應(yīng)用。（7）作業(yè)：無課次：8（2學(xué)時(shí)）（1）對(duì)應(yīng)章：第4章分治法。（2）教學(xué)內(nèi)容：求解組合問題。（3）教學(xué)方式：課堂講授。（4）教學(xué)重點(diǎn)：最大子序和，多數(shù)元素，求最近點(diǎn)對(duì)距離。（5）教學(xué)難點(diǎn)：各種分治組合算法的應(yīng)用。（6）教學(xué)過程：通過示例講授分治法在組合問題中的應(yīng)用。（7）作業(yè)：本章若干問答題和算法設(shè)計(jì)題。（8）實(shí)驗(yàn)：根據(jù)學(xué)生層次選擇一些在線編程題目。第5章回溯法（共6學(xué)時(shí)）課次：9（2學(xué)時(shí)）（1）對(duì)應(yīng)章：第5章回溯法。（2）教學(xué)內(nèi)容：?jiǎn)栴}的解空間，回溯法框架，深度優(yōu)先搜索。（3）教學(xué)方式：課堂講授。（4）教學(xué)重點(diǎn)：解空間的概念，圖的深度優(yōu)先遍歷和回溯法的不同點(diǎn)。（5）教學(xué)難點(diǎn)：圖的深度優(yōu)先遍歷和回溯法的不同點(diǎn)。（6）教學(xué)過程：通過示例講授深度優(yōu)先搜索和回溯算法的執(zhí)行過程。（7）作業(yè)：無。課次：10（2學(xué)時(shí)）（1）對(duì)應(yīng)章：第5章回溯法。（2）教學(xué)內(nèi)容：基于子集樹框架的問題求解。（3）教學(xué)方式：課堂講授+自學(xué)。（4）教學(xué)重點(diǎn)：基于子集樹框架求解子集和問題，簡(jiǎn)單裝載問題，0/1背包問題，完全背包問題，圖的m著色問題，n皇后問題和任務(wù)分配問題。（5）教學(xué)難點(diǎn)：子集樹框架中的剪支操作。（6）教學(xué)過程：從子集和問題的左右剪支到0/1背包問題的左右剪支講授如何設(shè)計(jì)剪支操作。由于時(shí)間限制，簡(jiǎn)單裝載問題和n皇后問題引導(dǎo)學(xué)生自學(xué)。（7）作業(yè)：無。課次：11（2學(xué)時(shí)）（1）對(duì)應(yīng)章：第5章回溯法。（2）教學(xué)內(nèi)容：基于排列樹框架的問題求解。（3）教學(xué)方式：課堂講授。（4）教學(xué)重點(diǎn)：基于排列樹