《高級(jí)算法設(shè)計(jì)》課程教學(xué)大綱

《高級(jí)算法設(shè)計(jì)與分析》課程教學(xué)大綱課程中文名稱:高級(jí)算法設(shè)計(jì)課程英文名稱：Advancedalgorithmdesignandanalysis課程類別：通開課課程學(xué)分?jǐn)?shù)：2課程學(xué)時(shí)數(shù)：32授課對(duì)象：計(jì)算機(jī)和網(wǎng)絡(luò)安全專業(yè)碩士研究生一．課程性質(zhì)《高級(jí)算法設(shè)計(jì)》是計(jì)算機(jī)專業(yè)和網(wǎng)絡(luò)安全專業(yè)碩士研究生的一門學(xué)科通開課。二、教學(xué)目的與要求本課程是對(duì)本科課程《算法設(shè)計(jì)與分析》的擴(kuò)展和提高，其是支撐網(wǎng)絡(luò)空間安全一級(jí)學(xué)科的基礎(chǔ)課程。算法是計(jì)算機(jī)最核心的內(nèi)容，計(jì)算機(jī)科學(xué)也被稱為算法科學(xué)。通過(guò)本科學(xué)習(xí)，學(xué)生已經(jīng)掌握了分治、動(dòng)態(tài)規(guī)劃、回溯等基本算法，本課程在這些算法的基礎(chǔ)上進(jìn)一步培養(yǎng)學(xué)生的算法設(shè)計(jì)和分析能力，培養(yǎng)學(xué)生“時(shí)間高效和空間高效地”解決實(shí)際問題思維習(xí)慣和動(dòng)手能力，進(jìn)一步提高學(xué)生的算法修養(yǎng)。本課程詳細(xì)講授了線性規(guī)劃、NP完全性理論、近似算法、隨機(jī)算法和啟發(fā)式算法等方面的相關(guān)知識(shí)，同時(shí)通過(guò)對(duì)各種算法的設(shè)計(jì)分析，使碩士研究生掌握各種算法原理的同時(shí)理解算法的設(shè)計(jì)思想，為將來(lái)學(xué)習(xí)加密算法、安全協(xié)議、人工智能算法打下基礎(chǔ)，同時(shí)能夠在這些領(lǐng)域設(shè)計(jì)新的算法，實(shí)現(xiàn)理論與實(shí)踐的統(tǒng)一。三．教學(xué)內(nèi)容本課程由七大部分組成：（一）線性規(guī)劃(6學(xué)時(shí))1.基本概念2.標(biāo)準(zhǔn)型和松弛型3.圖解法4.單純形法和單純形表5.對(duì)偶：對(duì)偶推導(dǎo)、性質(zhì)，矩陣博弈和對(duì)偶6.原始-對(duì)偶算法7.整數(shù)規(guī)劃及其解法（二）高級(jí)圖算法(5學(xué)時(shí))1．最大流問題2.圖的中心性算法3.社群發(fā)現(xiàn)算法（三）NP完全性問題(5學(xué)時(shí))1．NP完全理論的基本概念2.難解問題與易解問題、判定問題3.NP類與P類4.幾個(gè)NP完全問題:頂點(diǎn)覆蓋、哈密頓回路與貨郎問題、恰好覆蓋、子集和、0-1背包、整數(shù)線性規(guī)劃等（四）近似算法(4學(xué)時(shí))1．近似算法的設(shè)計(jì)思想及分析方法2.旅行商問題的近似解法3.集合覆蓋的近似解法4.斯坦納最小樹近似解法（五）隨機(jī)算法(4學(xué)時(shí))1．隨機(jī)算法概述和基本思想2.隨機(jī)快速排序、選擇3.最小圓覆蓋4.懶惰選擇(LazySelect)5.最小割（六）在線算法(4學(xué)時(shí))1.在線算法基本概念與競(jìng)爭(zhēng)度分析2.確定性在線算法3.隨機(jī)在線算法（七）啟發(fā)式算法(4學(xué)時(shí))1.蟻群算法2.遺傳算法3.模擬退火4.Tabu搜索四.教學(xué)計(jì)劃（包含每個(gè)課時(shí)的授課內(nèi)容等）授課內(nèi)容授課課時(shí)（一）線性規(guī)劃6（二）高級(jí)圖算法5（三）NP完全性問題5（四）近似算法4（五）隨機(jī)算法4（六）在線算法4（七）啟發(fā)式算法4五.課程重點(diǎn)和難點(diǎn)課程的重要知識(shí)點(diǎn)包括：1）線性規(guī)劃的模型建立和求解，線性模型是高級(jí)算法，如近似算法、隨機(jī)算法、在線算法用到的工具；2）高級(jí)圖算法中圖中心性算法，其是圖神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)；3）NPC問題的證明，其是算法問題分類的基礎(chǔ)；4）近似算法中采用對(duì)偶方法求解近似解；5）隨機(jī)算法中的最小割問題，其在圖中有著重要的作用；6）在線算法中的姚極小極大原理，其是衡量最優(yōu)在線算法的重要工具。課程的難點(diǎn)包括：1）線性規(guī)劃的對(duì)偶問題；2）圖算法的社群劃分問題；3）NPC問題的證明；4）近似算法和在線算法的近似度和競(jìng)爭(zhēng)度分析；5）隨機(jī)算法的算法的概率分析。六．教學(xué)方法本課程主要采用教師講授、課堂討論、學(xué)生自學(xué)、課堂練習(xí)及期末考試相結(jié)合的方法，靈活運(yùn)用多種教學(xué)手段，如MOOC課程（B站）、多媒體輔助教學(xué)、課堂互動(dòng)教學(xué)等，同時(shí)注重知識(shí)傳授上的整體性和連貫性，讓學(xué)生能夠從該課程的應(yīng)用領(lǐng)域，逐漸了解到知識(shí)點(diǎn)，最后深入到該領(lǐng)域的知識(shí)體系，通過(guò)課堂練習(xí)和討論，提高學(xué)生的積極性，引導(dǎo)學(xué)生進(jìn)行自主學(xué)習(xí)，提高學(xué)生對(duì)該研究領(lǐng)域的學(xué)習(xí)興趣。七．考核方式期末考試+大作業(yè)（報(bào)告）。八.適用對(duì)象（說(shuō)明此課程的開課對(duì)象是碩士或是博士等）開課對(duì)象：計(jì)算機(jī)和網(wǎng)絡(luò)安全專