1、算法設(shè)計(jì)與分析教學(xué)大綱一、基本信息英文名稱：Design and Analysis of Algorithms課程編號(hào)：063210845課程類別：專業(yè)課課程性質(zhì)：必修課學(xué)時(shí)：48（理論學(xué)時(shí)：48） 學(xué)分：3適用對(duì)象：計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)先修課程：C語(yǔ)言程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)開課單位：計(jì)算機(jī)學(xué)院使用教材：1 王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析.北京：電子工業(yè)出版社，2016主要參考書：1Anany Levitin(美). 算法設(shè)計(jì)與分析基礎(chǔ).北京：清華大學(xué)出版社，20152屈婉玲.算法設(shè)計(jì)與分析.北京：清華大學(xué)出版社，20113盧開澄.計(jì)算機(jī)算法導(dǎo)引.北京：清華大學(xué)出版社，2000二、教學(xué)目標(biāo)算法與設(shè)計(jì)

2、分析是一門面向算法設(shè)計(jì)，且是計(jì)算機(jī)類專業(yè)一門綜合性較強(qiáng)的專業(yè)必修課。使學(xué)生具備利用算法設(shè)計(jì)解決復(fù)雜計(jì)算機(jī)及軟件工程問題，具備針對(duì)算法復(fù)雜性進(jìn)行綜合分析的能力，培養(yǎng)學(xué)生程序邏輯思維能力和綜合設(shè)計(jì)能力。本課程的教學(xué)目的是培養(yǎng)學(xué)生學(xué)會(huì)從問題入手，運(yùn)用計(jì)算機(jī)專業(yè)基礎(chǔ)知識(shí)、核心理論和方法，分析和研究計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)、軟件結(jié)構(gòu)和應(yīng)用軟件中解決問題的算法，使學(xué)生能夠在復(fù)雜工程問題應(yīng)用中為算法選取適當(dāng)?shù)脑O(shè)計(jì)策略，同時(shí)對(duì)算法所需的時(shí)間和空間進(jìn)行分析。通過對(duì)常用的、有代表性的算法的研究，讓學(xué)生理解并掌握算法設(shè)計(jì)的基本方法，培養(yǎng)學(xué)生分析算法復(fù)雜度的初步能力，鍛煉其邏輯思維能力和想象力，并使之了解算法理論的發(fā)展。使學(xué)生

3、學(xué)會(huì)分析算法、選擇算法、設(shè)計(jì)算法，養(yǎng)成良好的程序設(shè)計(jì)風(fēng)格，即能夠綜合運(yùn)用算法設(shè)計(jì)與分析的思想，解決實(shí)際問題。使學(xué)生具有運(yùn)用算法知識(shí)解決實(shí)際問題、獨(dú)立科研和理論聯(lián)系實(shí)際的能力。課程目標(biāo)及能力要求具體如下：課程目標(biāo)1：掌握NP完全理論、遞歸與分治策略、動(dòng)態(tài)規(guī)劃、貪心算法、回溯法以及分支限界法解決問題的基本思想，能夠準(zhǔn)確地分析棋盤覆蓋、線性時(shí)間選擇、最接近點(diǎn)對(duì)問題、最長(zhǎng)公共子序列、0-1背包問題、哈夫曼編碼、旅行售貨員、單源最短路徑、最大團(tuán)等典型算法的效率及穩(wěn)定性，對(duì)解決方案的算法進(jìn)行時(shí)間復(fù)雜度的分析、評(píng)價(jià)和改進(jìn)。課程目標(biāo)2：將實(shí)際問題抽象為計(jì)算機(jī)語(yǔ)言表達(dá)是算法實(shí)現(xiàn)的重要一環(huán)，能夠熟練地將解決問題的

