《算法設(shè)計(jì)與分析》教學(xué)大綱

《算法設(shè)計(jì)與分析》教學(xué)大綱適用范圍：202X版本科人才培養(yǎng)方案課程代碼：08140431課程性質(zhì)：專業(yè)選修課程學(xué)分：4學(xué)分學(xué)時(shí)：64學(xué)時(shí)（理論48學(xué)時(shí)，實(shí)驗(yàn)16學(xué)時(shí)）先修課程：數(shù)據(jù)結(jié)構(gòu)后續(xù)課程：無適用專業(yè)：數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)、數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)（專升本）開課單位：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院一、課程說明《算法設(shè)計(jì)與分析》是數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)專業(yè)的專業(yè)選修課程。課程主要講授算法概述，貪心算法，遞歸與分治，動(dòng)態(tài)規(guī)劃，回溯算法，分支界限法，隨機(jī)化算法和NP完全理論8個(gè)章節(jié)的內(nèi)容。本課程主要用來培養(yǎng)學(xué)生的抽象能力、計(jì)算思維解能力、應(yīng)用能力和高效程序設(shè)計(jì)能力，藉以增進(jìn)學(xué)生的理解、分析、組織以及推理能力。通過本課程的學(xué)習(xí)，學(xué)生應(yīng)達(dá)到理解算法設(shè)計(jì)的主要思想，能夠應(yīng)用典型的算法解決問題，并為后續(xù)課程和進(jìn)一步深造打下堅(jiān)實(shí)基礎(chǔ)。本課程需要守好種好思想教育責(zé)任田，使課程與思想政治理論課同向同行，形成協(xié)同效應(yīng)。二、課程目標(biāo)通過本課程的學(xué)習(xí)，使學(xué)生達(dá)到如下目標(biāo)：課程目標(biāo)1：掌握算法的設(shè)計(jì)步驟和和復(fù)雜度分析，針對(duì)特定問題，能夠合理分析問題并建立數(shù)學(xué)模型；針對(duì)特定解決方案，能夠驗(yàn)證方案的合理性，并進(jìn)行復(fù)雜度分析，改進(jìn)方案的不足。培養(yǎng)學(xué)生分析問題的能力，引導(dǎo)學(xué)生獨(dú)立思考解決問題，促進(jìn)學(xué)生的個(gè)性化發(fā)展和提升。課程目標(biāo)2：理解貪心算法，遞歸與分治，動(dòng)態(tài)規(guī)劃，回溯算法，分支界限法算法的思想和原理，在實(shí)際開發(fā)中，能夠選擇相應(yīng)的數(shù)據(jù)結(jié)構(gòu)和算法解決程序設(shè)計(jì)中的難題。課程目標(biāo)3：針對(duì)計(jì)算機(jī)復(fù)雜工程問題，能夠基于算法設(shè)計(jì)與分析方法，通過調(diào)研和分析，設(shè)計(jì)合適的研究方案。三、課程目標(biāo)與畢業(yè)要求《算法設(shè)計(jì)與分析》課程教學(xué)目標(biāo)對(duì)數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)專業(yè)的畢業(yè)要求的支撐見表1。表1課程教學(xué)目標(biāo)與畢業(yè)要求關(guān)系畢業(yè)要求指標(biāo)點(diǎn)課程目標(biāo)支撐強(qiáng)度2．問題分析2.3能運(yùn)用數(shù)學(xué)、自然科學(xué)和數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)工程科學(xué)基本原理，分析和驗(yàn)證解決方案的合理性，并能夠掌握解決方案優(yōu)化方法。課程目標(biāo)1：掌握算法的設(shè)計(jì)步驟和和復(fù)雜度分析，針對(duì)特定問題，能夠合理分析問題并建立數(shù)學(xué)模型；針對(duì)特定解決方案，能夠驗(yàn)證方案的合理性，并進(jìn)行復(fù)雜度分析，改進(jìn)方案的不足。培養(yǎng)學(xué)生分析問題的能力，引導(dǎo)學(xué)生獨(dú)立思考解決問題，促進(jìn)學(xué)生的個(gè)性化發(fā)展和提升。H3．設(shè)計(jì)/開發(fā)解決方案3.1能夠針對(duì)大數(shù)據(jù)應(yīng)用系統(tǒng)設(shè)計(jì)與開發(fā)滿足特定需求的模塊或算法。課程目標(biāo)2：理解貪心算法，遞歸與分治，動(dòng)態(tài)規(guī)劃，回溯算法，分支界限法算法的思想和原理，在實(shí)際開發(fā)中，能夠選擇相應(yīng)的數(shù)據(jù)結(jié)構(gòu)和算法解決程序設(shè)計(jì)中的難題。H4．研究4.2能夠基于科學(xué)原理并采用科學(xué)方法對(duì)數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)領(lǐng)域相關(guān)問題選擇研究路線，并設(shè)計(jì)實(shí)驗(yàn)方案。課程目標(biāo)3：針對(duì)計(jì)算機(jī)復(fù)雜工程問題，能夠基于算法設(shè)計(jì)與分析方法，通過調(diào)研和分析，設(shè)計(jì)合適的研究方案。H注：表中“H（高）、M（中）”表示課程與相關(guān)畢業(yè)要求的關(guān)聯(lián)度。四、教學(xué)內(nèi)容、基本要求與學(xué)時(shí)分配1.理論部分理論部分的教學(xué)內(nèi)容、基本要求與學(xué)時(shí)分配見表2。表2教學(xué)內(nèi)容、基本要求與學(xué)時(shí)分配教學(xué)內(nèi)容教學(xué)要求，教學(xué)重點(diǎn)難點(diǎn)理論學(xué)時(shí)實(shí)驗(yàn)學(xué)時(shí)對(duì)應(yīng)的課程目標(biāo)1.算法概述1.1算法的特征；1.2算法的描述方式；1.3算法設(shè)計(jì)的一般過程；1.4算法分析；1.5遞推方程求解方法。教學(xué)要求：（1）理解算法與程序的關(guān)系以及與數(shù)據(jù)結(jié)構(gòu)的關(guān)系；（2）能夠抽象表達(dá)算法；（3）掌握定量估計(jì)算法的復(fù)雜度的方法。重點(diǎn)：算法表達(dá)的抽象機(jī)制，描述算法和復(fù)雜度分析。難點(diǎn)：將具體程序抽象為算法并對(duì)算法進(jìn)行復(fù)雜度分析。401、2、32.遞歸和分治2.1遞歸與分治法的基本思想與概念；2.2-2.4二分查找，選第二大元素，循環(huán)賽日程表；2.5-2.7合并排序，快速排序和線性時(shí)間選擇。教學(xué)要求：(1)掌握遞歸和分治的基本思想和原理；（2）二分查找，選第二大元素，循環(huán)賽日程表；（3）掌握合并排序，快速排序，在快速排序基礎(chǔ)上理解線性時(shí)間選擇的實(shí)現(xiàn)原理。重點(diǎn)：分治法思想與基本概念的掌握。難點(diǎn)：靈活利用分治和遞歸算法進(jìn)行二分查找，合并排序，快速排序。841、2、33.動(dòng)態(tài)規(guī)劃3.1-3.2動(dòng)態(tài)規(guī)劃的基本思想,矩陣連乘；3.3-3.5凸多邊形最優(yōu)三角剖分，最長(zhǎng)公共子序列，加工順序；3.6-3.7最優(yōu)二叉樹搜索，0/1背包問題。教學(xué)要求：（1）掌握動(dòng)態(tài)規(guī)劃的基本思想；（2）熟練應(yīng)用動(dòng)態(tài)規(guī)劃求解實(shí)際問題；（3）掌握最長(zhǎng)公共子序列，0/1背包問題與最優(yōu)二叉樹搜索；重點(diǎn)：動(dòng)態(tài)規(guī)劃基本思想以及與分治法的聯(lián)系與區(qū)別。難點(diǎn)：最長(zhǎng)公共子序列，0/1背包問題與最優(yōu)二叉樹搜索。841、2、34.貪心算法4.1-4.2貪心算法的基本概念，活動(dòng)安排問題；4.3-4.6最短路徑算法，哈夫曼編碼；4.8最小生成樹（Prim和Kruskal算法），背包問題。教學(xué)要求：（1）理解貪心算法的基本概念與思想；（2）熟練應(yīng)用貪心算法解決最優(yōu)裝載問題，哈夫曼樹和最短路徑問題；（3）理解最小生成樹的定義，以及兩種算法的原理。重點(diǎn)：掌握貪心算法的基本概念。難點(diǎn)：最短路徑算法和最小生成樹。641、2、35.回溯法5.1-5.2回溯法的基本概念，典型的解空間結(jié)構(gòu)；5.3-5.4子集樹問題：0-1背包和最大團(tuán)；5.5-5.6排列樹：批處理作業(yè)調(diào)度和旅行商問題；5.7-5.8滿m叉樹：圖的m著色問題和最小質(zhì)量機(jī)器設(shè)計(jì)問題。教學(xué)要求：（1）掌握回溯法的基本概念，熟練應(yīng)用回溯法解決實(shí)際問題；（2）能夠?qū)唧w問題進(jìn)行分析研究得到問題的解空間結(jié)構(gòu)，進(jìn)而設(shè)計(jì)實(shí)驗(yàn)方案；（3）了解回溯法的效率。重點(diǎn)：回溯法的基本概念，n后問題，旅行商問題，回溯法效率分析。難點(diǎn)：n后問題，旅行商問題，圖的m著色問題。621、2、36.分支限界法6.1分支限界法的基本思想；6.2-6.4旅行商問題，0/1背包問題，布線問題。教學(xué)要求：(1)掌握分支限界法的基本思想和原理；（2）能夠利用分支限界法解決旅行商問題，0/1背包問題；（3）理解布線問題的規(guī)則及表達(dá)方式。重點(diǎn)：分支限界法的原理和基本思想。難點(diǎn)：旅行商問題，0/1背包問題。621、2、37.隨機(jī)化算法7.1隨機(jī)化算法類型及隨機(jī)數(shù)生成器；7.2-7.5數(shù)值隨機(jī)化算法，蒙特卡羅算法，拉斯維加斯算法和舍伍德算法。教學(xué)要求：（1）掌握概率算法的基本思想和原理；（2）掌握簡(jiǎn)單分布的隨機(jī)數(shù)生成；（3）掌握數(shù)值概率算法，拉斯維加斯算法和蒙特卡羅算法。重點(diǎn)：了解概率算法的基本思想。難點(diǎn)：如何產(chǎn)生不同分布的隨機(jī)數(shù)，利用數(shù)值概率算法，拉斯維加斯算法和蒙特卡羅算法求解一些簡(jiǎn)單問題。601、2、38.NP完全理論8.1易解問題和難解問題定義；8.2P類與NP問題；8.3NP完全問題；8.4NP完全問題的近似算法。教學(xué)要求：（1）理解P類與NP問題，NP完全問題的定義；（2）了解非確定性圖靈機(jī)和多項(xiàng)式時(shí)間。重點(diǎn)：掌握P類與NP問題，NP完全問題分類。難點(diǎn)：非確定性圖靈機(jī)和多項(xiàng)式時(shí)間。401、2、3合計(jì)48162.實(shí)驗(yàn)部分實(shí)驗(yàn)部分的教學(xué)內(nèi)容、基本要求與學(xué)時(shí)分配見表3。表3實(shí)驗(yàn)項(xiàng)目、實(shí)驗(yàn)內(nèi)容與學(xué)時(shí)實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)內(nèi)容和要求實(shí)驗(yàn)學(xué)時(shí)對(duì)應(yīng)的課程目標(biāo)1.遞歸與分治實(shí)驗(yàn)內(nèi)容：合并排序，快速排序。實(shí)驗(yàn)要求：掌握遞歸與分治算法思想，分析算法的復(fù)雜度。41、2、32.動(dòng)態(tài)規(guī)劃實(shí)驗(yàn)內(nèi)容：矩陣連乘，最長(zhǎng)公共子序列，凸多邊形最優(yōu)三角剖分、圖像壓縮，流水作業(yè)調(diào)度，0/1背包問題，最優(yōu)二叉樹搜索（任選2個(gè)問題即可）。實(shí)驗(yàn)要求：掌握動(dòng)態(tài)規(guī)劃的基本思想，利用該算法解決一些具有全局最優(yōu)結(jié)構(gòu)的問題。41、2、33.貪心算法實(shí)驗(yàn)內(nèi)容：最優(yōu)裝載問題，哈夫曼樹，最短路徑算法，最小生成樹（Prim和Kruskal算法）（任選2個(gè)問題完成即可）。實(shí)驗(yàn)要求：掌握貪心算法的基本思想，分析貪心算法的正確性。41、2、34.分支限界法和回溯法實(shí)驗(yàn)內(nèi)容：裝載問題，旅行售貨員問題，0/1背包問題，n后問題和圖的m著色問題（任選1個(gè)問題，兩種算法完成即可）。實(shí)驗(yàn)要求：掌握分支限界法和回溯算法基本思想，并比較與貪心算法的設(shè)計(jì)理念的不同之處。41、2、3合計(jì)16五、教學(xué)方法及手段本課程以課堂講授為主，結(jié)合討論、案例、視頻資源、實(shí)驗(yàn)等教學(xué)手段完成課程教學(xué)任務(wù)和相關(guān)能力的培養(yǎng)。使得學(xué)生比較全面地理解算法的基本方法與設(shè)計(jì)原理，并能夠分析算法的復(fù)雜度和評(píng)價(jià)算法優(yōu)劣，在掌握各個(gè)算法特點(diǎn)和復(fù)雜度的基礎(chǔ)上，根據(jù)設(shè)計(jì)需求設(shè)計(jì)不同的算法。在實(shí)驗(yàn)教學(xué)環(huán)節(jié)中，通過案例教學(xué)和驗(yàn)證以掌握基本理論、基本知識(shí)和基本技能。培養(yǎng)學(xué)生自主學(xué)習(xí)能力、實(shí)際動(dòng)手能力，激發(fā)學(xué)生的創(chuàng)新思維。在實(shí)驗(yàn)前學(xué)生應(yīng)復(fù)習(xí)和掌握與本實(shí)驗(yàn)有關(guān)的教學(xué)內(nèi)容；在實(shí)驗(yàn)中要嚴(yán)格遵守實(shí)驗(yàn)紀(jì)律，按操作規(guī)程使用儀器；實(shí)驗(yàn)結(jié)束后，按規(guī)定對(duì)儀器進(jìn)行維護(hù)保養(yǎng)；每完成一項(xiàng)實(shí)驗(yàn)，要認(rèn)真完成一份實(shí)驗(yàn)報(bào)告。六、課程資源1.推薦教材（1）王秋芬.算法設(shè)計(jì)與分析(Python版)[M].北京:清華大學(xué)出版社,2021.2.參考書（1）王曉東.算法設(shè)計(jì)與分析習(xí)題解答（第四版）[M].北京:清華大學(xué)出版社,2018.（2）科曼,CormenTH.算法導(dǎo)論[M].北京:機(jī)械工業(yè)出版社,2021.（3）巴爾加瓦.算法圖解[M].北京:人民郵電出版社,2021.（4）王紅梅.算法設(shè)計(jì)與分析（第3版）[M].北京:清華大學(xué)出版社,2022.3.期刊（1）MadhumathiP,ThenmalarK.Dynamicoptimaldistributedresourceplanningforrenewableenergybasedinterconnectedmicrogridsusingteachinglearningalgorithm[J].JournalofIntelligent&FuzzySystems,2022,43(1).（2）ECancès,EhrlacherV,TLelièvre.Convergenceofagreedyalgorithmforhigh-dimensionalconvexnonlinearproblems[J].MathematicalModels&MethodsinAppliedSciences,2011,21(12):2433-2467.（3）劉國(guó)偉,任美睿,靳雨欣等.以培養(yǎng)計(jì)算思維能力為導(dǎo)向的算法設(shè)計(jì)與分析教學(xué)方法探索[J].計(jì)算機(jī)教育,2022(05):189-195.（4）SlevinskyRM,SafouhiH.ArecursivealgorithmfortheGtransformationandaccuratecomputationofincompleteBesselfunctions[J].AppliedNumericalMathematics,2010,60(12):1411-1417.（5）秦敏,王井陽(yáng),喬世權(quán).算法設(shè)計(jì)與分析課程案例教學(xué)模式的探討[J].創(chuàng)新創(chuàng)業(yè)理論研究與實(shí)踐,2022,5(11):145-147.4.網(wǎng)絡(luò)資源（1）算法導(dǎo)論.網(wǎng)易公開課./newview/movie/courseintro?newurl=%2Fspecial%2Fopencourse%2Falgorithms.html.（2）算法設(shè)計(jì)與分析.Bilibili./video/BV1Ls411W7PB?from=search&seid=5419514692522206093&spm_id_from=333.337.0.0.七、課程考核對(duì)課程目標(biāo)的支撐課程成績(jī)由過程性考核成績(jī)和期末測(cè)試成績(jī)兩部分構(gòu)成，具體考核/評(píng)價(jià)細(xì)則及對(duì)課程目標(biāo)的支撐關(guān)系見表4。表4課程考核對(duì)課程目標(biāo)的支撐考核環(huán)節(jié)占比考核/評(píng)價(jià)細(xì)則課程目標(biāo)123過程性考核課堂表現(xiàn)15（1）根據(jù)課堂出勤情況和課堂回答問題情況進(jìn)行考核，滿分100分。（2）以平時(shí)考核成績(jī)乘以其在總評(píng)成績(jī)中所占的比例計(jì)入課程總評(píng)成績(jī)。√√√447實(shí)驗(yàn)12.5（1）根據(jù)每個(gè)實(shí)驗(yàn)的實(shí)驗(yàn)操作完成情況和實(shí)驗(yàn)報(bào)告質(zhì)量單獨(dú)評(píng)分，滿分100分；（2）每次實(shí)驗(yàn)單獨(dú)評(píng)分，取各次實(shí)驗(yàn)成績(jī)的平均值作為此環(huán)節(jié)的最終成績(jī)。（3）以實(shí)驗(yàn)成績(jī)乘以其在總評(píng)成績(jī)中所占的比例計(jì)入課程總評(píng)成績(jī)。√√√52.55作業(yè)22.5（1）主要考核學(xué)生對(duì)各章節(jié)知識(shí)點(diǎn)的復(fù)習(xí)、理解和掌握程度，滿分100分；（2）每次作業(yè)單獨(dú)評(píng)分，取各次成績(jī)的平均值作為此環(huán)節(jié)的最終成績(jī)。（3）以作業(yè)成績(jī)乘以其在總評(píng)成績(jī)中所占的比例計(jì)入課程總評(píng)成績(jī)?！獭獭?8.58期末考核50（1）期末測(cè)試成績(jī)成績(jī)100分，以測(cè)試成績(jī)乘以其在總評(píng)成績(jī)中所占的比例計(jì)入課程總評(píng)成績(jī)。（2）主要考核基本算法的原理和應(yīng)用，包括遞歸，分治，動(dòng)態(tài)規(guī)劃，貪心，分支限界法，回溯算法和概率算法。（3）測(cè)試題型包含填空題、選擇題、判斷題和分析題等題型?！獭獭?02010合計(jì)：100分353530八、考核與成績(jī)?cè)u(píng)定1.考核方式及成績(jī)?cè)u(píng)定考核方式：本課程主要以課堂表現(xiàn)、實(shí)驗(yàn)、作業(yè)、期末測(cè)試等方式對(duì)學(xué)生進(jìn)行考核評(píng)價(jià)?？己嘶疽螅嚎己丝偝煽?jī)由期末測(cè)試（占比50%）和過程性考核成績(jī)（占比50%）組成，其中：期末測(cè)試滿分為100分，試題類型為填空題、選擇題、判斷題和分析題等題型，試卷中基本知識(shí)、基本理論、基本技能的試題分值不超過50%，綜合應(yīng)用題、分析題不低于50%；過程性考核滿分為100分，由課堂表現(xiàn)、實(shí)驗(yàn)和作業(yè)三部分組成，占過程