算法設(shè)計與分析 教學大綱

ADDINCNKISM.UserStyle課程編碼課程類別專業(yè)必修課課程名稱算法設(shè)計與分析英文名稱AlgorithmDesignandAnalysis學分3建議修讀學期4總學時數(shù)48講授學時32實驗學時16實踐實訓學時網(wǎng)絡(luò)學時先修課程C語言程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)考核方式考試適用專業(yè)計算機科學與技術(shù)、軟件工程大綱執(zhí)筆人大綱審核人一、課程目標《算法分析與設(shè)計》課程是計算機科學與技術(shù)專業(yè)的核心學位課程，同時也是軟件工程專業(yè)的專業(yè)必修課。課程內(nèi)容覆蓋計算模型、分治法、動態(tài)規(guī)劃、貪心算法、回溯法和分支限界等。通過本課程的學習，達成以下課程目標：1．知識目標：掌握算法基本概念，深入理解復雜度分析，熟悉多種遞歸與分治、動態(tài)規(guī)劃、貪心算法、回溯法、分支限界法等算法設(shè)計方法；（支撐畢業(yè)要求1）2．能力目標：能針對特定問題選擇算法策略，構(gòu)建算法框架并實現(xiàn)，具備性能分析與優(yōu)化能力；（支撐畢業(yè)要求2、3）3．職業(yè)素養(yǎng)：具備職業(yè)素養(yǎng)和團隊協(xié)作意識，具有設(shè)計、編寫、優(yōu)化算法的能力。（支撐畢業(yè)要求8、9）畢業(yè)要求工程知識問題分析設(shè)計與解決方案研究使用現(xiàn)代工具工程與社會環(huán)境與可持續(xù)發(fā)展職業(yè)規(guī)范個人和團隊溝通項目管理終身學習課程關(guān)聯(lián)度MHHLL二、課程目標與畢業(yè)要求的對應關(guān)系畢業(yè)要求指標點課程目標畢業(yè)要求1指標1-3 能夠運用專業(yè)知識對工程問題建立數(shù)學模型并解決計算問題；課程目標1畢業(yè)要求2指標2-2 能夠基于相關(guān)科學原理和數(shù)學模型方法正確表達復雜軟件工程問題；課程目標2畢業(yè)要求3指標3-2 能夠針對特定需求，完成軟件算法流程、單元模塊（組件、部件）的設(shè)計、開發(fā)和測試，并能在設(shè)計、開發(fā)和測試等全周期中體現(xiàn)工程思維；課程目標2畢業(yè)要求8指標8-3 理解工程師對公眾的安全、健康和福祉，以及環(huán)境保護的社會責任，能夠在工程實踐中自覺履行責任。課程目標3畢業(yè)要求9指標9-3 能夠了解團隊成員想法，具備在多學科背景下的團隊中的協(xié)調(diào)、協(xié)作、組織和管理能力，并能夠在項目實施過程中運用以上能力；課程目標3三、教學內(nèi)容和重難點第一章算法分析基礎(chǔ)（支撐課程目標1、3）（一）教學要求理解算法的概念掌握算法在最佳、最差和平均情況下的復雜度分析掌握算法復雜度漸進性態(tài)的數(shù)學表達式（二）教學內(nèi)容1.1算法與程序1.2算法復雜度分析概念1.3算法復雜度的漸進性態(tài)1.4O,Ω,θ1.5數(shù)學基礎(chǔ)1.6非遞歸算法的算法復雜度分析（三）本章重難點教學重點：算法的定義和復雜度教學難點：復雜度的計算第二章分治法（支撐課程目標1、2、3）（一）教學要求理解遞歸的概念掌握設(shè)計有效算法的分治策略通過范例學習分治策略設(shè)計技巧（二）教學內(nèi)容2.1遞歸的概念2.2分治法的基本思想2.3分治法的應用2.3.1一維數(shù)組的二分查找2.3.2二維數(shù)組查找2.3.3合并排序2.3.4逆序?qū)?.3.5快速排序2.3.6K選擇問題2.3.7棋盤覆蓋2.3.8快速冪2.3.9大整數(shù)乘法和Strassen矩陣乘法2.3.10快速傅里葉變換2.4小結(jié)（三）本章重難點教學重點：分治法的思想，適用條件，復雜度計算教學難點：分治法的基本思想和復雜度計算第三章貪心算法（支撐課程目標1、2、3）（一）教學要求理解貪心算法的概念掌握貪心算法的基本要素理解貪心算法與動態(tài)規(guī)劃算法的差異通過范例學習貪心算法設(shè)計策略（二）教學內(nèi)容3.1貪心算法的思想3.2貪心算法的要素3.3貪心選擇問題3.4任務調(diào)度問題3.5最小生成樹3.6單源最短路徑3.7哈夫曼編碼3.8小結(jié)（三）本章重難點教學重點：貪心算法的基本要素和思想教學難點：貪心算法和動態(tài)規(guī)劃的區(qū)別第四章回溯法（支撐課程目標1、2、3）（一）教學要求理解回溯法的深度優(yōu)先策略掌握回溯法的算法框架通過范例學習回溯法設(shè)計策略（二）教學內(nèi)容4.1回溯法的思想4.2排列問題4.3組合問題4.4N-皇后問題4.50-1背包問題4.6物流派送問題4.7小結(jié)（三）本章重難點教學重點：回溯法的深度優(yōu)先搜索策略和框架教學難點：回溯的剪枝和限制函數(shù)第五章分支限界法（支撐課程目標1、2、3）（一）教學要求理解分支限界的剪枝策略掌握分支限界的算法框架通過范例學習分支限界算法設(shè)計策略（二）教學內(nèi)容5.1分支限界的思想5.2最小出邊界限法5.3未訪問城市最小出邊之和界限法5.4廣度優(yōu)先搜索的未訪問城市最小出邊之和限界法5.50-1背包問題5.6小結(jié)（三）本章重難點教學重點：分支限界法的剪枝搜索策略，分支限界法的算法框架教學難點：分支限界法的剪枝搜索策略第六章動態(tài)規(guī)劃（支撐課程目標1、2、3）（一）教學要求理解動態(tài)規(guī)劃算法的概念掌握動態(tài)規(guī)劃的基本要素掌握設(shè)計動態(tài)規(guī)劃算法的步驟通過范例學習動態(tài)規(guī)劃算法設(shè)計策略（二）教學內(nèi)容6.1動態(tài)規(guī)劃的思想6.2線性動態(tài)規(guī)劃6.3背包類問題6.4記憶化搜索與區(qū)間動態(tài)規(guī)劃6.5小結(jié)（三）本章重難點教學重點：動態(tài)規(guī)劃的思想及求解步驟教學難點：動態(tài)規(guī)劃思想第七章智能算法（支撐課程目標1、3）（一）教學要求理解智能算法分類掌握粒子群算法的設(shè)計思想掌握模擬退火的設(shè)計思想掌握禁忌搜索的設(shè)計思想（二）教學內(nèi)容7.1智能算法分類7.2粒子群算法7.3模擬退火算法7.4禁忌搜索（三）本章重難點教學重點：智能算法的思想教學難點：智能算法的實現(xiàn)策略四、課時安排和教學方法（一）教學方法整個教學過程要努力做到將理論知識與實踐的緊密結(jié)合，闡述基本原理，培養(yǎng)學生問題分析能力。首先，課堂講授注意采用啟發(fā)式教學，激勵學生思考，并積極參與討論；通過案例分析，強化學生算法分析方法的應用、思維方法的建立；以課堂講為主，并以實驗課、課外作業(yè)、生產(chǎn)實習等教學環(huán)節(jié)作為課程學習的補充，理論教學與實驗訓練結(jié)合，強化算法設(shè)計與分析能力的培養(yǎng)。其次，加強計算機輔助教學，增加SPOC教學環(huán)節(jié)，并通過課堂互動、分組討論等多種形式，訓練學生分析、綜合、小結(jié)、歸納的能力，從而鞏固學生對所學知識的掌握程度，為后續(xù)課程的學習以及自主學習能力的培養(yǎng)打好基礎(chǔ)。最后，本門課程是在“新工科”背景下開設(shè)的課程，既講授了算法的基礎(chǔ)知識，也要緊跟社會需求培養(yǎng)學生的算法設(shè)計能力、分析能力和創(chuàng)新能力。此外，教師課堂教學上要有意識培養(yǎng)學生正確的人生觀、世界觀，使其具有良好的社會責任感，遵守職業(yè)道德。（二）課程思政切入點設(shè)計共16個教學周每周1次課每次課2學時教學周次課時安排教學進度（章節(jié)講/知識單元）課程思政點融入方式與教學方法預期教學成效11算法基礎(chǔ)概述精益求精工程倫理介紹抖音推薦算法案，算法的美與惡，討論法培養(yǎng)學生的工匠精神和工程倫理觀2-42分治法愛國情懷高效新冠病毒檢測試題，案例法培養(yǎng)學生的愛國情懷5-71貪心算法科技自豪感、精益求精最優(yōu)裝載，案例法培養(yǎng)學生的工匠精神和科技自豪感8-101回溯法愛國情懷、精益求精深度搜索，案例法培養(yǎng)學生的愛國敬業(yè)和工匠精神11-121分支限界愛國情懷、精益求精廣度搜索，案例法培養(yǎng)學生的愛國敬業(yè)和工匠精神13-152動態(tài)規(guī)劃科技自豪感、精益求精討論法培養(yǎng)學生的工匠精神和科技自豪感16-171智能算法精益求精案例法培養(yǎng)學生的工匠精神和科技自豪感（三）課時安排：章節(jié)講課實驗第1章算法基礎(chǔ)2學時第2章分治法6學時3學時第3章貪心算法4學時2學時第4章回溯法6學時3學時第5章分支限界4學時2學時第6章動態(tài)規(guī)劃6學時4學時第7章智能算法4學時2學時合計32學時16學時五、實踐教學安排本門課程是理論和實踐相結(jié)合的課程，其中實驗是很重要的一個教學環(huán)節(jié)，通過實驗可以給學生多一些實操的機會，并有助于在實驗中理解并掌握課堂中的基礎(chǔ)知識和基本原理。序號實驗項目實驗類型實驗要求1算法基礎(chǔ)驗證性實驗驗證最大元素問題的問題規(guī)模與運行時間的線性關(guān)系；2分治法設(shè)計性實驗用分治法實現(xiàn)快速排序等問題，分析其算法復雜度；3貪心算法實驗設(shè)計性實驗用貪心算法求解背包等問題，分析其算法復雜度；4回溯法實驗設(shè)計性實驗用回溯法求解旅行商等問題，分析其算法復雜度；5分支限界實驗設(shè)計性實驗用分支限界求解旅行商等問題，分析其算法復雜度；6動態(tài)規(guī)劃實驗1設(shè)計性實驗用動態(tài)規(guī)劃求解線性規(guī)劃等問題，分析其算法復雜度；7動態(tài)規(guī)劃實驗2設(shè)計性實驗用動態(tài)規(guī)劃求解背包類等問題，分析其算法復雜度；8智能算法實驗設(shè)計性實驗用智能算法求解優(yōu)化問題，分析其算法復雜度；六、課程教學評價本課程平時成績占30%，期末成績70%（視平時開展輔助教學活動而定），平時成績考核的形式主要有：作業(yè)、實驗報告、分組任務、課堂互動及章節(jié)測驗等；期末成績考核的形式是閉卷考試為主。課程教學目標考核內(nèi)容評價依據(jù)課程目標11.理解算法基本概念，掌握算法時間和空間復雜度分析的基本方法；2.計算算法的時間復雜度和空間復雜度，衡量算法的性能；3．熟悉分治法、貪心法、動態(tài)規(guī)劃、回溯法、分支限界和智能算法等理論知識；章節(jié)測試、平時作業(yè)、期末考試。課程目標21.運用分治法、貪心法、動態(tài)規(guī)劃、回溯法、分支限界和智能算法求解復雜問題；2.運用更優(yōu)化算法來求解復雜問題；平時作業(yè)、章節(jié)測試、實驗成績、期末考試。課程目標31.設(shè)計算法的能力；2.編寫代碼的能力；3.優(yōu)化算法的能力；4.團隊協(xié)作能力；分組任務、實驗成績、期末考試。七、成績評定方法（一）成績評定依據(jù)平時成績：30%，期末筆試：70%平時成績占分比例%期末筆試占分比例%課程目標14040課程目標24040課程目標32020（二）課程目標達成度評價課程目標平時成績目標總分期末筆試目標總分目標總分目標達成期望值課程目標14040400.65課程目標24040400.65課程目標32020200.7八、課程學習資源1.選用教材教材名稱（第幾版）編者出版社出版時間是否馬工程教材列入何規(guī)劃算法設(shè)計與分析田小霞清華大學出版社2024.8否國家級實驗教學示范中心計算機學科組2.主要參考書目[1]王曉東,計算機算法設(shè)計與分析（第五版）.2018.8，電子工業(yè)出版社.3.其它學習資源[1]超星學習通SPOC教學平臺;[2]力扣(LeetCode)在線題庫,/5;[3]ACWing在線題庫，/problem/;[4]洛谷在線題庫，.九、課程學習建議1、先修課程：程序設(shè)計語言和數(shù)據(jù)結(jié)構(gòu)；2、做好平時預習復習，要求學生從大一開始按照軟件開發(fā)流程，可以考慮從藍橋杯和ACM競賽入手，逐步培養(yǎng)學生的算法設(shè)計與分析學習興趣；3、注重實驗與考核相結(jié)合，鼓勵學生進行算法競賽；4、建議在教學過程中，將算法設(shè)計與分析的基礎(chǔ)知識與實際教學緊密結(jié)合，鼓勵學生積極參與算法競賽。對于積極參與并表現(xiàn)優(yōu)異的學生，建議在平時成績或總評成績中給予適當加分，直至在期末考試及格的前提下，按優(yōu)秀等級記分。（具體由任課老師按照校、院等相關(guān)文件確定并報批）。十、評分標準課程目標評分標準90-10080-8970-7960-690-59優(yōu)良中及格不及格課程目標1熟悉并掌握算法的基礎(chǔ)知識，對算法復雜度的基本概念有系統(tǒng)的認知；熟悉算法復雜度的分析過程。掌握算法的基礎(chǔ)知識，對算法復雜度的基本概念有較為系統(tǒng)的認知；掌握算法復雜度的分析過程。基本上理解算法的基礎(chǔ)知識，對算法復雜度的基本概念有一定的認知；基本上能理解算法復雜度的分析過程。部分理解和掌握算法的基礎(chǔ)知識，對算法復雜度的基本概念有零星的認知；了解算法復雜度的分析過程。對算法的基礎(chǔ)知識大部分不掌握，不了解算法復雜度的基本概念；不了解算法復雜度的分析過程。課程目標2熟悉并掌握分治法、貪心法、動態(tài)規(guī)劃、回溯法、分支限界和智能算法等理論知識；能夠較靈活地應用算法設(shè)計策略，具有較強的解決實際問題的能力。掌握分治法、貪心法、動態(tài)規(guī)劃、回溯法、分支限界和智能算法等理論知識；能夠較好地使用適合的算法策略，具有一定的解決實際問題的能力。理解分治法、貪心法、動態(tài)規(guī)劃、回溯法、分支限界和智能算法等理論知識；可以比較好地運用算法設(shè)計