4、文字描述中的指標(biāo)進(jìn)行參數(shù)化，將解決方案進(jìn)行數(shù)學(xué)模型化，能夠培養(yǎng)學(xué)生更好的利用計(jì)算機(jī)程序設(shè)計(jì)思想去分析實(shí)際問題的能力。課程目標(biāo)3：培養(yǎng)學(xué)生綜合分析較為復(fù)雜類型問題的能力，鍛煉其邏輯思維能力和想象力。通過熟練掌握基礎(chǔ)算法的基本理論，比較分析并總結(jié)各個(gè)類型算法的優(yōu)缺點(diǎn)。特別是針對(duì)某一給定的解決問題，學(xué)生能夠根據(jù)實(shí)際問題的特定需求，選擇和利用合理的算法類型給出最優(yōu)方案，并對(duì)解決方案進(jìn)行分析、評(píng)價(jià)和改進(jìn)。表1 課程目標(biāo)對(duì)畢業(yè)要求的支撐關(guān)系畢業(yè)要求畢業(yè)要求指標(biāo)點(diǎn)課程目標(biāo)對(duì)畢業(yè)要求的支撐關(guān)系1.工程知識(shí)1-4專業(yè)知識(shí)能夠?qū)⒂?jì)算機(jī)算法設(shè)計(jì)與分析的專業(yè)知識(shí)用于計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)、軟件設(shè)計(jì)和應(yīng)用軟件等復(fù)雜軟件工程問題

5、解決方案的分析、評(píng)價(jià)和改進(jìn)。課程目標(biāo)12.問題分析2-2問題表述能夠應(yīng)用算法分析的原理和方法，將實(shí)際的復(fù)雜軟件工程問題表述為計(jì)算機(jī)可識(shí)別的數(shù)據(jù)模型。課程目標(biāo)23.設(shè)計(jì)/開發(fā)解決方案3-1解決方案構(gòu)思能夠運(yùn)用計(jì)算機(jī)算法設(shè)計(jì)與分析的專業(yè)知識(shí)，確定解決復(fù)雜軟件工程問題的基本思路和方案。課程目標(biāo)3三、課程內(nèi)容、教學(xué)要求及評(píng)價(jià)方式1.課程內(nèi)容、要求與評(píng)價(jià)方式通過指導(dǎo)學(xué)生學(xué)習(xí)與課程目標(biāo)相對(duì)應(yīng)的課程內(nèi)容，實(shí)現(xiàn)課程目標(biāo)的達(dá)成。評(píng)價(jià)方式包括：平時(shí)作業(yè)、課堂測(cè)驗(yàn)、期末試題。各課程目標(biāo)的教學(xué)方式與評(píng)價(jià)方式詳見表2。表2 課程知識(shí)單元、要求與評(píng)價(jià)方式對(duì)應(yīng)關(guān)系表序號(hào)知識(shí)單元知識(shí)點(diǎn)教學(xué)要求教學(xué)方式評(píng)價(jià)方式推薦學(xué)時(shí)支撐課程

6、目標(biāo)1算法概述算法的概念，計(jì)算復(fù)雜性1. 理解算法的概念2. 掌握算法在最壞情況、最好情況和平均情況下的計(jì)算復(fù)雜性概念3. 掌握算法復(fù)雜性的漸進(jìn)性態(tài)分析4.了解NP類問題的基本概念講授期末考試212遞歸與分治策略遞歸與分治策略與設(shè)計(jì)技巧1. 掌握遞歸的概念、分治法的基本思想2. 掌握二分搜索技術(shù)、大整數(shù)的乘法、矩陣乘法、棋盤覆蓋、合并排序、快速排序、線性時(shí)間選擇和最接近點(diǎn)等典型分治算法的基本原理。講授課后作業(yè)；期末考試413遞歸與分治策略分治法的數(shù)學(xué)模型化分析1. 根據(jù)特定解決問題進(jìn)行參數(shù)化、數(shù)學(xué)模型化、程序化和時(shí)間復(fù)雜度分析。講授期末考試324遞歸與分治策略遞歸與分治算法綜合分析1. 分治法

7、與遞歸的關(guān)系分析2. 基于分治法的綜合比較分析講授期末考試135遞歸與分治策略分治算法綜合設(shè)計(jì)1. 愛因斯坦的思考題討論專題236動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)思想、適用性及算法設(shè)計(jì)要點(diǎn)1. 掌握矩陣連乘問題、動(dòng)態(tài)規(guī)劃算法要素2. 掌握最長(zhǎng)公共子序列、最大子段和、多邊形最優(yōu)三角剖分、多邊形游戲、0-1背包問題、最優(yōu)二叉搜索樹等典型動(dòng)態(tài)規(guī)劃算法的基本原理。講授課后作業(yè)；期末考試417動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型化分析1. 根據(jù)特定解決問題進(jìn)行參數(shù)化、數(shù)學(xué)模型化、程序化和時(shí)間復(fù)雜度分析。講授期末考試328動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃算法比較分析1. 基于動(dòng)態(tài)規(guī)劃算法的綜合比較分析講授期末考試139動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃算

