算法設(shè)計與分析 教案全套 田小霞

PAGE4PAGE5教師姓名：***職稱：TIME\@"yyyy/M/d"2024/8/5教案學(xué)年第學(xué)期教師所在單位課程名稱算法設(shè)計與分析專業(yè)、年級、班級主講教師教案編寫說明教案又稱課時授課計劃，是任課教師的教學(xué)實施方案。任課教師應(yīng)根據(jù)專業(yè)的培養(yǎng)方案，緊扣教學(xué)大綱，認(rèn)真分析教學(xué)內(nèi)容，切合學(xué)生實際，提前編寫設(shè)計好每門課程每個章、節(jié)或主題的全部教學(xué)活動。教案編寫說明如下：1、編號：按施教的順序標(biāo)明序號（每次課一個序號）。2、教學(xué)時數(shù)：是指每次課的教學(xué)時數(shù)。3、教學(xué)課型表示所授課程的類型，請在理論課、實驗課、習(xí)題課、實踐課及其它欄內(nèi)選擇打“√”。4、教學(xué)內(nèi)容：標(biāo)明章、節(jié)或主題。5、教學(xué)目的要求。6、教學(xué)重點、難點。7、教學(xué)方式和手段。8、教學(xué)過程（含復(fù)習(xí)舊課、引入新課、組織教學(xué)、啟發(fā)思維等）。將授課的內(nèi)容按邏輯層次，有序設(shè)計編排。本部分不同專業(yè)的授課可有自己的特色。9、討論、思考題和作業(yè)。10、參考資料：列出參考書籍、有關(guān)資料。11、日期的填寫系指本次課授課的時間。授課教案應(yīng)根據(jù)專業(yè)技術(shù)領(lǐng)域發(fā)展、教學(xué)要求變化、學(xué)生實際水平，以及教師以往教學(xué)的課后小結(jié)、批注等進行補充、修改或重寫，以保持教學(xué)內(nèi)容的先進性和適用性。請妥善保存各階段的教案，并配合好學(xué)院的教學(xué)檢查和歸檔等工作。

