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

《算法設(shè)計(jì)與分析》課程教學(xué)大綱一、課程基本信息課程名稱算法設(shè)計(jì)與分析課程代碼課程類型專業(yè)核心課程授課語(yǔ)言中文開課學(xué)院網(wǎng)絡(luò)安全學(xué)院開課年級(jí)二年級(jí)/三年級(jí)面向?qū)I(yè)網(wǎng)絡(luò)安全、信息安全、密碼學(xué)總學(xué)分2.5理論學(xué)分2實(shí)踐學(xué)分0.5總學(xué)時(shí)44理論學(xué)時(shí)32實(shí)踐學(xué)時(shí)12先修課程名稱離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)后續(xù)課程名稱無(wú)主要教材《算法設(shè)計(jì)與應(yīng)用》林海，曹越，陳治宏著，機(jī)械工業(yè)出版社，ISBN9787111761464參考書目《算法導(dǎo)論（原書第3版）》，ThomasH.Cormen等著，殷建平等翻譯，機(jī)械工業(yè)出版社，ISBN9787111407010課程負(fù)責(zé)人及團(tuán)隊(duì)成員角色姓名所在單位職稱課程中承擔(dān)任務(wù)電子郵箱負(fù)責(zé)人林海國(guó)家網(wǎng)絡(luò)安全學(xué)院副教授理論課授課lin.hai@成員李雨晴國(guó)家網(wǎng)絡(luò)安全學(xué)院副研究員理論課授課li.yuqing@成員張子君國(guó)家網(wǎng)絡(luò)安全學(xué)院副研究員理論課授課zijunzhang@成員蔡波國(guó)家網(wǎng)絡(luò)安全學(xué)院副教授理論課授課caib@二、課程目標(biāo)（提示：結(jié)合本校辦學(xué)定位、培養(yǎng)目標(biāo)及人才培養(yǎng)方案，對(duì)學(xué)生學(xué)習(xí)本課程后應(yīng)習(xí)得的價(jià)值觀、專業(yè)知識(shí)以及應(yīng)用相關(guān)知識(shí)的能力水平等方面進(jìn)行闡述。400字以內(nèi)。）1.價(jià)值觀塑造方面1）培養(yǎng)學(xué)生的邏輯思維和數(shù)學(xué)素養(yǎng)，讓學(xué)生能夠用嚴(yán)謹(jǐn)、清晰、有效的方式表達(dá)和解決問題，形成科學(xué)、理性、客觀的價(jià)值取向。2）培養(yǎng)學(xué)生的創(chuàng)新思維和探索精神，讓學(xué)生能夠在不同情境中發(fā)現(xiàn)問題、提出問題、解決問題，形成創(chuàng)造、主動(dòng)、積極的價(jià)值取向。3）培養(yǎng)學(xué)生的合作思維和社會(huì)責(zé)任感，讓學(xué)生能夠在團(tuán)隊(duì)中分享知識(shí)、交流想法、協(xié)作解決問題，形成合作、包容、公益的價(jià)值取向。2.知識(shí)獲得方面1）學(xué)習(xí)算法設(shè)計(jì)的常用方法，包括分治、動(dòng)態(tài)規(guī)劃、貪心、回溯與分支限界等算法。2）學(xué)習(xí)算法分析的理論工具，能夠分析算法的運(yùn)行時(shí)間，了解算法的效率估計(jì)、改進(jìn)途徑、計(jì)算復(fù)雜度、難解問題等重要內(nèi)容。3）學(xué)習(xí)對(duì)簡(jiǎn)單計(jì)算問題的建模、分析、算法設(shè)計(jì)、算法優(yōu)化和編程求解。3.能力培養(yǎng)方面1）培養(yǎng)學(xué)生分析問題和解決問題的能力，課程通過對(duì)算法的設(shè)計(jì)和分析，培養(yǎng)學(xué)生分析問題和解決問題的能力。2）增強(qiáng)學(xué)生創(chuàng)新能力，通過本課程的學(xué)習(xí)，了解經(jīng)典和前沿算法的思想和技巧，從而激發(fā)學(xué)生的創(chuàng)新思維，培養(yǎng)創(chuàng)新精神。三、課程簡(jiǎn)介（400字以內(nèi)）算法是計(jì)算機(jī)最核心的內(nèi)容，計(jì)算機(jī)科學(xué)也被稱為算法科學(xué)。本課程主要通過介紹常見的算法設(shè)計(jì)策略及復(fù)雜性分析方法，培養(yǎng)學(xué)生分析問題和解決問題的能力，為開發(fā)高效的軟件系統(tǒng)及參加相關(guān)領(lǐng)域的研究工作奠定堅(jiān)實(shí)的基礎(chǔ)。該課程理論與實(shí)踐并重，內(nèi)容具有綜合性、廣泛性和系統(tǒng)性，是一門集應(yīng)用性、創(chuàng)造性及實(shí)踐性為一體的綜合性極強(qiáng)的課程，通過對(duì)本課程的學(xué)習(xí)，學(xué)生需要掌握遞歸與分治、動(dòng)態(tài)規(guī)劃、貪心算法、回溯等基本的算法，并能將這些算法應(yīng)用到實(shí)際中來(lái)解決實(shí)際問題。課程通過線上和線下相結(jié)合的方式進(jìn)行教學(xué)。課前，通過線上課程視頻預(yù)習(xí)相關(guān)知識(shí)點(diǎn)，做到對(duì)知識(shí)點(diǎn)知其然；課中，通過互動(dòng)式教學(xué)，讓學(xué)生知其然，也知其所以然；課后，通過視頻復(fù)習(xí)，線上答疑，代碼開發(fā)等方式讓學(xué)生對(duì)所學(xué)知識(shí)進(jìn)一步鞏固。四、教學(xué)理念（提示：結(jié)合課程的專業(yè)定位、價(jià)值目標(biāo)、內(nèi)容與特色，挖掘其中的課程思政元素，重視培養(yǎng)學(xué)生的馬克思主義的世界觀與方法論、深厚的人文素養(yǎng)與嚴(yán)謹(jǐn)?shù)目茖W(xué)精神等，實(shí)現(xiàn)“成人”教育和“成才”教育的有機(jī)結(jié)合。300字以內(nèi)。）算法設(shè)計(jì)與分析課程的教學(xué)目的是讓學(xué)生掌握算法設(shè)計(jì)的基本技巧和方法，能夠分析算法的復(fù)雜性，根據(jù)不同的場(chǎng)景設(shè)計(jì)算法解決一些較綜合的問題。從而培養(yǎng)學(xué)生的創(chuàng)新思維和探索精神，提高學(xué)生的素質(zhì)和能力，為學(xué)生的專業(yè)發(fā)展和社會(huì)服務(wù)打下堅(jiān)實(shí)的基礎(chǔ)。通過激發(fā)學(xué)生的主動(dòng)學(xué)習(xí)興趣，培養(yǎng)他們的獨(dú)立思考和問題解決能力，實(shí)現(xiàn)"成人"教育的目標(biāo)。通過實(shí)際的問題和項(xiàng)目，讓學(xué)生應(yīng)用所學(xué)知識(shí)，培養(yǎng)他們的實(shí)際技能和創(chuàng)新能力，實(shí)現(xiàn)"成才"教育的目標(biāo)。同時(shí)，課程教學(xué)強(qiáng)調(diào)算法課程的社會(huì)價(jià)值和科學(xué)性，教育學(xué)生如何運(yùn)用馬克思主義的辯證唯物主義世界觀和方法論來(lái)分析和理解計(jì)算機(jī)科學(xué)領(lǐng)域中的問題。五、課程設(shè)計(jì)章節(jié)教學(xué)內(nèi)容學(xué)時(shí)教學(xué)方式與方法對(duì)應(yīng)的課程目標(biāo)1算法概念、復(fù)雜度分析、堆和不相交集數(shù)據(jù)結(jié)構(gòu)4課堂講授、課堂討論1.掌握什么是算法,算法能解決什么，算法的特征等基本概念；2.掌握時(shí)間復(fù)雜度分析和空間復(fù)雜度分析掌握堆和不相交集。2排序算法及其復(fù)雜度2課堂講授、課堂討論1.掌握基于比較的排序算法；2.掌握非比較的排序算法；3.重點(diǎn)通過排序算法進(jìn)行復(fù)雜度分析。3遞歸3課堂講授、課堂討論1.掌握遞歸的概念，通過遞歸的方式實(shí)現(xiàn)搜索、排序、整數(shù)劃分等問題；2.掌握復(fù)雜度的遞歸求解方法，如代入法、遞歸式方法、主方法。4分治5課堂講授、課堂討論1.理解分治的基本方法（分解、解決、合并）；2.掌握用分治解決最大子數(shù)組、最近點(diǎn)對(duì)、尋找第k小元素等問題；2.分治復(fù)雜度分析。5動(dòng)態(tài)規(guī)劃6課堂講授、課堂討論1.理解動(dòng)態(tài)規(guī)劃原理，基本步驟；2.掌握用動(dòng)態(tài)規(guī)劃解決最大子數(shù)組、0-1背包、旅行商等問題；3.掌握狀態(tài)壓縮動(dòng)態(tài)規(guī)劃方法。6貪心算法6課堂講授、課堂討論1.通過將動(dòng)態(tài)規(guī)劃和貪心算法進(jìn)行比較，理解貪心算法的基本概念和原理；2.掌握貪心算法的原理，基本步驟；3.掌握用貪心算法解決小數(shù)背包和0-1背包問題、最小生成樹問題、霍夫曼編碼問題。7圖算法6課堂講授、課堂討論1.掌握深度優(yōu)先搜索、廣度優(yōu)先搜索；2.掌握?qǐng)D算法的應(yīng)用；3.掌握單源最短路徑，多源最短路徑算法。8回溯和分支限界6課堂講授、課堂討論1.理解回溯和分支限界的基本概念、通用方法；2.理解狀態(tài)空間樹；3.掌握回溯和分支限界的相同點(diǎn)和不同點(diǎn)，用這兩個(gè)算法求解單源最短路徑、0-1背包、旅行商問題、任務(wù)分配等問題。9匹配與指派6課堂講授、課堂討論1.掌握基于圖的匈牙利算法；2