算法分析教學大綱

算法設計與分析DesignandAnalysisofAlgorithms適用范圍：2018本科人才培養(yǎng)方案課程編號：0604808150學分：3學分學時：52學時（其中：講課學時：40；實驗學時：12）開課學期：5先修課程：程序設計基礎、離散數(shù)學、數(shù)據(jù)結(jié)構(gòu)適用專業(yè)：計算機科學與技術(shù)建議教材：《算法設計與分析》，王秋芬等主編，清華大學出版社，2011開課單位：計算機與信息工程學院大綱版本：1一、課程性質(zhì)、任務課程性質(zhì)：算法的設計與分析屬于專業(yè)平臺必修課，是計算機科學的核心問題之一。算法涉及的范圍十分廣泛，不論是從事計算機硬件設計，還是從事計算機軟件設計，都需要認真研究算法。該課程系統(tǒng)地介紹計算機算法的設計方法與分析技巧，通過課程學習，為獨立地設計算法和對算法進行分析奠定堅實的知識基礎，對從事計算機軟件和計算機應用的研究者來說是非常重要和必不可少的。課程任務：通過學習該課程，使學生在知識方面要求：掌握算法的定義及基本概念、計算模型和復雜度的衡量；為分析算法的復雜性做準備，要了解相應的數(shù)學知識；掌握算法設計的過程和方法；掌握算法的時間復雜度、空間復雜度和穩(wěn)定性的分析；具有問題抽象和建模的初步能力。在能力方面要求：通過本課程的學習，學生要掌握幾種常用的算法設計策略，包括遞歸與分治策略、動態(tài)規(guī)劃算法、貪心算法、回溯法、分支限界法概率算法、線性規(guī)劃和網(wǎng)絡流法和NP完全性理論與近似算法等，并會分析算法的效率，能夠用所學方法解決實際問題。算法設計與分析能夠有效鍛煉學生的邏輯思維能力和想象力，更重要的是培養(yǎng)學生的創(chuàng)造性思維能力；培養(yǎng)學生在理論的指導下，分析、解決實際問題的能力。這正是計算機科學與技術(shù)專業(yè)培養(yǎng)目標的核心所在。二、課程目標（一）課程具體目標目標1：掌握算法設計與分析的專業(yè)知識，具有應用數(shù)學、算法及計算機的基本原理，能將其用于計算機復雜工程問題模型的實現(xiàn)。目標2：能基于算法設計與分析的專業(yè)知識，具備針對計算機應用領域復雜工程問題的關(guān)鍵環(huán)節(jié)進行分析、設計及優(yōu)化等工程實踐活動的能力；目標3：針對計算機復雜工程問題，能夠基于算法設計與分析方法，通過調(diào)研和分析，設計合適的研究方案。（二）課程目標與專業(yè)畢業(yè)要求的關(guān)系本課程對專業(yè)畢業(yè)要求及其指標點的支撐課程目標支撐的畢業(yè)要求支撐的畢業(yè)要求指標點目標1畢業(yè)要求1：能夠?qū)?shù)學、自然科學、工程基礎和計算機科學與技術(shù)專業(yè)知識用于解決計算機工程領域內(nèi)的復雜工程問題。指標點1-2：掌握算法分析與程序設計等計算機科學與技術(shù)專業(yè)知識，能將其用于計算機復雜工程問題模型的實現(xiàn)。目標2畢業(yè)要求2：能夠應用數(shù)學、自然科學和工程科學的基本原理，識別、表達、并通過文獻研究分析計算機工程領域的復雜工程問題，以獲得有效結(jié)論。指標點2-3：能夠基于數(shù)學、自然科學和計算機科學與技術(shù)的基本原理，對計算機復雜工程問題進行提煉、定義、建模、分析和評價。目標3畢業(yè)要求4：能夠基于計算機學科相關(guān)的原理并采用科學方法對計算機工程領域的復雜工程問題進行研究，包括設計實驗、分析與解釋數(shù)據(jù)，并通過信息綜合得到合理有效的結(jié)論。指標點4-1：針對計算機復雜工程問題，能夠基于計算機學科原理，通過調(diào)研和分析，設計合適的研究方案。（三）課程對解決復雜工程問題能力的培養(yǎng)在課程理論知識講授環(huán)節(jié)，不但注重培養(yǎng)學生對算法設計與分析的深入理解，使學生掌握解決計算機應用領域復雜工程問題所需的基本理論以及了解相關(guān)技術(shù)對社會等的影響，而且跟蹤行業(yè)發(fā)展前沿，探討當前熱點問題激發(fā)學生的學習興趣。并通過適當?shù)恼n后作業(yè)鍛煉和檢驗學生解決復雜工程問題的能力。在實驗教學環(huán)節(jié)，以培養(yǎng)學生解決復雜工程問題的能力為目標，圍繞課程支撐的課程目標安排實驗項目，設計實驗內(nèi)容，明確實驗要求，指導實驗實施，嚴格實驗成果考核。在課程考核環(huán)節(jié)，根據(jù)課程支撐的課程目標選擇合適的考核方式，考題設置完全覆蓋課程目標，考題設計應充分考慮學生解決復雜工程問題所需知識和能力?？傊?，本課程的教學通過在理論講授、課后作業(yè)、課內(nèi)實驗、課程考核等環(huán)節(jié)充分貫徹培養(yǎng)學生解決復雜工程問題能力的理念和要求，實現(xiàn)本課程支撐課程目標的達成。三、課程教學內(nèi)容及基本要求（一）理論教學第1章算法概述（4學時）1．教學內(nèi)容（1）算法的基本概念。（2）算法設計的一般過程。（3）算法分析的概念及漸進意義下的記號。（4）時間復雜度和空間復雜度建立的依據(jù)。（5）遞推方程求解方法。2．基本要求（1）理解算法的基本概念、復雜度的衡量。（2）掌握漸進復雜的概念及漸進意義下的記號。（3）掌握時間復雜度建立的依據(jù)和遞推方程求解的方法。3．支撐的課程目標本章各知識點的講授和學習，可以支撐“課程目標1：掌握算法設計與分析的專業(yè)知識，具有應用數(shù)學、算法及計算機的基本原理，能將其用于計算機復雜工程問題模型的實現(xiàn)”，使學生了解算法的基本概念、復雜度的衡量，掌握漸進復雜的概念及漸進意義下的記號，掌握時間復雜度建立的依據(jù)和遞推方程求解的方法，為解決實際工程問題奠定基礎。替代式教學策略和案例教學法，讓學生理解算法的基本概念及算法復雜度的分析方法，掌握漸進復雜度表示及遞推方程求解方法。第2章貪心算法（6學時）1．教學內(nèi)容（1）貪心法的基本思想及基本要素。（2）會場安排問題、最優(yōu)裝載問題。（3）單源最短路徑問題。（4）哈夫曼編碼。（5）最小生成樹。（6）背包問題2．基本要求（1）了解貪心法的應用范圍，理解貪心法的基本思想、特點。（2）掌握典型問題的精巧貪心算法（如會場安排問題、最短路徑問題的Dijkstra算法、求最小生成樹的Kruskal算法和Prim算法等）的基本思想，能利用貪心算法解決實際工程中遇到的問題。通過這些應用，掌握使用貪心策略設計算法的關(guān)鍵步驟、熟悉算法的分析方法及算法正確性的證明方法。3．支撐的課程目標本章各知識點的講授和學習，可以支撐“課程目標1：掌握算法設計與分析的專業(yè)知識，具有應用數(shù)學、算法及計算機的基本原理，能將其用于計算機復雜工程問題模型的實現(xiàn)”、“課程目標2：能基于算法設計與分析的專業(yè)知識，具備針對計算機應用領域復雜工程問題的關(guān)鍵環(huán)節(jié)進行分析、設計及優(yōu)化等工程實踐活動的能力”、“課程目標3：針對計算機復雜工程問題，能夠基于算法設計與分析方法，通過調(diào)研和分析，設計合適的研究方案”。使學生了解貪心算法的基本思想，掌握典型問題的精巧貪心算法，能利用貪心算法解決實際工程中遇到的問題。啟發(fā)式和任務驅(qū)動相結(jié)合，讓學生算法設計的過程及算法復雜度的分析方法，掌握貪心法的基本要素，如何使用貪心法解決實際問題。采用任務驅(qū)動，充分調(diào)動學生的積極性。第3章分治算法（6學時）1．教學內(nèi)容（1）分治法基本思想。（2）分治法的求解步驟。（3）二分查找。（4）選第二大元素。（5）循環(huán)賽日程表。（6）合并排序。（7）快速排序。（8）線性時間選擇。2．基本要求（1）了解分治法的適用范圍，理解其基本思想、特點。（2）掌握設計分治算法的基本步驟；掌握使用分治策略設計的典型問題的精巧算法（如二分搜索算法、排序算法、選擇問題算法等）。（3）理解算法的設計思想、分析方法及復雜度結(jié)論，能在給定問題實例上模擬算法的執(zhí)行。3．支撐的課程目標本章各知識點的講授和學習，可以支撐“課程目標1：掌握算法設計與分析的專業(yè)知識，具有應用數(shù)學、算法及計算機的基本原理，能將其用于計算機復雜工程問題模型的實現(xiàn)”、“課程目標2：能基于算法設計與分析的專業(yè)知識，具備針對計算機應用領域復雜工程問題的關(guān)鍵環(huán)節(jié)進行分析、設計及優(yōu)化等工程實踐活動的能力”、“課程目標3：針對計算機復雜工程問題，能夠基于算法設計與分析方法，通過調(diào)研和分析，設計合適的研究方案”?！?。使學生了解分治法的適用范圍，理解其基本思想，掌握使用分治策略設計的典型問題的精巧算法，能夠利用分治算法解決實際工程問題。分組討論和啟發(fā)式教學，讓學生理解分治算法的基本思想，掌握分治法分與治兩個要點。啟發(fā)學生回顧以前的哪些算法使用了分治策略，生活中哪些事情也是分治。第4章動態(tài)規(guī)劃（10學時）1．教學內(nèi)容（1）動態(tài)規(guī)劃的基本思想及要素。（2）矩陣連乘問題。（3）最優(yōu)凸多邊形三角剖分。（4）最長公共子序列問題。（5）加工順序問題。（6）0-1背包問題。（7）最優(yōu)二叉查找樹。2．基本要求（1）了解動態(tài)規(guī)劃法的適用范圍，理解其基本思想、特點，設計算法的基本步驟。（2）掌握典型問題（如最長公共子序列問題、矩陣連乘、加工順序、0/1背包及最優(yōu)二叉查找樹等問題）的動態(tài)規(guī)劃算法，能在給定問題實例上模擬算法的執(zhí)行。（3）能通過這些典型應用，熟練地掌握使用態(tài)規(guī)劃法設計算法的關(guān)鍵步驟。3．支撐的課程目標本章各知識點的講授和學習，可以支撐“課程目標1：掌握算法設計與分析的專業(yè)知識，具有應用數(shù)學、算法及計算機的基本原理，能將其用于計算機復雜工程問題模型的實現(xiàn)”、“課程目標2：能基于算法設計與分析的專業(yè)知識，具備針對計算機應用領域復雜工程問題的關(guān)鍵環(huán)節(jié)進行分析、設計及優(yōu)化等工程實踐活動的能力”、“課程目標3：針對計算機復雜工程問題，能夠基于算法設計與分析方法，通過調(diào)研和分析，設計合適的研究方案”。使學生了解動態(tài)規(guī)劃法的適用范圍，理解其基本思想、特點，設計算法的步驟，掌握典型問題的動態(tài)規(guī)劃算法求解方法，能夠熟練應用動態(tài)規(guī)劃算法為解決計算機應用的工程項目問題。案例教學法，讓學生了解為什么要使用動態(tài)規(guī)劃，理解動態(tài)規(guī)劃算法的基本要素，掌握動態(tài)規(guī)劃最優(yōu)子結(jié)構(gòu)分析及遞歸式的設計方法。任務驅(qū)動教學法，讓學生動手進行算法實現(xiàn)和分析。第5章回溯法（6學時）1．教學內(nèi)容（1）回溯法的算法框架及思想。（2）子集樹。（3）排列樹。（4）滿m叉樹。2．基本要求（1）了解回溯法，理解其基本思想、特點。（2）掌握針對具體問題設計回溯算法的基本步驟和方法。（3）通過在典型問題（如旅行商問題、0-1背包問題等）上的應用，較熟練掌握使用回溯法求解問題的基本步驟和方法，并能熟練編程序?qū)崿F(xiàn)算法。（4）了解回溯算法估計方法。3．支撐的課程目標本章各知識點的講授和學習，可以支撐“課程目標1：掌握算法設計與分析的專業(yè)知識，具有應用數(shù)學、算法及計算機的基本原理，能將其用于計算機復雜工程問題模型的實現(xiàn)”、“課程目標2：能基于算法設計與分析的專業(yè)知識，具備針對計算機應用領域復雜工程問題的關(guān)鍵環(huán)節(jié)進行分析、設計及優(yōu)化等工程實踐活動的能力”、“課程目標3：針對計算機復雜工程問題，能夠基于算法設計與分析方法，通過調(diào)研和分析，設計合適的研究方案”。使學生了解回溯法、分支限界法的應用范圍，掌握針對具體問題設計回溯算法的基本步驟和方法，并能熟練編程序?qū)崿F(xiàn)算法，為解決實際工程問題奠定基礎。分組討論和案例教學法，讓學生掌握回溯法及算法框架；回溯法的算法設計模式；回溯法及分支限界法的效率分析。布置任務，提高學生動手實踐能力。第6章分支限界法（4學時）1．教學內(nèi)容（1）分支限界法的基本思想。（3）0/1背包問題。（3）旅行商問題。（4）圖的m著色問題。（5）分支限界法與回溯法的比較。2．基本要求（1）了解分支限界法的應用范圍，理解其基本思想、特點。（2）掌握針對具體問題設計分枝限界算法的基本步驟和方法。（3）通過在典型問題（如m著色問題、旅行商問題、0-1背包問題等）上的應用，較熟練掌握使用分枝限界法求解問題的基本步驟和方法，并能熟練編程序?qū)崿F(xiàn)算法。（4）了解分枝限界算法的效率估計方法。3．支撐的課程目標本章各知識點的講授和學習，可以支撐“課程目標1：掌握算法設計與分析的專業(yè)知識，具有應用數(shù)學、算法及計算機的基本原理，能將其用于計算機復雜工程問題模型的實現(xiàn)”、“課程目標2：能基于算法設計與分析的專業(yè)知識，具備針對計算機應用領域復雜工程問題的關(guān)鍵環(huán)節(jié)進行分析、設計及優(yōu)化等工程實踐活動的能力”、“課程目標3：針對計算機復雜工程問題，能夠基于算法設計與分析方法，通過調(diào)研和分析，設計合適的研究方案”。使學生了解回溯法、分支限界法的應用范圍，掌握針對具體問題設計分枝限界算法的基本步驟和方法，并能熟練編程序?qū)崿F(xiàn)算法，為解決實際工程問題奠定基礎。分組討論和案例教學法，讓學生掌握分支限界法算法框架；分支限界法的算法設計模式；分支限界法的效率分析。布置任務，提高學生動手實踐能力。第7章線性規(guī)劃問題與網(wǎng)絡流（8學時）1．教學內(nèi)容（1）線性規(guī)劃的基本概念、定理及單純形算法。（2）最大網(wǎng)絡流問題的解法。（3）最小費用流問題的解法。2．基本要求（1）了解線性規(guī)劃模型的特點、線性規(guī)劃問題的標準型及退化處理。（2）掌握線性規(guī)劃問題解的概念、有關(guān)解的基本定理。（3）掌握單純形法的原理和求解方法。（4）掌握最大網(wǎng)絡流問題的求解方法和最小費用流問題的求解方法。3．支撐的課程目標本章各知識點的講授和學習，可以支撐“課程目標1：掌握算法設計與分析的專業(yè)知識，具有應用數(shù)學、算法及計算機的基本原理，能將其用于計算機復雜工程問題模型的實現(xiàn)”、“課程目標2：能基于算法設計與分析的專業(yè)知識，具備針對計算機應用領域復雜工程問題的關(guān)鍵環(huán)節(jié)進行分析、設計及優(yōu)化等工程實踐活動的能力”、“課程目標3：針對計算機復雜工程問題，能夠基于算法設計與分析方法，通過調(diào)研和分析，設計合適的研究方案”。使學生解線性規(guī)劃模型的特點、線性規(guī)劃問題的標準型及退化處理，掌握單純形法的原理和求解方法，掌握最大網(wǎng)絡流問題的求解方法和最小費用流問題的求解方法，能夠利用最大流算法解決實際工程問題。案例教學和啟發(fā)式教學法，讓學生理解線性規(guī)劃和網(wǎng)絡流的基本思想，掌握單純形算法；最大網(wǎng)絡流問題；最小費用流問題的求解方法。啟發(fā)學生動手動腦，解決布置的任務。第8章隨機化算法（6學時）1．教學內(nèi)容（1）隨機化算法的類型及特點。（2）隨機數(shù)發(fā)生器。（3）數(shù)值隨機化算法。（4）蒙特卡羅算法。（5）拉斯維加斯算法。（6）舍伍德算法。2．基本要求（1）了解隨機化算法的基本特征。（2）理解數(shù)值隨機算法、舍伍德算法、拉斯維加斯算法、蒙特卡洛算法的特點和適用范圍。（3）掌握素數(shù)測試、整數(shù)的因子分解等隨機化算法。3．支撐的課程目標本章各知識點的講授和學習，可以支撐“課程目標1：掌握算法設計與分析的專業(yè)知識，具有應用數(shù)學、算法及計算機的基本原理，能將其用于計算機復雜工程問題模型的實現(xiàn)”、“課程目標2：能基于算法設計與分析的專業(yè)知識，具備針對計算機應用領域復雜工程問題的關(guān)鍵環(huán)節(jié)進行分析、設計及優(yōu)化等工程實踐活動的能力”，使學生了解隨機化算法的基本特征，掌握素數(shù)測試、整數(shù)的因子分解等隨機化算法，體會隨機化算法在工程項目中的應用，為解決實際工程問題奠定基礎。啟發(fā)式教學法，讓學生理解什么是隨機化算法，掌握四種隨機化算法的特點和適用范圍，啟發(fā)學生思考生活中的隨機化例子，鼓勵學生動手實現(xiàn)。第9章NP完全理論（2學時）1．教學內(nèi)容（1）P類和NP類問題。（2）NP完全問題。（3）NP完全問題的近似算法。2．基本要求（1）了解P類和NP類問題。（2）理解NP完全問題及近似算法。3．支撐的課程目標本章各知識點的講授和學習，可以支撐“課程目標1：掌握算法設計與分析的專業(yè)知識，具有應用數(shù)學、算法及計算機的基本原理，能將其用于計算機復雜工程問題模型的實現(xiàn)”，使學生了解P類和NP類問題，理解NP完全問題及近似算法，為解決實際工程問題奠定基礎。分組討論和啟發(fā)式教學法，讓學生理解P類和NP類問題、NP完全問題，及近似算法的設計與可靠性分析。啟發(fā)學生思考以前學過的算法屬于什么問題類型。（二）實驗教學實驗項目1．貪心算法應用（2學時）1．實驗內(nèi)容（1）給出背包問題的貪心算法。（2）給出會議安排問題的貪心算法。（3）給出算法復雜度分析。2．基本要求（1）理解和掌握貪心算法的基本思想和步驟。（2）掌握貪心算法的復雜性分析方法。（3）能夠利用貪心算法解決實際工程問題。3．支撐的課程目標本實驗項目可以支撐“課程目標1：掌握算法設計與分析的專業(yè)知識，具有應用數(shù)學、算法及計算機的基本原理，能將其用于計算機復雜工程問題模型的實現(xiàn)”、“課程目標2：能基于算法設計與分析的專業(yè)知識，具備針對計算機應用領域復雜工程問題的關(guān)鍵環(huán)節(jié)進行分析、設計及優(yōu)化等工程實踐活動的能力”、“課程目標3：針對計算機復雜工程問題，能夠基于算法設計與分析方法，通過調(diào)研和分析，設計合適的研究方案”。本實驗通過問題啟發(fā)式引導學生依據(jù)所掌握的相關(guān)知識點，熟悉某一具體問題的貪心算法求解方法，加深對貪心算法的理解，達到課程目標的要求。實驗項目2．分治算法應用（2學時）1．實驗內(nèi)容（1）給出合并排序算法和程序。（2）給出快速排序算法和程序。（3）給出算法復雜度分析。2．基本要求（1）熟悉分治算法的分解與治理方法。（2）掌握分治法的應用場景和遞歸求解的方法。（3）鍛煉利用分治法解決實際問題的能力。3．支撐的課程目標本實驗項目可以支撐“課程目標1：掌握算法設計與分析的專業(yè)知識，具有應用數(shù)學、算法及計算機的基本原理，能將其用于計算機復雜工程問題模型的實現(xiàn)”、“課程目標2：能基于算法設計與分析的專業(yè)知識，具備針對計算機應用領域復雜工程問題的關(guān)鍵環(huán)節(jié)進行分析、設計及優(yōu)化等工程實踐活動的能力”、“課程目標3：針對計算機復雜工程問題，能夠基于算法設計與分析方法，通過調(diào)研和分析，設計合適的研究方案”。本實驗通過問題啟發(fā)式引導學生依據(jù)所掌握的相關(guān)知識點，熟悉某一具體問題的分治算法求解方法，加深對分治算法的理解，達到課程目標的要求。實驗項目3．動態(tài)規(guī)劃算法應用（2學時）1．實驗內(nèi)容（1）給出最優(yōu)三角剖分的動態(tài)規(guī)劃算法和程序。（2）給出最優(yōu)二叉樹的動態(tài)規(guī)劃算法和程序。（3）給出算法復雜度分析。2．基本要求（1）理解動態(tài)規(guī)劃算法的適用場景。（2）掌握動態(tài)規(guī)劃問題的算法設計與實現(xiàn)方法。（3）掌握動態(tài)規(guī)劃算法的復雜度分析方法。3．支撐的課程目標本實驗項目可以支撐“課程目標1：掌握算法設計與分析的專業(yè)知識，具有應用數(shù)學、算法及計算機的基本原理，能將其用于計算機復雜工程問題模型的實現(xiàn)”、“課程目標2：能基于算法設計與分析的專業(yè)知識，具備針對計算機應用領域復雜工程問題的關(guān)鍵環(huán)節(jié)進行分析、設計及優(yōu)化等工程實踐活動的能力”、“課程目標3：針對計算機復雜工程問題，能夠基于算法設計與分析方法，通過調(diào)研和分析，設計合適的研究方案”。本實驗通過啟發(fā)式方式引導學生依據(jù)所掌握的相關(guān)知識點，根據(jù)具體問題設計動態(tài)規(guī)劃算法并分析優(yōu)化，達到課程目標的要求。實驗項目4．搜索算法應用（2學時）1．實驗內(nèi)容（1）給出最大團問題的回溯算法和程序。（2）給出旅行商問題的分支限界算法和程序。（3）掌握搜索算法的復雜度分析方法。2．基本要求（1）理解和掌握搜索算法的算法設計框架。（2）理解和掌握搜索算法解決實際問題的過程和算法設計優(yōu)化方法。3．支撐的課程目標本實驗項目可以支撐“課程目標1：掌握算法設計與分析的專業(yè)知識，具有應用數(shù)學、算法及計算機的基本原理，能將其用于計算機復雜工程問題模型的實現(xiàn)”、“課程目標2：能基于算法設計與分析的專業(yè)知識，具備針對計算機應用領域復雜工程問題的關(guān)鍵環(huán)節(jié)進行分析、設計及優(yōu)化等工程實踐活動的能力”、“課程目標3：針對計算機復雜工程問題，能夠基于算法設計與分析方法，通過調(diào)研和分析，設計合適的研究方案”。本實驗通過啟發(fā)式方式引導學生依據(jù)所掌握的相關(guān)知識點，根據(jù)具體工程項目設計搜索算法并分析優(yōu)化，達到課程目標的要求。實驗項目5．隨機化算法應用（2學時）1．實驗內(nèi)容（1）給出n皇后問題的隨機化算法和程序。（2）給出隨機快速排序的算法和程序。（3）掌握隨機化算法的復雜度分析方法。2．基本要求（1）熟悉隨機化算法的類型和特點。（2）根據(jù)具體問題設計隨機化算法。3．支撐的課程目標本實驗項目可以支撐“課程目標1：掌握算法設計與分析的專業(yè)知識，具有應用數(shù)學、算法及計算機的基本原理，能將其用于計算機復雜工程問題模型的實現(xiàn)”、“課程目標2：能基于算法設計與分析的專業(yè)知識，具備針對計算機應用領域復雜工程問題的關(guān)鍵環(huán)節(jié)進行分析、設計及優(yōu)化等工程實踐活動的能力”。本實驗通過啟發(fā)式方式，引導學生掌握在計算機應用項目中設計隨機化算法解決實際問題，達到課程目標的要求。實驗項目6．網(wǎng)絡流算法應用（2學時）1．實驗內(nèi)容（1）給出飛行員配對問題的算法和程序。（2）給出太空實驗室計劃的算法和程序。（3）掌握網(wǎng)絡流算法的復雜度分析方法。2．基本要求（1）理解并體會具體問題分析抽象的過程。（2）運用網(wǎng)絡流算法解決實際問題。（3）培養(yǎng)學生的系統(tǒng)思維，提升解決復雜工程問題所需的問題分析和系統(tǒng)設計能力。3．支撐的課程目標本實驗項目可以支撐“課程目標1：掌握算法設計與分析的專業(yè)知識，具有應用數(shù)學、算法及計算機的基本原理，能將其用于計算機復雜工程問題模型的實現(xiàn)”、“課程目標2：能基于算法設計與分析的專業(yè)知識，具備針對計算機應用領域復雜工程問題的關(guān)鍵環(huán)節(jié)進行分析、設計及優(yōu)化等工程實踐活動的能力”、“課程目標3：針對計算機復雜工程問題，能夠基于算法設計與分析方法，通過調(diào)研和分析，設計合適的研究方案”。本實驗通過啟發(fā)式方式，引導學生依據(jù)所掌握的相關(guān)知識點，培養(yǎng)具備學生根據(jù)具體工程項目問題進行網(wǎng)絡流算法設計的能力，達到課程目標的要求。四、教學方式、教學方法及課時安排（一）教學方式課程目標與教學環(huán)節(jié)序號課程目標教學環(huán)節(jié)講授作業(yè)實驗1掌握算法設計與分析的專業(yè)知識，具有應用數(shù)學、算法及計算機的基本原理，能將其用于計算機復雜工程問題模型的實現(xiàn)2目標2：能基于算法設計與分析的專業(yè)知識，具備針對計算機應用領域復雜工程問題的關(guān)鍵環(huán)節(jié)進行分析、設計及優(yōu)化等工程實踐活動的能力3目標3：針對計算機復雜工程問題，能夠基于算法設計與分析方法，通過調(diào)研和分析，設計合適的研究方案。以課堂講授為主，結(jié)合課堂講授內(nèi)容安排課內(nèi)實驗及課后作業(yè)，加深對理論教學內(nèi)容的理解和認識，培養(yǎng)工程實踐能力。（二）教學方法本課程貫徹“以學生為主體，以教師為主導”的教學思想，采用“互動、開放”的課堂形式，具體以課堂教學為主，結(jié)合自學、課后作業(yè)和實驗教學，采用啟發(fā)式、問題式的教學方法，基于項目的實際問題，提高學生解決復雜計算機算法應用問題的能力，達到課程目標的要求。相關(guān)課程目標支撐如下：課堂教學主要講解與算法設計與分析有關(guān)的基本概念、基本理論以及基本分析方法，并將日常生活中所遇到的算法問題、智能應用系統(tǒng)案例融入基本理論的講解，使同學們更好地熟悉或掌握算法的基本原理，提高學生對算法的興趣、熟悉算法設計分析及優(yōu)化、思維方式和研究方法。課堂教學盡量引入互動環(huán)節(jié)，通過問題導入教學，引導學生尋找解決方案，提高教學效果，達到“課程目標1：掌握算法設計與分析的專業(yè)知識，具有應用數(shù)學、算法及計算機的基本原理，能將其用于計算機復雜工程問題模型的實現(xiàn)”、“課程目標2：能基于算法設計與分析的專業(yè)知識，具備針對計算機應用領域復雜工程問題的關(guān)鍵環(huán)節(jié)進行分析、設計及優(yōu)化等工程實踐活動的能力”、“課程目標3：針對計算機復雜工程問題，能夠基于算法設計與分析方法，通過調(diào)研和分析，設計合適的研究方案”的要求。通過實驗教學增強學生理解理論知識，動手尋找答案，以培養(yǎng)學生解決數(shù)據(jù)庫應用問題的能力，達到“課程目標1：掌握算法設計與分析的專業(yè)知識，具有應用數(shù)學、算法及計算機的基本原理，能將其用于計算機復雜工程問題模型的實現(xiàn)”、“課程目標2：能基于算法設計與分析的專業(yè)知識，具備針對計算機應用領域復雜工程問題的關(guān)鍵環(huán)節(jié)進行分析、設計及優(yōu)化等工程實踐活動的能力”、“課程目標3：針對計算機復雜工程問題，能夠基于算法設計與分析方法，通過調(diào)研和分析，設計合適的研究方案”。課堂討論以及課后作業(yè)，能培養(yǎng)同學們的綜合能力，熟悉運用所學知識的能力，鍛煉表達能力，并通過合作客觀評價相關(guān)工程對社會、經(jīng)濟等影響，發(fā)表自己的見解。達到“課程目標1：掌握算法設計與分析的專業(yè)知識，具有應用數(shù)學、算法及計算機的基本原理，能將其用于計算機復雜工程問題模型的實現(xiàn)”、“課程目標2：能基于算法設計與分析的專業(yè)知識，具備針對計算機應用領域復雜工程問題的關(guān)鍵環(huán)節(jié)進行分析、設計及優(yōu)化等工程實踐活動的能力”、“課程目標3：針對計算機復雜工程問題，能夠基于算法設計與分析方法，通過調(diào)研和分析，設計合適的研究方案”的要求。（三）課時安排本課程總學時52學時，其中：講授40學時，實驗（或上機或綜合練習）12學時，具體教學安排如下表。學時分配與教學方法序號教學內(nèi)容學時分配教學方法1算法概述4講授2貪心算法6講授3分治算法6講授4動態(tài)規(guī)劃10講授5回溯法6講授6分支限界法4講授7線性規(guī)劃和網(wǎng)絡流8講授8隨機化算法6講授9NP完全理論2講授10實驗一：貪心算法應用2實驗11實驗二：分治算法應用2實驗12實驗三：動態(tài)規(guī)劃算法應用2實驗13實驗四：搜索算法應用2實驗14實驗五：隨機化算法應用2實驗15實驗六：網(wǎng)絡流算法應用2實驗合計64五、考核方式與成績評定辦法（一）考核方式及具體要求最終成績由平時作業(yè)成績、上機與實驗成績和期末成績等組合而成，各部分所占比例如下：平時作業(yè)成績（占30%）：包括章節(jié)測試、作業(yè)。其中，作業(yè)：教師評判作業(yè)并根據(jù)作業(yè)內(nèi)容的正確性、完成認真度及規(guī)范性給出評定成績。上機與實驗（占20%）：主要考核根據(jù)常見的問題進行算法設計能力、算法分析的能力、算法優(yōu)化的能力，學生可根據(jù)任課教師布置的實驗題目與目標，通過結(jié)合算法的理論知識，進行設計、代碼編寫、測試與分析，給出一定形式的實驗結(jié)果及分析說明。上機與實驗考核：根據(jù)實驗結(jié)果正確性的完成情況及實驗報告的規(guī)范性給出評定成績。期末考試成績（占50%）：在考核算法基礎知識掌握程度的基礎上，重點考核理論知識的應用能力，以及解決計算機應用工程項目中相關(guān)復雜工程問題的能力。期末考試采用書面閉卷形式，主要題型可以是選擇題、填空題、簡答題、算法設計題、綜合應用題等。課程考核能夠針對學生對專業(yè)核心知識的掌握情況、運用理論知識解決計算機應用的能力、客觀評價算法優(yōu)化及智能算法領域?qū)ι鐣?、文化等影響的能力和能及時跟蹤相關(guān)行業(yè)發(fā)展狀況，就當前的熱點問題發(fā)表自己見解的能力等方面進行考核，支持“課程目標1：掌握算法設計與分析的專業(yè)知識，具有應用數(shù)學、算法及計算機的基本原理，能將其用于計算機復雜工程問題模型的實現(xiàn)”、“課程目標2：能基于算法設計與分析的專業(yè)知識，具備針對計算機應用領域復雜工程問題的關(guān)鍵環(huán)節(jié)進行分析、設計及優(yōu)化等工程實踐活動的能力”、“課程目標3：針對計算機復雜工程問題，能夠基于算法設計與分析方法，通過調(diào)研和分析，設計合適的研究方案”。（二）成績評定辦法及依據(jù)1.平時成績章節(jié)測試成績由網(wǎng)絡教學平臺自動批閱評定。平時成績評分標準（作業(yè)）分值觀測點90-100分70-89分60-69分0-59分得分作業(yè)完成程度（權(quán)重10%）按時全部完成延時全部完成按時部分完成延時部分完成算法基礎知識掌握及復雜算法問題應用系統(tǒng)解決方案的分析（權(quán)重45%）概念清晰，分析得當主要概念清晰，但部分分析有誤部分概念清晰，分析中有明顯錯誤基本概念不清，分析錯誤應用