編號：1課時安排：2學(xué)時教學(xué)課型：理論課實驗課習(xí)題課□實踐課□其它□教學(xué)內(nèi)容（教學(xué)章、節(jié)或主題）：第一章算法基礎(chǔ)教學(xué)目的要求（分知識、能力和素質(zhì)三維目標(biāo)）：知識：理解算法的概念、特性；掌握算法在最壞情況、最好情況和平均情況下的計算復(fù)雜性概念；能力：掌握算法復(fù)雜性的漸近性態(tài)的數(shù)學(xué)表述和算法復(fù)雜度計算；素養(yǎng)：培養(yǎng)學(xué)生的家國情懷和團隊協(xié)作。教學(xué)重點、難點：重點：算法的概念、算法的時間復(fù)雜性、算法復(fù)雜性的漸近性態(tài)的數(shù)學(xué)表述以及遞歸的概念。通過講解、舉例方法、課堂練習(xí)。難點：算法復(fù)雜性與求算法復(fù)雜度通過講解、舉例、提問與引導(dǎo)方法。課程思政元素：愛崗敬業(yè)、家國情懷，如Tiktok推薦算法和大數(shù)據(jù)殺熟。教學(xué)方式和手段：教學(xué)方式：講授、討論、案例分析等；教學(xué)手段：學(xué)習(xí)通的搶答，分組任務(wù)、主題討論等；擬定的教學(xué)方法和手段要能有效地調(diào)動學(xué)生的學(xué)習(xí)積極性，促進學(xué)生的積極思考，激發(fā)學(xué)生的潛能教學(xué)過程：提問算法是什么，算法具有什么特性，如何定義算法？主題討論算法之美和之惡。講授算法的復(fù)雜性，主要包括時間復(fù)雜性與空間復(fù)雜性。講授最壞情況、最好情況與平均情況的時間復(fù)雜性。講授算法復(fù)雜性在漸近意義下、、，并通過具體例子說明。講授遞歸和非遞歸算法復(fù)雜度分析方法。討論、思考題、作業(yè)：1.主題討論算法之美和之惡。2.分組任務(wù)推薦算法講解報告；3.作業(yè)。實驗報告：排序問題的程序運行時長與問題規(guī)模大小關(guān)系。參考資料：競賽網(wǎng)站：1.PTA輔助實踐平臺；2.韓師OJ平臺。編號：2課時安排：6學(xué)時教學(xué)課型：理論課實驗課習(xí)題課□實踐課□其它□教學(xué)內(nèi)容（教學(xué)章、節(jié)或主題）：第二章遞歸和分治法教學(xué)目的要求（分知識、能力和素質(zhì)三維目標(biāo)）：知識：理解遞歸、分治的設(shè)計思想和適用條件；理解分治法的算法復(fù)雜度分析；能力：運用分治法策略和計算分治法的算法復(fù)雜度；素養(yǎng)：培養(yǎng)學(xué)生的科學(xué)思維，激發(fā)創(chuàng)新能力。教學(xué)重點、難點：重點：分治的設(shè)計思想；分治法的適用條件。通過講解、舉例方法、課堂練習(xí)。難點：分治法的算法復(fù)雜度分析。通過講解、舉例、主題討論、隨堂練習(xí)、問卷調(diào)查。課程思政元素：自強不息、積極探索、科學(xué)思維。教學(xué)方式和手段：教學(xué)方式：講授、討論、案例分析等；教學(xué)手段：學(xué)習(xí)通的搶答，分組任務(wù)、主題討論等；擬定的教學(xué)方法和手段要能有效地調(diào)動學(xué)生的學(xué)習(xí)積極性，促進學(xué)生的積極思考，激發(fā)學(xué)生的潛能教學(xué)過程：通過課堂甜點的趣味問題(拿牌)，引導(dǎo)學(xué)生如何求解問題。通過課堂甜點（找假幣）引入分治法，講解分治法算法的策略思想和適用條件。講解實例及練習(xí)，視頻實列有：二分搜索、合并排序、快速排序、棋盤覆蓋、逆序?qū)?、快速冪。講解主遞推公式。討論、思考題、作業(yè)：1.逆序?qū)υ趫D像處理中的應(yīng)用。2.快速排序復(fù)雜度的計算；3.作業(yè)。實驗報告：二維數(shù)組中查找特定元素，迷宮招駙馬。參考資料：競賽網(wǎng)站：1.PTA輔助實踐平臺；2.韓師OJ平臺。此部分內(nèi)容基礎(chǔ)知識可參考同濟大學(xué)《高等代數(shù)》。

