1、算法設(shè)計(jì)與分析一、課程概況所屬專業(yè):軟件工程開課單位：數(shù)學(xué)計(jì)算機(jī)科學(xué)學(xué)院課程類型:專業(yè)選修課程課程代碼:07494020開課學(xué)期:4學(xué)分：2學(xué)時(shí)：34核心課程:否擬使用教材：陳慧南. 算法設(shè)計(jì)與分析: C+語言描述M. 電子工業(yè)出版社, 2012.國(guó)內(nèi)(外)現(xiàn)有教材：M.H.ALSUWAIYEL. 算法設(shè)計(jì)技巧與分析M. 電子工業(yè)出版社, 2006.余祥宣 崔國(guó)華. 計(jì)算機(jī)算法基礎(chǔ)(第3版)M. 華中科大出版社, 2006.學(xué)習(xí)參考資料：王曉東. 計(jì)算機(jī)算法設(shè)計(jì)與分析(第3版)M. 電子工業(yè)出版社, 2007.李春葆. 算法設(shè)計(jì)與分析M. 清華大學(xué)出版社, 2015.二、課程描述算法設(shè)計(jì)與分析

2、是軟件工程專業(yè)的選修課。無論是計(jì)算科學(xué)還是計(jì)算實(shí)踐，算法都在其中扮演著重要角色。該課程系統(tǒng)地介紹了計(jì)算機(jī)算法的設(shè)計(jì)方法與分析技巧，通過課程學(xué)習(xí)，為獨(dú)立地設(shè)計(jì)算法和對(duì)算法進(jìn)行分析奠定堅(jiān)實(shí)的知識(shí)基礎(chǔ)，本課程的教學(xué)目的是講授在計(jì)算機(jī)應(yīng)用中常常遇到的實(shí)際問題的解法，講授設(shè)計(jì)和分析各種算法的基本原理、方法和技術(shù)，培養(yǎng)學(xué)生對(duì)算法復(fù)雜性進(jìn)行正確分析的能力。三、課程目標(biāo)(1) 掌握算法分析的基本概念和理論。(2) 掌握算法設(shè)計(jì)技術(shù)和分析算法以及算法復(fù)雜性。(3) 便運(yùn)用算法設(shè)計(jì)方法來設(shè)計(jì)解決一些常用的或較為復(fù)雜的實(shí)際問題的算法。(4) 具有問題抽象和建模的初步能力。四、教學(xué)要求授課教師將按照學(xué)校本科教學(xué)工作有

3、關(guān)要求做好課程教學(xué)各項(xiàng)工作，嚴(yán)格按照課表規(guī)定的時(shí)間、地點(diǎn)上課，不遲到、不早退。授課過程力求內(nèi)容充實(shí)、概念準(zhǔn)確、思路清晰、詳略得當(dāng)、邏輯性強(qiáng)、重難點(diǎn)突出，理論與實(shí)踐相結(jié)合的教學(xué)方法，以理論學(xué)習(xí)為主，以上機(jī)實(shí)驗(yàn)為輔，加深對(duì)理論的理解。提倡學(xué)生廣泛閱讀參考書、獨(dú)立思考、結(jié)合實(shí)際問題展開討論的教學(xué)方式。重視對(duì)學(xué)生的學(xué)習(xí)方法指導(dǎo)和課堂教學(xué)效果信息的反饋，實(shí)現(xiàn)教與學(xué)的雙向互動(dòng)；同時(shí)將結(jié)合課程目標(biāo)要求，做好考核內(nèi)容設(shè)計(jì)，并嚴(yán)格按照本要求做好出勤率統(tǒng)計(jì)、作業(yè)評(píng)價(jià)等各項(xiàng)工作。學(xué)生應(yīng)根據(jù)課程要求制定本門課程學(xué)習(xí)計(jì)劃，加強(qiáng)學(xué)業(yè)管理，嚴(yán)格自我要求，提升自主學(xué)習(xí)能力，主動(dòng)適應(yīng)課程學(xué)習(xí)要求。參與課堂教學(xué)活動(dòng)不遲到、不早退

