數(shù)據(jù)結(jié)構(gòu)課程大綱 PAGE5PAGE4 數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱《算法設(shè)計與分析》課程教學(xué)大綱（含課程思政）課程代碼：****課程負(fù)責(zé)人：****課程中文名稱：算法設(shè)計與分析課程英文名稱：DesignandAnalysisofAlgorithms課程類別：必修課程學(xué)分?jǐn)?shù)：2.5課程學(xué)時數(shù)：44/32授課對象：計算機(jī)科學(xué)與技術(shù)及相關(guān)專業(yè)本科本課程的前導(dǎo)課程：C/C++程序設(shè)計、離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)一、教學(xué)目的（黑體五號）本課程是計算機(jī)科學(xué)與技術(shù)專業(yè)的專業(yè)必修課。課程目標(biāo)如下：掌握計算機(jī)算法的基本概念和特性，了解計算機(jī)相關(guān)學(xué)科中算法分析與設(shè)計技巧的重要性，掌握算法時間復(fù)雜性的分析方法。掌握基本的算法設(shè)計策略，結(jié)合具體問題實例學(xué)習(xí)，重點(diǎn)掌握分治法、貪心法、動態(tài)規(guī)劃法、回溯法、分支限界法等常見的算法設(shè)計策略。通過理論學(xué)習(xí)和上機(jī)實踐的訓(xùn)練，具備靈活運(yùn)用所學(xué)解決實際應(yīng)用問題的能力。二、教學(xué)要求（黑體五號）通過課堂講授、課堂練習(xí)和討論互動、課后作業(yè)和上機(jī)實驗等教學(xué)手段，系統(tǒng)掌握計算機(jī)算法的有關(guān)概念和算法設(shè)計的基本策略。使學(xué)生掌握計算機(jī)算法的基本概念和特性，了解計算機(jī)相關(guān)學(xué)科中算法設(shè)計技術(shù)的重要性，掌握算法復(fù)雜性的分析方法。結(jié)合典型示例和實戰(zhàn)問題求解過程，使學(xué)生重點(diǎn)掌握窮舉法、歸納法、迭代法和遞歸法等基本算法設(shè)計方法以及分治法、蠻力法、回溯法、分支限界法、貪心法和動態(tài)規(guī)劃法等算法設(shè)計策略，了解計算復(fù)雜性基本理論，具備靈活運(yùn)用所學(xué)解決復(fù)雜工程應(yīng)用問題的能力。三、課程內(nèi)容與學(xué)時分配（黑體五號）主要內(nèi)容：1.概論：算法的概念和算法分析方法。教學(xué)重點(diǎn)：算法時空分析方法。教學(xué)難點(diǎn)：算法時間復(fù)雜度漸進(jìn)符號O、和。課程思政：好算法的時空平衡辯證唯物論，引導(dǎo)學(xué)生建立客觀、理性的辯證思維，樹立正確的人生觀，善于從政治上看問題，在大是大非面前保持政治清醒[2019年3月習(xí)近平總書記主持召開學(xué)校思想政治理論課教師座談會明確要求]。2.常用數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用：線性表、字符串、棧、隊列、雙端隊列、二叉樹、優(yōu)先隊列、樹和并查集、圖、二叉排序樹、平衡二叉樹和哈希表，設(shè)計好的數(shù)據(jù)結(jié)構(gòu)。教學(xué)重點(diǎn)：各種STL容器的應(yīng)用和設(shè)計好的數(shù)據(jù)結(jié)構(gòu)。教學(xué)難點(diǎn)：如何利用各種STL容器設(shè)計求解相關(guān)問題的算法設(shè)計，如何利用數(shù)據(jù)結(jié)構(gòu)容器高效地設(shè)計求解相關(guān)問題的算法。課程思政：數(shù)據(jù)結(jié)構(gòu)是算法的基本構(gòu)件，只有選擇好的數(shù)據(jù)結(jié)構(gòu)才能設(shè)計出求解問題的好算法社會是一個結(jié)構(gòu)化的有機(jī)系統(tǒng)，每個人是社會系統(tǒng)的一個構(gòu)件，引導(dǎo)學(xué)生要有家國情懷，心里裝著國家和民族，在黨和人民的偉大實踐中關(guān)注時代、關(guān)注社會，汲取養(yǎng)分、豐富思想，做一個有用于社會的人[2019年3月習(xí)近平總書記主持召開學(xué)校思想政治理論課教師座談會明確要求]。3.基本算法設(shè)計方法：窮舉法、歸納法、迭代法和遞歸法，遞推式計算。教學(xué)重點(diǎn)：各種基本算法設(shè)計方法求解問題的思路。教學(xué)難點(diǎn)：如何優(yōu)化窮舉法算法和利用歸納法建立求解問題的遞推關(guān)系，如何建立求解問題的遞歸模型。課程思政：歸納法求解問題的思路解決問題的是能力而不是碎片化的知識，能力是每個人自己總結(jié)歸納出來的特有的解決問題的一般方法，引導(dǎo)學(xué)生在學(xué)習(xí)中要善于總結(jié)歸納，在學(xué)習(xí)中做一些專題探討（見算法設(shè)計與分析教案）[工匠精神]。4.分治法：分治法概述，求解排序問題，求解查找問題，求解組合問題和快速冪算法。教學(xué)重點(diǎn)：分治法的基本策略和框架，快速排序和歸并排序，二分查找，查找假幣問題（三分查找），最大連續(xù)子序列和，求最近點(diǎn)對距離，求xn和An問題。教學(xué)難點(diǎn)：利用分治法求解問題的一般思路，快速排序、歸并排序和二分查找及其擴(kuò)展應(yīng)用。課程思政：分治法算法策略，大問題分解為若干小問題，由小問題的解合并為大問題的解每個小問題的解必須是正確的，這就是執(zhí)行力，通過朝鮮戰(zhàn)爭中中國人民志愿者英勇頑強(qiáng)的戰(zhàn)斗力示例向?qū)W生做愛國主義教育[愛國情懷]。5.回溯法：問題的解空間，回溯法框架，基于子集樹框架的問題求解和基于排列樹框架的問題求解。教學(xué)重點(diǎn)：簡單裝載問題，0/1背包問題，任務(wù)分配問題，貨郎擔(dān)問題。教學(xué)難點(diǎn)：利用回溯法求解問題的一般思路，回溯法中的剪支操作。課程思政：回溯法中的剪支操作以史為鑒，引導(dǎo)學(xué)生認(rèn)識從中華民族近代苦難歷史到中國特色社會主義道路是必然的選擇，是中華民族偉大復(fù)興是唯一正確之路[愛國情懷]。6.分支限界法：分支限界法概述，限界函數(shù)設(shè)計，廣度優(yōu)先搜索，隊列式分支限界法和優(yōu)先隊列式分支限界法。教學(xué)重點(diǎn)：各種基本廣度優(yōu)先搜索，圖的單源最短路徑，0/1背包問題，任務(wù)分配問題和貨郎擔(dān)問題。教學(xué)難點(diǎn)：利用分支限界法求解問題的一般思路，分支限界法中的限界函數(shù)設(shè)計。課程思政：分支限界法中限界函數(shù)設(shè)計人工智能中的啟發(fā)式算法設(shè)計，我國政府制定了《新一代人工智能發(fā)展規(guī)劃》，將人工智能上升到國家戰(zhàn)略層面，并提出人工智能產(chǎn)業(yè)要成為新的重要經(jīng)濟(jì)增長點(diǎn)，而且要在2030年達(dá)到世界領(lǐng)先水平，讓中國成為世界主要人工智能創(chuàng)新中心，為躋身創(chuàng)新型國家前列和經(jīng)濟(jì)強(qiáng)國奠定重要基礎(chǔ)。讓學(xué)生認(rèn)識人工智能的國家戰(zhàn)略，投身國家科技建設(shè)中[科技報國]。7.貪心法：貪心法原理和要點(diǎn)，貪心法框架，求解組合問題，求解圖問題，求解調(diào)度問題和哈夫曼編碼。教學(xué)重點(diǎn)：活動安排問題Ⅰ，背包問題，Prim算法、Kruskal算法和Dijkstra算法，不帶懲罰的調(diào)度問題和帶懲罰的調(diào)度問題。教學(xué)難點(diǎn)：利用貪心法求解問題的一般思路，如何在求解問題中選擇正確的貪心策略。課程思政：貪心法算法設(shè)計必須采用正確的貪心選擇策略引導(dǎo)學(xué)生認(rèn)識一個經(jīng)濟(jì)學(xué)問題即財富第3次分配。財富初次分配就是要讓那些有知識、善于創(chuàng)新并努力工作的人得到更多的勞務(wù)報酬，首先富裕起來；財富第二次分配就是政府利用稅收等手段來幫助弱勢群體，建立全面、系統(tǒng)、適度、公平和有效的社會保障體系；財富第三次分配是富人們在自愿的基礎(chǔ)上拿出自己的部分財富，幫助窮人改善生活、教育和醫(yī)療的條件[愛國情懷]。8.動態(tài)規(guī)劃：動態(tài)規(guī)劃原理和要點(diǎn)，一維動態(tài)規(guī)劃，二維動態(tài)規(guī)劃，三維動態(tài)規(guī)劃，字符串動態(tài)規(guī)劃，背包動態(tài)規(guī)劃，樹形動態(tài)規(guī)劃，區(qū)間動態(tài)規(guī)劃。教學(xué)重點(diǎn)：動態(tài)規(guī)劃原理和要點(diǎn)，一維動態(tài)規(guī)劃，二維動態(tài)規(guī)劃，三維動態(tài)規(guī)劃，背包動態(tài)規(guī)劃。教學(xué)難點(diǎn)：利用動態(tài)規(guī)劃求解問題的一般思路，動態(tài)規(guī)劃算法中的空間優(yōu)化。課程思政：動態(tài)規(guī)劃用于求最優(yōu)解，“規(guī)劃”本質(zhì)就是將求解過程分為若干階段，利用前面階段的最優(yōu)解求后面階段的最優(yōu)解中國的發(fā)展分為若干個五年計劃，新的五年計劃都是在前期總結(jié)的基礎(chǔ)上考慮國家發(fā)展和總目標(biāo)制定的，形成最優(yōu)社會發(fā)展方向，引導(dǎo)學(xué)生認(rèn)識社會主義制度和中國模式的優(yōu)越性[愛國情懷]。9.NP完全問題：P類、NP類和NP完全問題。教學(xué)重點(diǎn)：P類、NP類和NP完全問題的概念。教學(xué)難點(diǎn)：NP完全問題。課程思政：NP完全問題是目前已知最難的問題上海洋山深水港四期是全球領(lǐng)先、亞洲首個全自動化碼頭，集裝箱裝卸轉(zhuǎn)運(yùn)全部由智能設(shè)備完成，無人駕駛自動導(dǎo)引車，自動堆箱軌塔吊…，是美國九大港口的吞吐總量，占到目前全球港口年吞吐量的十分之一。其智能化程度之高讓不少外國網(wǎng)友驚嘆，“跟看科幻片似的”。數(shù)百臺車輛實現(xiàn)自動調(diào)度屬于NP完全問題，該港采用5G智慧解決方案。讓學(xué)生體會中國社會主義建設(shè)的自豪感[工匠精神，科技報國]。課程內(nèi)容與學(xué)時分配表（44學(xué)時）內(nèi)容學(xué)時1、概論22、常用數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用43、基本算法設(shè)計方法44、分治法65、回溯法66、分支限界法67、貪心法68、動態(tài)規(guī)劃89、NP完全問題2小計44課程內(nèi)容與學(xué)時分配表（32學(xué)時）—方案1內(nèi)容學(xué)時1、概論22、常用數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用23、基本算法設(shè)計方法44、分治法45、回溯法66、分支限界法47、貪心法48、動態(tài)規(guī)劃69、NP完全問題0小計32課程內(nèi)容與學(xué)時分配表（32學(xué)時）—方案2內(nèi)容學(xué)時1、概論22、常用數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用03、基本算法設(shè)計方法04、分治法65、回溯法66、分支限界法67、貪心法68、動態(tài)規(guī)劃69、NP完全問題0小計32四、教材與參考書（黑體五號）教材：算法設(shè)計與分析基礎(chǔ).李春葆等.北京：清華大學(xué)出版社，2022參考書：[1]算法導(dǎo)論.ThomasH.Cormen，CharlesE.Leiserson，RonaldL.Rivest，CliffordStein著.潘金貴，顧鐵成，李成法、葉懋譯.北京：機(jī)械工業(yè)出版社，2009[2]算法設(shè)計技巧與分析.AlsuwaiyelM.H.著，吳偉昶等譯.北京：電子工業(yè)出版社，2004[3]算法設(shè)計與分析.王紅梅.北京：清華大學(xué)出版社，2006[4]計算機(jī)算法設(shè)計與分析.王曉東.北京：電子工業(yè)出版社.2012[5]算法設(shè)計與分析基礎(chǔ)學(xué)習(xí)與上機(jī)指導(dǎo).李春葆等，清華大學(xué)出版社，2022五、考核方式（黑體五號）期末考試（60%），上機(jī)實驗（20%），作業(yè)（10%），其他（10%）《算法設(shè)計與分析實驗》課程教學(xué)大綱課程代碼：****課程負(fù)責(zé)人：****課程中文名稱：算法設(shè)計與分析實驗課程英文名稱：Algorithmdesignandanalysisexperiment課程類別：必修課程學(xué)分?jǐn)?shù)：0.5課程學(xué)時數(shù)：15～21授課對象：計算機(jī)科學(xué)與技術(shù)及相關(guān)專業(yè)本科本課程的前導(dǎo)課程：C/C++程序設(shè)計、離散數(shù)學(xué)、算法設(shè)計與分析一、教學(xué)介紹算法設(shè)計與分析實驗是算法設(shè)計與分析的配套課程，主要通過上機(jī)編程鞏固算法設(shè)計與分析的基本原理和方法，掌握數(shù)據(jù)組織和算法設(shè)計和實現(xiàn)技術(shù)，培養(yǎng)綜合運(yùn)用算法設(shè)計與分析策略高效解決問題的能力。主要窮舉法、歸納法、迭代法和遞歸法等基本算法設(shè)計方法以及分治法、蠻力法、回溯法、分支限界法、貪心法和動態(tài)規(guī)劃法等算法設(shè)計策略。二、教學(xué)目的算法設(shè)計與分析實驗課程的總目標(biāo)是培養(yǎng)學(xué)生能夠根據(jù)需要開展實驗研究，正確地描述數(shù)據(jù)和組織數(shù)據(jù)，并應(yīng)用數(shù)據(jù)處理方法，編寫程序，分析實驗結(jié)果以獲得合理有效的結(jié)論，具備解決復(fù)雜工程問題的能力。算法設(shè)計與分析實驗分為單機(jī)實驗和在線編程。單機(jī)實驗是在自己計算機(jī)或者實驗室計算機(jī)上完成，目的讓學(xué)生領(lǐng)會算法的原理、驗證算法的正確性和采用常用的算法策略求解問題。在線編程實驗是在LeetCode、POJ或者HDU在線編程平臺中完成，目的是培養(yǎng)學(xué)生研究問題、合理地選擇數(shù)據(jù)結(jié)構(gòu)和算法策略構(gòu)建解決方案，并分析比較各種方案優(yōu)劣的能力。三、實驗基本要求與方式1、基本要求課前：要求任課教師布置好實驗題目、實驗要求和實驗?zāi)康?，要求實驗教師為實驗?zhǔn)備好必須的設(shè)備和軟件；要求學(xué)生提前編寫完成實驗要求的程序代碼。課中：要求任課教師隨時解答學(xué)生提出的實驗問題，同時要注重啟發(fā)和引導(dǎo)學(xué)生，使學(xué)生養(yǎng)成獨(dú)立思考、解決問題的能力，檢查學(xué)生的實驗內(nèi)容；實驗教師要及時解決實驗設(shè)備可能出現(xiàn)的故障，保證實驗順利地進(jìn)行。學(xué)生則應(yīng)該按照實驗要求，認(rèn)真編寫和調(diào)試源代碼，完成實驗內(nèi)容。課后：提交實驗報告。2、實驗方式單機(jī)實驗題：輸入相應(yīng)的數(shù)據(jù)，通過檢測輸出結(jié)果，驗證是否實現(xiàn)了實驗的要求。在線編程題：在在線編程平臺提交代碼，查看提交結(jié)果，分析代碼運(yùn)行的時間和空間。四、實驗報告實驗報告按學(xué)院要求格式書寫，包含封面（含學(xué)號，姓名等），目錄，每個實驗的題目，解答思路，程序框架，源代碼，提交結(jié)果圖（在線編程題給出包含提交通過、運(yùn)行時間和空間的截屏圖），實驗體會（選）。五、實驗內(nèi)容與學(xué)時分配說明：所有實驗題的題目描述見《教材》，在線編程實驗題目見LeetCode、北京大學(xué)POJ和杭州電子科技大學(xué)HUD網(wǎng)站。實驗1：常用數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用學(xué)時數(shù)：0～3。任課教師根據(jù)學(xué)生情況在以下各種類型的實驗題目中選擇若干實驗題目。1.單機(jī)實驗題（1）高效地插入、刪除和查找（2）一種特殊的隊列（3）方塊操作2.在線編程題（1）LeetCode328—奇偶鏈表（2）LeetCode394—字符串解碼（3）LeetCode215—數(shù)組中的第k個最大元素（4）HDU1280—前m大的數(shù)（5）POJ2236—無線網(wǎng)絡(luò)實驗2：基本算法設(shè)計方法學(xué)時數(shù)：0～3。任課教師根據(jù)學(xué)生情況在以下各種類型的實驗題目中選擇若干實驗題目。1.單機(jī)實驗題（1）最長重復(fù)子串（2）求子矩陣元素和（3）求n階螺旋矩陣（4）驗證梵塔問題2.在線編程題（1）LeetCode344—反轉(zhuǎn)字符串（2）LeetCode206—反轉(zhuǎn)鏈表（3）LeetCode24—兩兩交換鏈表中的結(jié)點(diǎn)（4）LeetCode62—不同路徑（5）HDU1003—最大子序列和（6）HDU1143—三平鋪問題（7）POJ2231—奶牛的總音量（8）POJ1050—最大子矩形實驗3：分治法學(xué)時數(shù)：3。任課教師根據(jù)學(xué)生情況在以下各種類型的實驗題目中選擇若干實驗題目。1.單機(jī)實驗題（1）將一個整數(shù)數(shù)組劃分為兩個和差最大的子數(shù)組（2）四路歸并排序（3）查找假幣問題（4）求眾數(shù)（5）求漢諾塔Ⅱ（6）求Fibonacci數(shù)列2.在線編程題（1）LeetCode240—搜索二維矩陣II（2）LeetCode35—搜索插入位置（3）LeetCode33—搜索旋轉(zhuǎn)排序數(shù)組（4）LeetCode162—尋找峰值（5）HDU2141—能否找到X（6）HDU2199—解方程（7）HDU1040—排序（8）HDU1157—求中位數(shù)（9）HDU1007—套圈游戲（10）POJ2255—由二叉樹中序和先序序列產(chǎn)生后序序列（11）POJ1854—轉(zhuǎn)換為回文的交換次數(shù)（12）POJ1995—求表達(dá)式值實驗4：回溯法學(xué)時數(shù)：3。任課教師根據(jù)學(xué)生情況在以下各種類型的實驗題目中選擇若干實驗題目。1.單機(jī)實驗題（1）象棋算式（2）子集和（3）迷宮路徑（4）哈密頓回路2.在線編程題（1）LeetCode216—組合總和III（2）LeetCode39—組合總和（3）3.LeetCode131—分割回文串（4）HDU1027—第k小的排列（5）HDU2553—N皇后問題（6）HDU2616—?dú)⑺拦治铮?）POJ3187—向后數(shù)字和（8）POJ1321—棋盤問題（9）POJ2488—騎士游歷（10）POJ1040—運(yùn)輸問題（11）POJ1129—最少頻道數(shù)實驗5：分支限界法學(xué)時數(shù)：3。任課教師根據(jù)學(xué)生情況在以下各種類型的實驗題目中選擇若干實驗題目。1.單機(jī)實驗題（1）原始森林中解救A（2）裝載問題（3）最小機(jī)器重量設(shè)計問題Ⅰ（4）最小機(jī)器重量設(shè)計問題Ⅱ（5）貨郎擔(dān)問題2.在線編程題（1）LeetCode847—訪問所有結(jié)點(diǎn)的最短路徑（2）LeetCode1376—通知所有員工所需的時間（3）HDU1242—救援問題（4）HDU1548—奇怪的電梯（5）HDU1869—六度分離（6）HDU2425—徒步旅行（7）HDU1072—變形迷宮（8）POJ2312—坦克游戲?qū)嶒?：貪心法學(xué)時數(shù)：3。任課教師根據(jù)學(xué)生情況在以下各種類型的實驗題目中選擇若干實驗題目。1.單機(jī)實驗題（1）蓄欄保留問題（2）刪數(shù)問題（3）求所有最小生成樹（4）改進(jìn)Dijkstra算法（5）字符串的編碼和解碼2.在線編程題（1）LeetC