編號：3課時安排：4學(xué)時教學(xué)課型：理論課實驗課習(xí)題課□實踐課□其它□教學(xué)內(nèi)容（教學(xué)章、節(jié)或主題）：第四章貪心算法教學(xué)目的要求（分知識、能力和素質(zhì)三維目標(biāo)）：知識和能力：理解貪心算法的設(shè)計思想和特性；理解貪心算法最優(yōu)選擇和最優(yōu)子結(jié)構(gòu)性；掌握貪心算法的一般步驟；預(yù)期達到的效果：能夠通過編寫代碼運用貪心算法解決特定問題；教學(xué)重點、難點：重點：貪心算法的概念；貪心算法的基本要素。通過講解、舉例方法、課堂練習(xí)。難點：理解貪心算法與動態(tài)規(guī)劃算法的差異通過講解、舉例、主題討論、隨堂練習(xí)。課程思政元素：科學(xué)思維、實事求是。教學(xué)方式和手段：教學(xué)方式：講授、討論、案例分析等；教學(xué)手段：學(xué)習(xí)通的搶答，分組任務(wù)、主題討論等；擬定的教學(xué)方法和手段要能有效地調(diào)動學(xué)生的學(xué)習(xí)積極性，促進學(xué)生的積極思考，激發(fā)學(xué)生的潛能教學(xué)過程：1.通過課堂趣味問題(硬幣兌換)，引導(dǎo)學(xué)生理解求解目標(biāo)，鼓勵學(xué)生利用貪心探索求解。2.講解貪心算法的策略思想和基本要素。3.通過0/1背包理解動態(tài)規(guī)劃與貪心算法區(qū)別與聯(lián)系。4.講解實例及練習(xí)，實例有活動安排問題、最優(yōu)裝載問題、哈夫曼編碼、單源最短路徑、最小生成樹，其中視頻有：韓山師范學(xué)院公開課（貪心算法）和最小生成樹。討論、思考題、作業(yè)：1.主題討論人生的奮斗目標(biāo)。2.分組任務(wù)講解競賽題目；3.作業(yè)。參考資料：競賽網(wǎng)站：1.PTA輔助實踐平臺；2.韓師OJ平臺。此部分內(nèi)容基礎(chǔ)知識可參考《數(shù)據(jù)結(jié)構(gòu)》。后記：教學(xué)過程應(yīng)提供更多展示視頻。編號：4課時安排：6學(xué)時教學(xué)課型：理論課實驗課習(xí)題課□實踐課□其它□教學(xué)內(nèi)容（教學(xué)章、節(jié)或主題）：第五章回溯法教學(xué)目的要求（分知識、能力和素質(zhì)三維目標(biāo)）：知識：理解回溯法的深度優(yōu)先搜索策略；理解算法的剪枝函數(shù)；能力：掌握用回溯法解題的算法框架；素養(yǎng)：培養(yǎng)學(xué)生的家國情懷和團隊協(xié)作。教學(xué)重點、難點：重點：回溯法的深度優(yōu)先搜索策略和框架；子集樹和排列樹。通過講解、舉例方法、課堂練習(xí)。難點：回溯的剪枝和限制函數(shù)。通過講解、舉例、主題討論。課程思政元素：崇尚科學(xué)、探索精神、勇于創(chuàng)新。教學(xué)方式和手段：教學(xué)方式：講授、討論、案例分析等；教學(xué)手段：學(xué)習(xí)通的搶答，分組任務(wù)、主題討論等；擬定的教學(xué)方法和手段要能有效地調(diào)動學(xué)生的學(xué)習(xí)積極性，促進學(xué)生的積極思考，激發(fā)學(xué)生的潛能教學(xué)過程：1.通過趣味問題(0-1背包和TSP背包)，引導(dǎo)學(xué)生理解子集樹和排列樹，鼓勵學(xué)生利用深度優(yōu)先探索求解，講解剪枝函數(shù)、回溯法解題步驟。2.講解回溯法的策略思想。講解在解空間樹中如何最快尋找最優(yōu)解。3.講解實例及練習(xí)，實例有0-1背包、最優(yōu)裝載問題、TSP、連續(xù)郵資，其中視頻有：回溯法的策略思想和N皇后。討論、思考題、作業(yè)：1.主題討論萬能神奇-暴力求解。2.作業(yè)。實驗報告：鄉(xiāng)村旅游規(guī)劃問題和0-1背包問題。參考資料：競賽網(wǎng)站：1.PTA輔助實踐平臺；2.韓師OJ平臺。編號：5課時安排：4學(xué)時教學(xué)課型：理論課實驗課習(xí)題課□實踐課□其它□教學(xué)內(nèi)容（教學(xué)章、節(jié)或主題）：第六章分支限界教學(xué)目的要求（分知識、能力和素質(zhì)三維目標(biāo)）：知識：理解分支限界的寬度優(yōu)先搜索策略；理解算法的限界函數(shù)；掌握用分支限界解題的算法框架。

