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

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