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

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