能力：運用分支限界解題的算法框架求解問題；素養(yǎng)：培養(yǎng)學(xué)生的家國情懷和團隊協(xié)作。教學(xué)重點、難點：重點：分支限界的算法策略；分支限界算法的寬度優(yōu)先和限界函數(shù)；FIFO隊列和優(yōu)先級隊列。難點：分支限界法的剪枝搜索策略。通過講解、舉例、主題討論。課程思政元素：集思廣益、擇優(yōu)執(zhí)行。教學(xué)方式和手段：教學(xué)方式：講授、討論、案例分析等；教學(xué)手段：學(xué)習(xí)通的搶答，分組任務(wù)、主題討論等；擬定的教學(xué)方法和手段要能有效地調(diào)動學(xué)生的學(xué)習(xí)積極性，促進學(xué)生的積極思考，激發(fā)學(xué)生的潛能教學(xué)過程：1.通過趣味問題(0-1背包)，引導(dǎo)學(xué)生理解FIFO（先進先出）隊列和活節(jié)點擴展方式，鼓勵學(xué)生利用廣度優(yōu)先探索求解，講解限界函數(shù)和FIFO解題步驟。2.通過問題(TSP)，引導(dǎo)學(xué)生理解優(yōu)先級隊列和活節(jié)點擴展方式，鼓勵學(xué)生利用廣度優(yōu)先探索求解，講解限界函數(shù)和優(yōu)先級隊列的解題步驟。3.講解分支限界的策略思想。講解在解空間樹中如何最快尋找最優(yōu)解。4.講解實例及練習(xí)，實例有0-1背包、最優(yōu)裝載問題、TSP、單源最短路徑，其中視頻有：分支限界算法的課堂實錄。討論、思考題、作業(yè)：1.分組任務(wù)錄制賽題求解過程；2.作業(yè)。實驗報告：中國旅行商問題或者物流路徑選擇。參考資料：競賽網(wǎng)站：1.PTA輔助實踐平臺；2.韓師OJ平臺。編號：6課時安排：6學(xué)時教學(xué)課型：理論課實驗課習(xí)題課□實踐課□其它□教學(xué)內(nèi)容（教學(xué)章、節(jié)或主題）：第三章動態(tài)規(guī)劃教學(xué)目的要求（分知識、能力和素質(zhì)三維目標(biāo)）：知識：理解動態(tài)規(guī)劃的設(shè)計思想和特性；理解動態(tài)規(guī)劃子問題重疊性和最優(yōu)性；能力：掌握動態(tài)規(guī)劃求解步驟；素養(yǎng)：培養(yǎng)學(xué)生的科學(xué)思維和精益求精，激發(fā)創(chuàng)新能力。教學(xué)重點、難點：重點：動態(tài)規(guī)劃基本概念；動態(tài)規(guī)劃問題的特征。通過講解、舉例方法、課堂練習(xí)。難點：動態(tài)規(guī)劃的基本步驟。通過講解、舉例、主題討論、隨堂練習(xí)。課程思政元素：-創(chuàng)新性思維，鼓勵學(xué)生探索求解，從底向上解決大問題。教學(xué)方式和手段：教學(xué)方式：講授、討論、案例分析等；教學(xué)手段：學(xué)習(xí)通的搶答，分組任務(wù)、主題討論等；擬定的教學(xué)方法和手段要能有效地調(diào)動學(xué)生的學(xué)習(xí)積極性，促進學(xué)生的積極思考，激發(fā)學(xué)生的潛能教學(xué)過程：通過走向升旗臺問題，引導(dǎo)學(xué)生理解大問題分割子問題和子問題不獨立，鼓勵學(xué)生探索求解；通過數(shù)塔引入動態(tài)規(guī)劃法，講解動態(tài)規(guī)劃的算法策略思想和適用條件；通過0-1背包加深對動態(tài)規(guī)劃算法的理解；講解實例及練習(xí)，實例有石子合并、最長公共子序列、背包問題(KnapsackProblem)、其中視頻實列有：最長公共子序列和割繩子（算法工程師面試題）。討論、思考題、作業(yè)：1.動態(tài)規(guī)劃與分治法的差異。3.作業(yè)。實驗報告：背包問題，石子合并。參考資料：競賽網(wǎng)站：1.PTA輔助實踐平臺；2.韓師OJ平臺。編號：7課時安排：4學(xué)時教學(xué)課型：理論課實驗課習(xí)題課□實踐課□其它□教學(xué)內(nèi)容（教學(xué)章、節(jié)或主題）：第七章智能算法教學(xué)目的要求（分知識、能力和素質(zhì)三維目標(biāo)）：知識和能力：理解粒子群算法、模擬退火算法和禁忌搜索算法的設(shè)計思想和特性；理解智能算法的調(diào)優(yōu)方式；掌握粒子群算法、模擬退火算法和禁忌搜索算法的一般設(shè)計步驟。預(yù)期達到的效果：能夠?qū)μ囟ǖ膯栴}編寫粒子群算法、模擬退火算法和禁忌搜索算法的代碼。教學(xué)重點、難點：粒子群算法、模擬退火算法和禁忌搜索算法的基本原理；粒子群算法、模擬退火算法和禁忌搜索算法的參數(shù)設(shè)置。課程思政元素：探索未知、自我突破。教學(xué)方式和手段：教學(xué)方式：講授、討論、案例分析等；教學(xué)手段：多媒體教學(xué)設(shè)備，學(xué)習(xí)軟件如超星學(xué)習(xí)通，學(xué)習(xí)通的搶答，分組任務(wù)、主題討論等；擬定的教學(xué)方法和手段