算法設(shè)計(jì)與分析（含實(shí)驗(yàn)實(shí)踐） 課程教學(xué)大綱

《算法設(shè)計(jì)與分析》課程教學(xué)大綱一、課程簡介課程中文名算法設(shè)計(jì)與分析課程英文名AlgorithmDesignandAnalysis雙語授課□是否課程代碼10122105課程學(xué)分3總學(xué)時(shí)數(shù)48（含實(shí)踐0）課程類別□通識教育課程□公共基礎(chǔ)課程專業(yè)教育課程□綜合實(shí)踐課程□教師教育課程課程性質(zhì)□必修選修□其他課程形態(tài)□線上線下□線上線下混合式□社會實(shí)踐□虛擬仿真實(shí)驗(yàn)教學(xué)考核方式閉卷□開卷□課程論文□課程作品□匯報(bào)展示□報(bào)告課堂表現(xiàn)階段性測試平時(shí)作業(yè)□其他（可多選）開課學(xué)院大數(shù)據(jù)與智能工程學(xué)院開課系(教研室)數(shù)據(jù)科學(xué)與大數(shù)據(jù)面向?qū)I(yè)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)專業(yè)開課學(xué)期第5學(xué)期先修課程無后續(xù)課程無選用教材王幸明,張曉霞.算法設(shè)計(jì)與分析[M].北京：人民郵電出版社,2018參考書目吳哲輝,崔煥慶,馬炳先,吳振寰.算法設(shè)計(jì)方法[M].北京：機(jī)械工業(yè)出版社,2008.課程資源中國大學(xué)MOOC—北京大學(xué)：/course/PKU-1002534001課程簡介算法設(shè)計(jì)與分析課程是數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)專業(yè)的選修課程，主要介紹算法的設(shè)計(jì)和分析方法，包括用算法設(shè)計(jì)策略、貪心算法、動態(tài)規(guī)劃等。通過算法設(shè)計(jì)與分析的學(xué)習(xí)，學(xué)生能夠掌握算法的設(shè)計(jì)和分析方法，具備設(shè)計(jì)高效算法解決實(shí)際問題的能力。此外，課程還強(qiáng)調(diào)團(tuán)隊(duì)協(xié)作和溝通能力的培養(yǎng)，通過分組項(xiàng)目和討論等方式，提高學(xué)生的表達(dá)和交流能力。二、課程目標(biāo)表2-1課程目標(biāo)序號具體課程目標(biāo)課程目標(biāo)1能夠掌握算法設(shè)計(jì)和分析中的問題分析方法，包括問題定義、問題分解、算法復(fù)雜度分析等。通過課程的學(xué)習(xí)，學(xué)生可以培養(yǎng)出對問題的識別和抽象能力，能夠準(zhǔn)確分析問題的本質(zhì)和特征，為后續(xù)的算法設(shè)計(jì)和分析提供基礎(chǔ)。課程目標(biāo)2能夠掌握算法設(shè)計(jì)和實(shí)現(xiàn)的技能，具備設(shè)計(jì)高效算法解決實(shí)際問題的能力。課程將通過多種算法設(shè)計(jì)策略和復(fù)雜度分析方法的學(xué)習(xí)和實(shí)踐，幫助學(xué)生掌握算法設(shè)計(jì)和分析的技巧，能夠設(shè)計(jì)和實(shí)現(xiàn)針對不同問題的有效算法。課程目標(biāo)3能夠了解算法設(shè)計(jì)與分析領(lǐng)域的前沿研究成果，包括最新的算法設(shè)計(jì)和分析技術(shù)、應(yīng)用場景等。通過文獻(xiàn)閱讀、研究報(bào)告等方式，培養(yǎng)學(xué)生的研究能力，讓他們能夠跟蹤和掌握該領(lǐng)域的發(fā)展動態(tài)，為未來的研究和開發(fā)工作打下基礎(chǔ)。表2-2課程目標(biāo)與畢業(yè)要求對應(yīng)關(guān)系畢業(yè)要求指標(biāo)點(diǎn)課程目標(biāo)畢業(yè)要求2：問題分析：能夠應(yīng)用數(shù)學(xué)、自然科學(xué)、計(jì)算機(jī)科學(xué)和工程科學(xué)的基本原理，通過文獻(xiàn)研究、數(shù)學(xué)建模、工程經(jīng)驗(yàn)提煉等方法，在大數(shù)據(jù)應(yīng)用的構(gòu)思與設(shè)計(jì)階段，識別、表達(dá)、分析大數(shù)據(jù)應(yīng)用領(lǐng)域復(fù)雜工程問題及其解決方法，以獲得有效結(jié)論?！綡】2.2能夠針對大數(shù)據(jù)應(yīng)用領(lǐng)域中的相關(guān)工程問題，選擇合適的數(shù)學(xué)模型并分析其可行性，驗(yàn)證其正確性。課程目標(biāo)1畢業(yè)要求3：設(shè)計(jì)/開發(fā)解決方案：能夠針對大數(shù)據(jù)應(yīng)用領(lǐng)域的復(fù)雜工程問題，綜合應(yīng)用數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)基本原理和方法，設(shè)計(jì)、開發(fā)滿足特定應(yīng)用需求的系統(tǒng)方案，并能夠在設(shè)計(jì)環(huán)節(jié)中體現(xiàn)創(chuàng)新意識，考慮社會、健康、安全、法律、文化以及環(huán)境等多維度協(xié)同發(fā)展因素?！綥】3.2能夠根據(jù)實(shí)際目標(biāo)和解決方案，設(shè)計(jì)或開發(fā)出大數(shù)據(jù)應(yīng)用系統(tǒng)及說明文檔，并能夠在設(shè)計(jì)和開發(fā)過程中體現(xiàn)創(chuàng)新性。課程目標(biāo)2畢業(yè)要求4：研究：能夠基于數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)的相應(yīng)原理，采用科學(xué)方法對大數(shù)據(jù)應(yīng)用領(lǐng)域中的復(fù)雜工程問題進(jìn)行研究，制定技術(shù)路線、設(shè)計(jì)實(shí)驗(yàn)方案并開展實(shí)驗(yàn)，通過實(shí)驗(yàn)分析得到合理有效的結(jié)論。【M】4.2能夠針對大數(shù)據(jù)應(yīng)用領(lǐng)域復(fù)雜工程問題，根據(jù)解決方案進(jìn)行方案設(shè)計(jì)與實(shí)施，能對設(shè)計(jì)或?qū)嵤┻^程的中間結(jié)果或數(shù)據(jù)進(jìn)行正確分析和反饋。課程目標(biāo)3三、課程學(xué)習(xí)內(nèi)容與方法（一）理論學(xué)習(xí)內(nèi)容及要求表3-1課程目標(biāo)、學(xué)習(xí)內(nèi)容和教學(xué)方法對應(yīng)關(guān)系序號課程模塊學(xué)習(xí)內(nèi)容學(xué)習(xí)任務(wù)課程目標(biāo)學(xué)習(xí)重點(diǎn)難點(diǎn)教學(xué)方法學(xué)時(shí)1算法基礎(chǔ)1.算法的基本概念個人作業(yè)：漢諾塔、斐波那契數(shù)列的時(shí)間復(fù)雜度分析課程目標(biāo)1重點(diǎn)：算法和算法復(fù)雜度的基本概念難點(diǎn)：算法時(shí)間復(fù)雜度的估算方法講授法案例教學(xué)82.算法設(shè)計(jì)與分析的基本方法課程目標(biāo)13.算法的定量分析（時(shí)間復(fù)雜度，空間復(fù)雜度）課程目標(biāo)34.遞歸與歸納定義及一般方法課程目標(biāo)22分治算法1.分治算法的思想個人作業(yè)：編程實(shí)現(xiàn)快速排序算法課程目標(biāo)1重點(diǎn)：1.分治算法的思想難點(diǎn)：2.快速排序、折半查找算法講授法案例教學(xué)102.排序問題中的分治算法課程目標(biāo)23.查找問題中的分治算法課程目標(biāo)34.組合問題中的分治算法課程目標(biāo)23貪心算法1.貪心算法的思想個人作業(yè)：編程實(shí)現(xiàn)單源最短路徑算法、最小生成樹算法課程目標(biāo)1重點(diǎn)：1.貪心算法的思想難點(diǎn)：2.背包問題、單源最短路徑問題、最小生成樹問題講授法案例教學(xué)102.組合問題中的貪心算法課程目標(biāo)23.圖問題中的貪心算法課程目標(biāo)34動態(tài)規(guī)劃算法1.動態(tài)規(guī)劃算法的思想個人作業(yè)：編程實(shí)現(xiàn)最優(yōu)二叉搜索樹、0/1背包問題課程目標(biāo)1重點(diǎn)：動態(tài)規(guī)劃算法的思想講授法案例教學(xué)102.查找問題中的動態(tài)規(guī)劃算法課程目標(biāo)2難點(diǎn)：0/1背包問題3.圖問題中的動態(tài)規(guī)劃算法課程目標(biāo)24.組合問題中的動態(tài)規(guī)劃算法課程目標(biāo)25回溯算法1.回溯算法的思想個人作業(yè)：利用回溯法編程實(shí)現(xiàn)0/1背包問題課程目標(biāo)1重點(diǎn)：1.回溯算法的思想難點(diǎn)：2.回溯算法的設(shè)計(jì)思路講授法案例教學(xué)102.組合問題中的回溯算法課程目標(biāo)23.圖問題中的回溯算法課程目標(biāo)24.算法效率的影響因素及改進(jìn)途徑課程目標(biāo)3四、課程考核（一）考核內(nèi)容與考核方式表4課程目標(biāo)、考核內(nèi)容與考核方式對應(yīng)關(guān)系課程目標(biāo)考核內(nèi)容所屬學(xué)習(xí)模塊/項(xiàng)目考核占比考核方式課程目標(biāo)11.算法的基本概念模塊155%閉卷考試2.算法設(shè)計(jì)與分析的基本方法模塊13.分治算法的思想模塊24.貪心算法的思想模塊35.動態(tài)規(guī)劃算法的思想模塊46.回溯算法的思想模塊5課程目標(biāo)21.遞歸算法的特性與執(zhí)行過程模塊116%閉卷考試2.排序問題、組合問題中的分治算法模塊23.組合問題中的貪心算法模塊34.查找問題、圖問題、組合問題中的動態(tài)規(guī)劃算法模塊45.組合問題、圖問題中的回溯算法模塊5課程目標(biāo)31.算法時(shí)間復(fù)雜度分析模塊129%閉卷考試2.查找問題中的分治算法模塊23.圖問題中的貪心算法模塊34.算法效率的影響因素及改進(jìn)途徑模塊5表4-2課程目標(biāo)與考核方式矩陣關(guān)系課程目標(biāo)考核方式考核占比閉卷成績比例60%課堂表現(xiàn)成績比例10%平時(shí)作業(yè)成績比例20%階段性測驗(yàn)成績比例10%課程目標(biāo)150%60%60%70%55%課程目標(biāo)220%10%10%10%16%課程目標(biāo)330%30%30%20%29%（二）成績評定1.平時(shí)成績評定（1）課堂表現(xiàn)（25%）：通過學(xué)生在課堂上的表現(xiàn)情況、發(fā)言與提問情況，來評價(jià)學(xué)生相關(guān)的能力。（2）作業(yè)完成情況（50%）：圍繞課程的學(xué)習(xí)目標(biāo)進(jìn)行作業(yè)的設(shè)計(jì)。如讓學(xué)生簡述對知識的認(rèn)識，考核學(xué)生對于概念的理解情況，幫助學(xué)生將定義轉(zhuǎn)化為自己的理解。（3）階段性測驗(yàn)（25%）：學(xué)生在平時(shí)測試、測驗(yàn)中掌握課程的情況。2.期末成績評定主要考察學(xué)生對算法設(shè)計(jì)與分析的基本概念、基本知識、遞歸算法、分治算法、貪心算法、動態(tài)規(guī)劃算法、回溯算法的理解、掌握和應(yīng)用，方式為閉卷考試。3.總成績評定總成績應(yīng)由平時(shí)考核成績和期末考核成績構(gòu)成總成績（100%）=平時(shí)成績（40%）+期末成績（60%）（三）評分標(biāo)準(zhǔn)表5評分標(biāo)準(zhǔn)（非試卷考核項(xiàng)目）考核項(xiàng)目評分標(biāo)準(zhǔn)優(yōu)秀(100>x≥90)良好(90>x≥80)中等(80>x≥70)及格(70>x≥60)不及格(x<60)課堂表現(xiàn)課上嚴(yán)格遵守課堂紀(jì)律，按要求完成課堂練習(xí)且正確率高，積極參與課堂討論，討論觀點(diǎn)有新意，有見解，實(shí)驗(yàn)課不遲到早退，與老師積極互動。課上嚴(yán)格遵守課堂紀(jì)律，按要求完成課堂練習(xí)且正確率較高，積極參與課堂討論，討論觀點(diǎn)有一定新意和見解，實(shí)驗(yàn)課不遲到早退，與老師積極互動。課上嚴(yán)格遵守課堂紀(jì)律，按要求完成課堂練習(xí)且有一定正確率，參與課堂討論，討論觀點(diǎn)有一定新意和見解，實(shí)驗(yàn)課不遲到早退，與老師互動。課上嚴(yán)格遵守課堂紀(jì)律，按要求完成課堂練習(xí)且基本正確率，參與課堂討論，討論觀點(diǎn)基本的新意和見解，實(shí)驗(yàn)課不遲到早退，與老師偶爾互動。課上不遵守課堂紀(jì)律，不參與課堂討論，未按要求完成課堂練習(xí)或正確率低。實(shí)驗(yàn)課缺課。平時(shí)作業(yè)按照作業(yè)目標(biāo)完成，步驟完整、數(shù)據(jù)詳實(shí)、按時(shí)提交。按照作業(yè)目標(biāo)完成，步驟基本完整、數(shù)據(jù)基本詳實(shí)、按時(shí)提交。按照作業(yè)目標(biāo)完成，步驟完整，缺乏數(shù)據(jù)支撐，按時(shí)提交按照作業(yè)目標(biāo)完成，步驟描述不完整，缺乏數(shù)據(jù)支撐，按時(shí)提交未按照作業(yè)目標(biāo)完成，缺乏步驟描述、數(shù)據(jù)支撐，未按時(shí)提交。階段性測驗(yàn)掌握算法基礎(chǔ)知識和常用相關(guān)算法如分治算法、貪心算法、動態(tài)規(guī)劃算法等設(shè)計(jì)思想，能熟練使用相關(guān)知識并解決問題。掌握算法基礎(chǔ)知識和常用相關(guān)算法如分治算法、貪心算法、動態(tài)規(guī)劃算法等設(shè)計(jì)思想，能使用相關(guān)知識并解決問題。掌握算法基礎(chǔ)知識和常用相關(guān)算法如分治算法、貪心算法、動態(tài)規(guī)劃算法等設(shè)計(jì)思想，能在一定程度上使用相關(guān)知識并解決問題。掌握算法基礎(chǔ)知識和常用相關(guān)算法如分治算法、貪心算法