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

《算法分析與設(shè)計》教學(xué)大綱課程編號：13220507英文名稱：Design&AnalysisofAlgorithms學(xué)分：3學(xué)時：總學(xué)時64學(xué)時，其中理論32學(xué)時，實踐32學(xué)時先修課程：高級語言、數(shù)據(jù)結(jié)構(gòu)課程類別：專業(yè)拓展課授課對象：計算機科學(xué)與技術(shù)專業(yè)學(xué)生教學(xué)單位：機械與電氣工程學(xué)院修讀學(xué)期：第5學(xué)期一、課程描述和目標(biāo) 本課程是一門理論性與實踐性兼顧的課程，是計算機科學(xué)與技術(shù)專業(yè)拓展課程,理論性和實踐性都很強，既要掌握基本算法設(shè)計與實現(xiàn)方法，還要理論分析這些算法的時間與空間復(fù)雜度。通過本課程的學(xué)習(xí)，使學(xué)生具備較扎實的算法設(shè)計與分析知識和方法；使學(xué)生掌握基本的算法分析方法和常見的算法設(shè)計方法；理解計算機算法效率分析與設(shè)計所涉及的基本概念和基礎(chǔ)知識。通過對算法實例的分析，進一步加深對算法設(shè)計方法的認(rèn)識和理解。通過學(xué)習(xí)本課程，達到以下課程目標(biāo)：課程目標(biāo)1：學(xué)習(xí)算法設(shè)計的常見的主要方法，掌握理解算法分析的相關(guān)概念和基本方法，培養(yǎng)算法設(shè)計和分析的初步能力。課程目標(biāo)2：能根據(jù)實際問題選擇合適的數(shù)據(jù)邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，能運用算法設(shè)計與分析的相關(guān)知識設(shè)計和分析求解實際問題的算法，對復(fù)雜工程問題具有一定的算法設(shè)計與分析能力，能熟練應(yīng)用課程介紹的算法設(shè)計方法來解決軟件開發(fā)中的實際問題。課程目標(biāo)3：能應(yīng)用算法性能分析方法對算法性能進行分析研究，能有針對性地設(shè)計實驗，并通過實驗數(shù)據(jù)對算法性能進行分析。二、課程目標(biāo)對畢業(yè)要求的支撐關(guān)系畢業(yè)要求指標(biāo)點課程目標(biāo)權(quán)重指標(biāo)點4-2：能夠根據(jù)計算機相關(guān)領(lǐng)域的復(fù)雜工程問題的研究對象及其特征，制定研究方法和技術(shù)路線，設(shè)計實驗方案。課程目標(biāo)1課程目標(biāo)2課程目標(biāo)3H指標(biāo)點5-3：能夠針對具體系統(tǒng)模塊，開發(fā)或選用滿足特定需求的現(xiàn)代工具，模擬、預(yù)測計算機軟硬件系統(tǒng)在設(shè)計與實施等過程中的專業(yè)問題，并能夠分析其局限性。課程目標(biāo)1課程目標(biāo)2課程目標(biāo)3M三、教學(xué)內(nèi)容、基本要求與學(xué)時分配序號教學(xué)內(nèi)容基本要求及重、難點（含德育要求）學(xué)時教學(xué)方式對應(yīng)課程目標(biāo)1算法概述：算法和程序；算法復(fù)雜性；算法效率；NP完全性理論。理解算法的概念、算法的時間復(fù)雜性和空間復(fù)雜性；掌握求解問題的基本步驟；掌握算法運行時間的估計；NP完全理論。德育要求：培養(yǎng)勇于探索的科學(xué)精神。2講授式討論式課程目標(biāo)1課程目標(biāo)22遞歸與分治策略：遞歸的概念；分治法的基本思想；二分搜索技術(shù)；大整數(shù)的乘法；strassen矩陣乘法；棋盤覆蓋；合并排序；快速排序；線性時間選擇；最接近點對問題；循環(huán)賽日程表。理解掌握遞歸的概念與的基本原理；理解分治策略的基本原理和效率分析，掌握設(shè)計有效算法的分治策略。德育要求：培養(yǎng)嚴(yán)謹(jǐn)踏實的科學(xué)態(tài)度。6講授式啟發(fā)式探究式討論式練習(xí)式課程目標(biāo)1課程目標(biāo)2課程目標(biāo)33動態(tài)規(guī)劃：矩陣連乘問題；動態(tài)規(guī)劃算法的基本要素；最長公共子序列；最大子段和；凸多邊形最優(yōu)三角剖分；多邊形游戲；圖像壓縮；電路布線；流水作業(yè)調(diào)度；0-1背包問題；最優(yōu)二叉搜索樹。理解動態(tài)規(guī)劃算法的概念；掌握動態(tài)規(guī)劃算法的基本要素；掌握設(shè)計動態(tài)規(guī)劃算法的步驟以及典型問題的應(yīng)用與分析。德育要求：培養(yǎng)刻苦鉆研的科學(xué)精神。4講授式啟發(fā)式探究式討論式練習(xí)式課程目標(biāo)1課程目標(biāo)2課程目標(biāo)34貪心算法：活動安排問題；貪心算法的基本要素；最優(yōu)裝載；哈夫曼編碼；單源最短路徑；最小生成樹；多機調(diào)度問題。理解貪心算法的基本思想、適用條件；掌握貪心算法的設(shè)計策略，掌握貪心算法典型問題的應(yīng)用與分析。德育要求：養(yǎng)成腳踏實地、精益求真的習(xí)慣；獲取奮發(fā)向上、探索創(chuàng)新的精神動力。4講授式討論式練習(xí)式課程目標(biāo)1課程目標(biāo)2課程目標(biāo)35回溯法：回溯法的算法框架；裝載問題；批處理作業(yè)調(diào)度；符號三角形問題；n后問題；0-1背包問題；最大團問題；圖的m著色問題；旅行售貨員問題；圓排列問題；電路板排列問題；連續(xù)郵資問題；回溯法的效率分析。理解回溯法的基本思想及效率估計，限界函數(shù)；掌握回溯法在典型問題的應(yīng)用及分析。德育要求：樹立愛國情懷、文化自信；獲取奮發(fā)向上、探索創(chuàng)新的精神動力。4講授式啟發(fā)式探究式討論式練習(xí)式課程目標(biāo)1課程目標(biāo)2課程目標(biāo)36分支限界法：分支限界法的基本思想；單源最短路徑問題；裝載問題；布線問題；0-1背包問題；最大團問題；旅行售貨員問題；電路板排列問題；批處理作業(yè)調(diào)度。理解分支限界法的基本思想及效率估計；掌握分支限界法的算法框架；掌握分支限界法在典型問題的應(yīng)用。德育要求：體會勤奮學(xué)習(xí)、洞察研究的價值；獲取奮發(fā)向上、探索創(chuàng)新的精神動力。4講授式啟發(fā)式探究式討論式練習(xí)式課程目標(biāo)1課程目標(biāo)2課程目標(biāo)37隨機化算法：隨機數(shù)；數(shù)值隨機化算法；舍伍德(Sherwood)算法；拉斯維加斯(LasVegas)算法；蒙特卡羅(MonteCarlo)算法。理解產(chǎn)生偽隨機數(shù)的算法；掌握數(shù)值概率算法的設(shè)計思想；掌握蒙特卡羅算法、拉斯維加斯算法和舍伍德算法的設(shè)計思想。德育要求：堅定家國情懷和助力中國夢的信念；獲取奮發(fā)向上、探索創(chuàng)新的精神動力。4講授式啟發(fā)式探究式討論式練習(xí)式課程目標(biāo)1課程目標(biāo)2課程目標(biāo)38線性規(guī)劃與網(wǎng)絡(luò)流：線性規(guī)劃問題和單純形算法；最大網(wǎng)絡(luò)流問題；最小費用流問題。理解線性規(guī)劃算法的模型，理解網(wǎng)絡(luò)與網(wǎng)絡(luò)流的基本概念；掌握線性規(guī)劃問題的單純形算法；掌握網(wǎng)絡(luò)最大流的增廣路算法與預(yù)流推進算法；掌握網(wǎng)絡(luò)最小費用流的消圈算法、最小費用路算法與單純形算法。德育要求：樹立正確的世界觀、價值觀、人生觀；獲取奮發(fā)向上、探索創(chuàng)新的精神動力。4講授式啟發(fā)式探究式討論式練習(xí)式課程目標(biāo)1課程目標(biāo)2課程目標(biāo)3合計32序號實驗項目實驗內(nèi)容與要求學(xué)時類型對應(yīng)課程目標(biāo)1遞歸與分治策略實驗內(nèi)容：（1）遞歸算法；（2）分治算法；（3）用遞歸和分治算法求解問題。實驗要求：必修。6設(shè)計課程目標(biāo)1課程目標(biāo)2課程目標(biāo)32動態(tài)規(guī)劃法實驗內(nèi)容：（1）動態(tài)規(guī)劃基本要素；（2）設(shè)計動態(tài)規(guī)劃算法的步驟；（3）用動態(tài)規(guī)劃算法求解問題。實驗要求：必修。4設(shè)計課程目標(biāo)1課程目標(biāo)2課程目標(biāo)33貪心算法實驗內(nèi)容：（1）貪心算法基本要素；（2）貪心設(shè)計策略；（3）用貪心算法求解問題。實驗要求：必修。4設(shè)計課程目標(biāo)1課程目標(biāo)2課程目標(biāo)34回溯法實驗內(nèi)容：（1）回溯法基本框架；（2）回溯法設(shè)計策略；（3）用回溯法求解問題。實驗要求：必修。4設(shè)計課程目標(biāo)1課程目標(biāo)2課程目標(biāo)35分支限界法實驗內(nèi)容：（1）分支限界法的基本思想；（2）剪枝搜索策略；（3）分支限界法基本框架。（4）用分支限界法求解問題。實驗要求：必修。4設(shè)計課程目標(biāo)1課程目標(biāo)2課程目標(biāo)36隨機化算法實驗內(nèi)容：（1）偽隨機數(shù)生成算法；（2）隨機算法的設(shè)計思想；（3）用蒙特卡羅算法求解問題。實驗要求：必修。4設(shè)計課程目標(biāo)1課程目標(biāo)2課程目標(biāo)37線性規(guī)劃與網(wǎng)絡(luò)流實驗內(nèi)容：（1）線性規(guī)劃問題與單純形算法；（2）最大網(wǎng)絡(luò)流問題求解算法；（3）最小費用流問題求解算法。實驗要求：必修。6綜合課程目標(biāo)1課程目標(biāo)2課程目標(biāo)3合計32四、課程教學(xué)方法課堂講授與小組討論相結(jié)合；集中講授與探究式教學(xué)及翻轉(zhuǎn)課堂相結(jié)合；采用講授式、啟發(fā)式、探究式、討論式和練習(xí)式等教學(xué)方式。五、學(xué)業(yè)評價和課程考核（一）考核方式及具體要求序號考核方式課程目標(biāo)1（分值）課程目標(biāo)2（分值）課程目標(biāo)3（分值）合計1平時作業(yè)244102課程實驗253103課堂表現(xiàn)253104期末考試15352070課程目標(biāo)對應(yīng)分值214930100（二）考核與評價標(biāo)準(zhǔn)1.平時作業(yè)考核與評價標(biāo)準(zhǔn)分值觀測點90-100分70-89分60-69分0-59分作業(yè)按時完成，90%以上的作業(yè)內(nèi)容齊全，基本知識點理解、掌握到位。能夠利用理論知識設(shè)計算法求解具體問題并分析算法復(fù)雜度。按時完成，70%以上的作業(yè)內(nèi)容齊全，基本知識點理解、掌握得較為到位。能夠較好地利用理論知識設(shè)計算法求解具體問題并分析算法復(fù)雜度。延時完成，60%以上作業(yè)內(nèi)容齊全，基本知識點理解、掌握得基本到位?；灸軌蚶美碚撝R設(shè)計算法求解具體問題并分析算法復(fù)雜度。不交和補交，50%以下作業(yè)內(nèi)容齊全，基本知識點理解、掌握有偏差?；静荒芾美碚撝R設(shè)計算法求解具體問題并分析算法復(fù)雜度。2.課程實驗考核與評價標(biāo)準(zhǔn)分值觀測點90-100分70-89分60-69分0-59分課程實驗?zāi)芨鶕?jù)實驗要求自主設(shè)計實驗方案，有自己的設(shè)計理念，實驗完成度高，效果好。算法復(fù)雜度分析正確。實驗報告內(nèi)容完整。能根據(jù)實驗要求自主設(shè)計實驗方案，有自己的設(shè)計理念，實驗完成度較高，效果較好。算法復(fù)雜度分析比較正確。實驗報告比較完整。能根據(jù)實驗要求自主設(shè)計實驗方案，實驗完成度一般，效果一般。算法復(fù)雜度分析基本正確。實驗報告基本完整?；灸芨鶕?jù)實驗要求自主設(shè)計實驗方案，實驗完成度較差，效果較差。算法復(fù)雜度分析不正確。實驗報告不完整。3.線下表現(xiàn)與評價標(biāo)準(zhǔn)根據(jù)回答問題、課堂表現(xiàn)及團隊合作等情況及評分標(biāo)準(zhǔn)評分（百分制）。4.期末考試與評價標(biāo)準(zhǔn)根據(jù)期末考試及評分標(biāo)準(zhǔn)評分（百分制）。六、教材與參考書（一）推薦教材《計算機算法設(shè)計與分析（第5版）》，王曉東主編，電子工業(yè)出版社，2018年8月版。（二