4、，無正當(dāng)理由不請(qǐng)假，上課認(rèn)真聽講，不做任何與課堂教學(xué)無關(guān)事宜，不使用手機(jī)，積極與授課教師進(jìn)行教學(xué)互動(dòng)，同時(shí)利用課余時(shí)間做好預(yù)習(xí)、復(fù)習(xí)、課外書籍閱讀等工作，主動(dòng)與同學(xué)開展合作學(xué)習(xí)，認(rèn)真完成任課教師布置的課程作業(yè)。根據(jù)算法設(shè)計(jì)與分析這門課的特點(diǎn)，達(dá)到以下要求：(1)掌握算法的定義及基本概念,計(jì)算模型和復(fù)雜度的衡量; (2)為分析算法的復(fù)雜性做準(zhǔn)備,要了解相應(yīng)的數(shù)學(xué)知識(shí); (3)掌握算法設(shè)計(jì)的過程和方法; (4)學(xué)會(huì)分析算法的時(shí)間復(fù)雜度,空間復(fù)雜度和穩(wěn)定性; (5)具有問題抽象和建模的初步能力。五、考核方式及要求為實(shí)現(xiàn)課程教學(xué)目標(biāo)，本門課程考核方式及要求分為平時(shí)成績(jī)和期末成績(jī)。平時(shí)成績(jī)占總成績(jī)60%

5、：出勤率占40%，點(diǎn)到不少于8次；隨堂測(cè)驗(yàn)1次，測(cè)驗(yàn)成績(jī)占20%；課程作業(yè)2次，成績(jī)占20%；實(shí)驗(yàn)作業(yè)2次，成績(jī)占20%。期末成績(jī)占總成績(jī)40%：期末考試為卷面考試。六、課程內(nèi)容第一章：算法問題求解基礎(chǔ)（授課時(shí)間：第四學(xué)期第一周）教學(xué)目標(biāo)：理解算法的定義和特征、掌握算法問題的求解過程、掌握遞歸策略和數(shù)學(xué)歸納法證明算法正確性方法。教學(xué)重點(diǎn)：算法的定義和特征、算法問題的求解過程。教學(xué)難點(diǎn)：歸策略和數(shù)學(xué)歸納法證明算法正確性方法。學(xué) 時(shí)：課堂教學(xué)2學(xué)時(shí)，自主學(xué)習(xí)時(shí)間不少于2學(xué)時(shí)教學(xué)方法：講授法、演示法主要內(nèi)容：1.1 算法概述1.2 問題求解方法1.3 算法設(shè)計(jì)與分析1.4 遞歸和歸納學(xué)習(xí)方法：小組討

6、論。課后作業(yè)：完成教材第13頁練習(xí)題1-5、1-9。第二章：算法分析基礎(chǔ)（授課時(shí)間：第四學(xué)期第二周）教學(xué)目標(biāo)：了解算法的計(jì)算復(fù)雜性分析方法、理解算法分析的基本理論、掌握算法分析的基本概念。教學(xué)重點(diǎn)：算法的計(jì)算復(fù)雜性分析方法教學(xué)難點(diǎn)：算法的計(jì)算復(fù)雜性分析方法學(xué) 時(shí)：課堂教學(xué)2學(xué)時(shí)，自主學(xué)習(xí)時(shí)間不少于2學(xué)時(shí)教學(xué)方法：講授法、演示法主要內(nèi)容：2.1 算法復(fù)雜度2.2 漸近表示法2.3 遞推關(guān)系2.4 分?jǐn)偡治鰧W(xué)習(xí)方法：小組討論。課后作業(yè)：完成教材第28頁練習(xí)題2-4、2-17.第三章：基本搜索和遍歷方法（授課時(shí)間：第四學(xué)期第二周）教學(xué)目標(biāo)：理解搜索和遍歷算法中的基本概念、掌握?qǐng)D的鄰接表的表示、掌握廣

7、度優(yōu)先搜索和深度優(yōu)先搜索、掌握關(guān)節(jié)點(diǎn)的發(fā)現(xiàn)方法教學(xué)重點(diǎn)：掌握廣度優(yōu)先搜索和深度優(yōu)先搜索、掌握關(guān)節(jié)點(diǎn)的發(fā)現(xiàn)方法教學(xué)難點(diǎn)：掌握關(guān)節(jié)點(diǎn)的發(fā)現(xiàn)方法學(xué) 時(shí)：課堂教學(xué)4學(xué)時(shí)，自主學(xué)習(xí)時(shí)間不少于3學(xué)時(shí)教學(xué)方法：講授法、演示法主要內(nèi)容：3.1 基本概念3.2 圖的搜索和遍歷3.3 雙連通分量3.4 與或圖學(xué)習(xí)方法：小組討論、實(shí)驗(yàn)操作。課后作業(yè)：完成教材第62頁練習(xí)題第4、10題。第四章：分治法（授課時(shí)間：第四學(xué)期第四到五周）教學(xué)目標(biāo)：理解典型范例中分治策略應(yīng)用技巧、掌握分治策略教學(xué)重點(diǎn)：分治法的一般方法、歸并分類和快速分類算法教學(xué)難點(diǎn)：快速分類算法、選擇問題算法學(xué) 時(shí)：課堂教學(xué)3學(xué)時(shí)，課外自主學(xué)習(xí)時(shí)間不少于2