8、法綜合設(shè)計(jì)1. 高并發(fā)狀態(tài)下的負(fù)載均衡問題討論專題2310貪心算法貪心算法設(shè)計(jì)策略、一般理論，與動(dòng)態(tài)規(guī)范算法的差異1. 掌握活動(dòng)安排問題、貪心算法的基本要素2.掌握最優(yōu)裝載、哈夫曼編碼、單源最短路徑、最小生成樹和多機(jī)調(diào)度等典型貪心算法的基本原理。講授課后作業(yè)；期末考試4111貪心算法貪心算法的數(shù)學(xué)模型化分析1. 根據(jù)特定解決問題進(jìn)行參數(shù)化、數(shù)學(xué)模型化、程序化和時(shí)間復(fù)雜度分析。講授期末考試3212貪心算法貪心算法比較分析1. 貪心算法與動(dòng)態(tài)規(guī)劃算法的比較分析講授期末考試1313貪心算法綜合訓(xùn)練1. 綜合測(cè)試考試并課堂詳解測(cè)驗(yàn)課堂測(cè)驗(yàn)2314回溯法回溯法的算法框架、設(shè)計(jì)策略，深度優(yōu)先搜索策略掌握回

9、溯法的算法框架掌握裝載問題、批處理作業(yè)調(diào)度、n后問題、0-1背包問題、最大團(tuán)問題、m著色問題、旅行售貨員等典型回溯法算法的基本原理。講授課后作業(yè)；期末考試4115回溯法回溯法的數(shù)學(xué)模型化分析1. 根據(jù)特定解決問題進(jìn)行參數(shù)化、數(shù)學(xué)模型化、程序化和時(shí)間復(fù)雜度分析。講授期末考試2216回溯法回溯法交叉算法的綜合分析1. 回溯法的效率分析2. 裝載問題、0-1背包問題、旅行售貨員等具有典型算法交叉問題的綜合分析與訓(xùn)練。講授期末考試2317分支限界法分支限界法的算法框架、設(shè)計(jì)策略，剪枝搜索策略1. 掌握分支限界法的基本思想2.掌握單源最短路徑問題、裝載問題3.掌握布線問題、0-1背包問題4. 掌握最大團(tuán)

10、問題、旅行售貨員問題5. 掌握電路板排列問題、批處理作業(yè)調(diào)度講授課后作業(yè)；期末考試4118分支限界法分支限界法的數(shù)學(xué)模型化分析1. 根據(jù)特定解決問題進(jìn)行參數(shù)化、數(shù)學(xué)模型化、程序化和時(shí)間復(fù)雜度分析。講授期末考試2219分支限界法分支限界法交叉算法的綜合分析1. 回溯法與分支限界法的比較分析2. 深度優(yōu)先搜索與廣度優(yōu)先搜索問題比較3. 單源最短路徑、0-1背包問題、最大團(tuán)等典型算法交叉問題的綜合分析與訓(xùn)練。講授期末考試23課程評(píng)價(jià)計(jì)算表3 課程目標(biāo)與評(píng)價(jià)依據(jù)占比關(guān)系表評(píng)價(jià)占比課程目標(biāo)評(píng)價(jià)項(xiàng)目課程目標(biāo)1課程目標(biāo)2課程目標(biāo)3課后作業(yè)10100%-專題10-100%課堂測(cè)驗(yàn)10-100%期末考試7060