8、學(xué)時(shí)教學(xué)方法：講授法、演示法主要內(nèi)容：4.1 一般方法4.2 求最大最小元4.3 二分搜索4.4 排序問題4.5 選擇問題4.6 斯特拉森矩陣乘法學(xué)習(xí)方法：小組討論、實(shí)驗(yàn)操作課后作業(yè)：完成教材第89頁練習(xí)題第6、9、11題。第五章：貪心法（授課時(shí)間：第四學(xué)期第六到八周）教學(xué)目標(biāo)：了解貪心算法的理論基礎(chǔ)及基本要素、 理解典型范例中貪心算法的設(shè)計(jì)思想、掌握貪心算法的設(shè)計(jì)要點(diǎn)教學(xué)重點(diǎn)：貪心設(shè)計(jì)策略的一般方法，歸并算法、最小生成樹算法教學(xué)難點(diǎn)：最小生成樹算法、最短路徑算法學(xué) 時(shí)：課堂教學(xué)5學(xué)時(shí)，課外自主學(xué)習(xí)時(shí)間不少于4學(xué)時(shí)教學(xué)方法：講授法、演示法主要內(nèi)容：5.1 一般方法5.2 背包問題5.3 帶時(shí)限

9、的作業(yè)排序5.4 最佳合并模式5.5 最小代價(jià)生成樹5.6 單源最短路徑5.7 磁帶最優(yōu)存儲(chǔ)5.8貪心法的基本要素學(xué)習(xí)方法：小組討論、實(shí)驗(yàn)操作課后作業(yè)：完成教材第120頁練習(xí)題第1、3、12題。第六章：動(dòng)態(tài)規(guī)劃法（授課時(shí)間：第四學(xué)期第八到十一周）教學(xué)目標(biāo)：理解典型范例中動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)思想、掌握動(dòng)態(tài)規(guī)劃算法的基本要求以及算法的設(shè)計(jì)要點(diǎn)教學(xué)重點(diǎn)：動(dòng)態(tài)規(guī)劃的一般方法、最優(yōu)二分檢索樹、0/1背包問題教學(xué)難點(diǎn)：段圖、最優(yōu)二分檢索樹、流水線調(diào)度問題學(xué) 時(shí)：課堂教學(xué)5學(xué)時(shí)，自主學(xué)習(xí)時(shí)間不少于3學(xué)時(shí)教學(xué)方法：講授法、演示法主要內(nèi)容：6.1 一般方法和基本要素6.2 每對(duì)結(jié)點(diǎn)間的最短路徑6.3 矩陣連乘6.

10、4 最長(zhǎng)公共子序列6.5 最優(yōu)二叉搜索樹6.6 0/1背包6.7 流水作業(yè)調(diào)度.學(xué)習(xí)方法：小組討論、實(shí)驗(yàn)操作課后作業(yè)：完成教材第158頁練習(xí)題第1、13、20題。第七章：回溯法（授課時(shí)間：第四學(xué)期第十一到十三周）教學(xué)目標(biāo)：理解回溯法的效率分析方法、掌握回溯法的算法框架和應(yīng)用技巧教學(xué)重點(diǎn)：回溯的一般方法、n-皇后問題、圖的著色教學(xué)難點(diǎn)：n-皇后問題、圖的著色學(xué) 時(shí)：課堂教學(xué)3學(xué)時(shí)，課外自主學(xué)習(xí)時(shí)間不少于2學(xué)時(shí)教學(xué)方法：講授法、演示法主要內(nèi)容：7.1 一般方法7.2 n-皇后7.3 子集和數(shù)7.4 圖的著色7.5 哈密頓環(huán)7.6 0/1背包7.7 批處理作業(yè)調(diào)度學(xué)習(xí)方法：小組討論、實(shí)驗(yàn)操作課后作業(yè)：完成教材第180頁練習(xí)題第2、14題。第八章：分枝限界法（授課時(shí)間：第四學(xué)期第十四到十五周）教學(xué)目標(biāo)：理解分支限界法的基本思想、掌握典型范例中分支限界法的應(yīng)用技巧教學(xué)重點(diǎn)：分枝-限界的一般方法教學(xué)難點(diǎn)：