11、%30%10%合 計(jì)100502030表4 各考核環(huán)節(jié)所占分值比例及考查重點(diǎn)課程成績(jī)構(gòu)成及比例考核環(huán)節(jié)考查點(diǎn)課程目標(biāo)分值課后作業(yè)5次，每次滿分100分，共占總成績(jī)的10%作業(yè)1分治法復(fù)雜性分析的一般推導(dǎo)過程，及其時(shí)間復(fù)雜度的總結(jié)與分類，遞歸算法解決排列、劃分問題。1102動(dòng)態(tài)規(guī)劃的計(jì)算過程和算法思想，如何解決最長(zhǎng)公共子序列、多邊形游戲、0-1背包問題。13貪心算法的設(shè)計(jì)策略，如何解決活動(dòng)安排問題、哈夫曼編碼問題、單源最短路徑問題。14回溯法的基本思想、基本步驟和算法框架，解決裝載問題、0-1背包問題和旅行售貨員問題。150-1背包問題、旅行售貨員問題的多種算法之間的比較。1專題2次，每次滿分1

12、00分，共占總成績(jī)的10%專題1愛因斯坦的思考題3102高并發(fā)狀態(tài)下的負(fù)載均衡問題3課堂測(cè)驗(yàn)1次，滿分100分，共占總成績(jī)的10%課堂測(cè)驗(yàn)1根據(jù)排序、搜索、劃分等實(shí)際問題的特定需求，利用遞歸與分治策略的基本思想、基本步驟和算法框架解決問題。3102根據(jù)最長(zhǎng)公共子序列、0-1背包等實(shí)際問題的特定需求，利用動(dòng)態(tài)規(guī)劃的基本思想、基本步驟和算法框架解決問題。33根據(jù)最優(yōu)裝載、單源最短路徑等實(shí)際問題的特定需求，利用貪心算法的基本思想、基本步驟和算法框架解決問題。3期末考試100分，占總成績(jī)的70%期末考試1綜合考核學(xué)生利用遞歸與分治策略、動(dòng)態(tài)規(guī)劃、貪心算法回溯法、分支限界法等算法解決問題時(shí)所需的基本知識(shí)

13、、基本理論和基本技能，對(duì)實(shí)踐性和應(yīng)用性問題的解決方案進(jìn)行分析、評(píng)價(jià)和改進(jìn)?？荚囶}型可為判斷對(duì)錯(cuò)題、選擇題、填空題、簡(jiǎn)答題等。1702綜合考核學(xué)生利用遞歸與分治策略、動(dòng)態(tài)規(guī)劃、貪心算法、回溯法、分支限界法等算法對(duì)解決問題進(jìn)行參數(shù)化、模型化和程序化分析。考試題型可為判斷對(duì)錯(cuò)題、選擇題、填空題、簡(jiǎn)答題等。23綜合考核學(xué)生利用遞歸與分治策略、動(dòng)態(tài)規(guī)劃、貪心算法、回溯法和分支限界法解決實(shí)際問題的基本思路和方案，學(xué)生能夠根據(jù)實(shí)際問題的特定需求，選擇和利用合理的算法類型給出最優(yōu)方案?？荚囶}型可為判斷對(duì)錯(cuò)題、選擇題、填空題、簡(jiǎn)答題等。3五、考核方式與成績(jī)?cè)u(píng)定辦法考核方式：課后作業(yè)（10%），專題（10%），課

14、堂測(cè)驗(yàn)（10%），期末考試（70%）。成績(jī)?cè)u(píng)定辦法如下所示。課后作業(yè)評(píng)分標(biāo)準(zhǔn)觀測(cè)點(diǎn)17 - 20分13 - 16分9 - 12分5 - 8分0 - 4分得分內(nèi)容完整性（權(quán)重0.2）書寫工整、清晰，有完整的解題過程書寫工整、清晰，解題無(wú)明顯過程缺失書寫較工整、較清晰，解題無(wú)明顯過程缺失書寫較工整、較清晰，解題有明顯過程缺失書寫不工整、不清晰，無(wú)解題過程20正確性（權(quán)重0.2）采用的算法設(shè)計(jì)合理，結(jié)果準(zhǔn)確采用的算法設(shè)計(jì)合理，結(jié)果有偏差采用的算法設(shè)計(jì)合理，結(jié)果錯(cuò)誤采用的算法設(shè)計(jì)較合理，結(jié)果有偏差采用的算法設(shè)計(jì)不合理，結(jié)果錯(cuò)誤20邏輯性和創(chuàng)新性（權(quán)重0. 2）算法的設(shè)計(jì)思想邏輯結(jié)構(gòu)嚴(yán)謹(jǐn)、有一定的創(chuàng)新性

15、算法的設(shè)計(jì)思想邏輯結(jié)構(gòu)較嚴(yán)謹(jǐn)、有一定的創(chuàng)新性算法的設(shè)計(jì)思想邏輯結(jié)構(gòu)基本明確、有一定的創(chuàng)新性算法的設(shè)計(jì)思想邏輯結(jié)構(gòu)較混亂、有一定的創(chuàng)新性算法的設(shè)計(jì)思想邏輯結(jié)構(gòu)不完整層次混亂、無(wú)創(chuàng)新性20基本思想掌握程度（權(quán)重0.2）完全地掌握算法設(shè)計(jì)的基本思想，并能夠靈活運(yùn)用較為完全地掌握算法設(shè)計(jì)的基本思想，并能夠靈活運(yùn)用較為完全地掌握算法設(shè)計(jì)的基本思想，但不能夠靈活運(yùn)用基本掌握算法設(shè)計(jì)的基本思想，但不能夠靈活運(yùn)用沒有掌握算法設(shè)計(jì)的基本思想，更不能能夠靈活運(yùn)用20解決問題的能力（權(quán)重0.2）能自主地、主動(dòng)地謀求解決問題的規(guī)劃、方法和步驟，并合理地、有效地解決問題能自主地、主動(dòng)地謀求解決問題的規(guī)劃、方法和步驟，并

16、較合理地、較有效地解決問題能自主地、主動(dòng)地謀求解決問題的規(guī)劃、方法和步驟，只能解決部分問題不能自主地、主動(dòng)地謀求解決問題的規(guī)劃、方法和步驟，但能解決問題不能自主地、主動(dòng)地謀求解決問題的規(guī)劃、方法和步驟，且不能解決問題20合計(jì)100專題評(píng)分標(biāo)準(zhǔn)觀測(cè)點(diǎn)100分0 - 99分得分準(zhǔn)確性（權(quán)重0.4）解決方案所使用的算法的邏輯結(jié)構(gòu)和實(shí)現(xiàn)結(jié)果準(zhǔn)確算法邏輯混亂不得分40合理性（權(quán)重0.4）解決方案的整體設(shè)計(jì)方案和框架合理算法設(shè)計(jì)不合理不得分40新穎性（權(quán)重0.2）算法設(shè)計(jì)新穎算法直接抄襲不得分20合計(jì)100課堂測(cè)驗(yàn)評(píng)分標(biāo)準(zhǔn)觀測(cè)點(diǎn)100分0 - 99分得分解決問題的準(zhǔn)確性（權(quán)重1）主觀題型的判分點(diǎn)無(wú)錯(cuò)誤，結(jié)果準(zhǔn)確，書寫工整，字跡清晰主觀題按照步驟判分點(diǎn)以及結(jié)果的準(zhǔn)確性得分，字跡模糊不清導(dǎo)致結(jié)果無(wú)法識(shí)別的按判分點(diǎn)錯(cuò)誤不得分100合計(jì)100期末考試評(píng)分標(biāo)準(zhǔn)觀測(cè)點(diǎn)100分0 - 99分得分解決問題的準(zhǔn)確性（權(quán)重1）客觀題按照標(biāo)準(zhǔn)答案無(wú)錯(cuò)誤；主觀題按照步驟判分點(diǎn)無(wú)錯(cuò)誤，結(jié)果準(zhǔn)確，書寫工整，字跡清晰客觀題按照標(biāo)準(zhǔn)答案對(duì)的得分，錯(cuò)誤的不得分；主觀題按照步驟判分點(diǎn)以及結(jié)果的準(zhǔn)確性得分。字跡模糊不清導(dǎo)致結(jié)果無(wú)法識(shí)別的按判分點(diǎn)錯(cuò)誤不得分100合計(jì)100附件：課程達(dá)成度評(píng)價(jià)計(jì)算附表1 課程評(píng)價(jià)考核基本信息表課程目標(biāo)評(píng)價(jià)內(nèi)容課后作業(yè)(A)專題（B）課堂測(cè)驗(yàn)(C)期末考試(D)課程總評(píng)成績(jī)?cè)诰€作業(yè)紙質(zhì)方案