算法設(shè)計(jì)與分析教學(xué)大綱及實(shí)驗(yàn)大綱

1、精選優(yōu)質(zhì)文檔-傾情為你奉上算法設(shè)計(jì)與分析教學(xué)大綱課程名稱（中、英文）：算法設(shè)計(jì)與分析、Design and Analysis of Algorithm 課程編號(hào)： 學(xué)分?jǐn)?shù)：3 總學(xué)時(shí)數(shù)：45(理教：40 實(shí)驗(yàn)：6)適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)、軟件工程、網(wǎng)絡(luò)工程一、課程的性質(zhì)、目的與任務(wù)隨著計(jì)算機(jī)的廣泛應(yīng)用，對(duì)計(jì)算機(jī)算法的研究變得日益重要。本課程將覆蓋計(jì)算機(jī)軟件實(shí)現(xiàn)中的大部分算法，并具有一定的深度和廣度，使學(xué)生對(duì)計(jì)算機(jī)常用算法有一個(gè)全盤的了解；本課程首先介紹計(jì)算復(fù)雜性的定義和算法分析的基本方法，結(jié)合計(jì)算機(jī)科學(xué)及應(yīng)用領(lǐng)域中常見的有代表性的非數(shù)值算法，介紹了幾種重要的算法設(shè)計(jì)的方法：分治法、動(dòng)態(tài)

2、規(guī)劃、貪心法、回朔法、分枝限界法，NP完全問題。使學(xué)生在掌握各種算法的同時(shí)，掌握算法分析的基本方法和技巧。本課程的任務(wù)是：培養(yǎng)學(xué)生具有針對(duì)給定問題設(shè)計(jì)和實(shí)現(xiàn)高效算法的能力。包括以下三方面：1通過對(duì)常用的、有代表性的算法的研究，讓學(xué)生理解并掌握算法設(shè)計(jì)的基本技術(shù)。2培養(yǎng)學(xué)生分析算法復(fù)雜度的初步能力，鍛煉其邏輯思維能力和想象力，并使之了解算法理論的發(fā)展。3鼓勵(lì)學(xué)生運(yùn)用算法知識(shí)解決各自學(xué)科的實(shí)際問題，培養(yǎng)他們的獨(dú)立科研的能力和理論聯(lián)系實(shí)踐的能力。二、課程的基本要求本課程在學(xué)習(xí)之前，最好具有離散數(shù)學(xué)、程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)等方面的知識(shí)。在此基礎(chǔ)上通過本課程的學(xué)習(xí)，掌握算法的定義及基本概念、計(jì)算模型和復(fù)雜度

3、的質(zhì)量；為分析算法的復(fù)雜性做準(zhǔn)備，在這個(gè)基礎(chǔ)上，學(xué)習(xí)一些常用的算法設(shè)計(jì)策略，掌握其基本思想和相應(yīng)算法，編制出相應(yīng)程序上機(jī)調(diào)試。三、基本教學(xué)內(nèi)容與學(xué)時(shí)安排1. 算法概述（4學(xué)時(shí)） (1)了解算法與程序的概念。 (2)掌握算法復(fù)雜性分析及其有關(guān)的概念。 2. 遞歸與分治策略（8學(xué)時(shí)） (1)理解遞歸的概念。 (2)了解分治法的基本思想。 (3) 掌握Strassen矩陣乘法、大整數(shù)乘法、線性時(shí)間選擇、最接近點(diǎn)對(duì)問題的算法。 (4) 理解合并排序和快速排序算法。3. 動(dòng)態(tài)規(guī)劃（8學(xué)時(shí)） (1)掌握動(dòng)態(tài)規(guī)劃算法的概念和步驟。 (2)掌握矩陣的連乘算法設(shè)計(jì)和分析。 (3)掌握動(dòng)態(tài)規(guī)劃算法的基本要素。 (

4、4)掌握最長(zhǎng)公共子序列、0-1背包問題的算法設(shè)計(jì)和分析。 (5)了解凸多邊形最優(yōu)三角剖分、多邊形游戲、流水作業(yè)調(diào)度問題的算法設(shè)計(jì)和分析。 4. 貪心算法（6學(xué)時(shí)） (1)掌握貪心算法的概念。 (2)掌握貪心算法的基本要素。 (3)了解最優(yōu)裝載問題的算法分析。 (4)了解哈夫曼編碼的算法分析。 (5)了解單源最短路徑的Dijkstra算法的設(shè)計(jì)與分析。 (6)了解最小生成樹的Prim和Kruskal算法的設(shè)計(jì)與分析。5. 回溯法（4學(xué)時(shí)） (1)掌握回溯法的算法框架。 (2)掌握裝載問題、批處理作業(yè)調(diào)度、符號(hào)三角形問題、0-1背包問題、圖的m著色問題的算法設(shè)計(jì)與分析。 (3)了解n后問題、最大團(tuán)

5、問題的回溯法的算法設(shè)計(jì)與分析。6. 分支限界法（4學(xué)時(shí)） (1)掌握分支限界法的基本思想。 (2)掌握單源最短路問題、0-1背包問題的分支限界法分析。 (3)了解旅行售貨員問題的算法設(shè)計(jì)與分析。7. 隨機(jī)化算法（2學(xué)時(shí)） (1)掌握隨機(jī)化算法的特征。 (2)掌握隨機(jī)化算法的4種分類。 (3) 理解產(chǎn)生偽隨機(jī)數(shù)的算法。8. NP完全性問題（4學(xué)時(shí)） (1)了解NP完全性問題的概念。 (2)理解求解問題的計(jì)算模型。 (3)了解P類問題和NP類問題。 (4)了解NP完全問題。 (5)了解一些典型的NP完全問題。四、 建議學(xué)時(shí)分配表序號(hào)教 學(xué) 內(nèi) 容課時(shí)分配講課實(shí)驗(yàn)習(xí)題小計(jì)1第一章 算法概述4 42第

6、二章 遞歸與分治策略82103第三章 動(dòng)態(tài)規(guī)劃82104第四章 貪心算法62105第五章 回溯法446第六章 分支限界法447第七章 隨機(jī)化算法227第八章 NP完全性問題44合 計(jì)40646五、 使用教材及主要參考書課程教材：1. 王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析.電子工業(yè)出版社.2007年5月主要參考書：1. 呂國(guó)英.算法設(shè)計(jì)與分析 .清華大學(xué)出版社. 2006.3(1) 2. 王曉東. 算法設(shè)計(jì)與實(shí)驗(yàn)題解. 電子工業(yè)出版社 2006.9(1) 3. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein (2001), Introdu

7、ction to Algorithms (the second edition). The MIT Press，中文名算法導(dǎo)論（第二版）（影印版），高等教育出版社六、 考核方式考核方式：平時(shí)作業(yè)、課堂回答問題及考勤、實(shí)驗(yàn)占30%，期末考試占70%。 制定：高艷霞執(zhí)筆，教研室集體討論 審定： 批準(zhǔn)： 2007年11月算法設(shè)計(jì)與分析實(shí)驗(yàn)教學(xué)大綱課程名稱（中、英文）：算法設(shè)計(jì)與分析、Design and Analysis of Algorithm課程編號(hào)： 課程總學(xué)時(shí)/學(xué)分： 45/3 實(shí)驗(yàn)總學(xué)時(shí)： 6適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)、網(wǎng)絡(luò)工程、軟件工程一、實(shí)驗(yàn)教學(xué)目標(biāo)算法設(shè)計(jì)與分析旨在教會(huì)學(xué)生處理各

8、種問題的方法，而通過實(shí)驗(yàn)，使學(xué)生能夠把所學(xué)的方法用于具體的問題，并對(duì)所用算法進(jìn)行比較分析，從而提高學(xué)生分析問題、解決問題的能力。只有通過實(shí)驗(yàn)，學(xué)生才能判定自己所擬算法是否正確，是否算得上一個(gè)較優(yōu)算法。通過該課程的實(shí)驗(yàn)，使學(xué)生對(duì)課堂中所講述的內(nèi)容有一個(gè)直觀的認(rèn)識(shí)，更好地掌握所學(xué)的知識(shí)。同時(shí)培養(yǎng)學(xué)生的實(shí)際動(dòng)手能力，加強(qiáng)學(xué)生創(chuàng)新思維能力的培養(yǎng)。二、主要儀器設(shè)備名稱計(jì)算機(jī)、C語言或C+語言。三、實(shí)驗(yàn)基本要求算法設(shè)計(jì)與分析是計(jì)算機(jī)相關(guān)專業(yè)的專業(yè)基礎(chǔ)課程，其先修課程有數(shù)據(jù)結(jié)構(gòu)和至少一門高級(jí)語言。算法設(shè)計(jì)與分析課程將覆蓋計(jì)算機(jī)軟件實(shí)現(xiàn)中的大部分算法，并具有一定的深度和廣度，使學(xué)生對(duì)計(jì)算機(jī)常用算法有一個(gè)全盤的

9、了解；通過此課的學(xué)習(xí)，學(xué)生應(yīng)該具有針對(duì)所給的問題設(shè)計(jì)和實(shí)現(xiàn)高效算法的能力。通過上機(jī)實(shí)驗(yàn)，將使學(xué)生熟悉、掌握課堂教學(xué)中所學(xué)的大部分算法。同時(shí)，上機(jī)實(shí)習(xí)是對(duì)學(xué)生在軟件設(shè)計(jì)方面的綜合訓(xùn)練，包括問題分析，總體結(jié)構(gòu)設(shè)計(jì)，用戶界面設(shè)計(jì)，程序設(shè)計(jì)基本技能和技巧等，以培養(yǎng)良好的編程風(fēng)格和科學(xué)作風(fēng)。通過理論聯(lián)系實(shí)際，以最終提高學(xué)生動(dòng)手操作的能力以及分析問題的能力。四、實(shí)驗(yàn)項(xiàng)目設(shè)置與內(nèi)容序號(hào)實(shí)驗(yàn)名稱內(nèi)容提要實(shí)驗(yàn)學(xué)時(shí)每組人數(shù)實(shí)驗(yàn)類型開出要求1遞歸與分治法用分治法查找數(shù)組元素的最大值和最小值用分治法實(shí)現(xiàn)歸并排序算法21設(shè)計(jì)二選一2動(dòng)態(tài)規(guī)劃0/1背包問題有一個(gè)背包容量為，輸入個(gè)物品，每個(gè)物品有重量i，以及物品放入背包中

10、所得的收益。問選擇放入的物品，要么全部放入，要么不放，不超過背包的容量，且得到的收益最好。最長(zhǎng)公共子序列給定兩個(gè)序列X和Y，根據(jù)動(dòng)態(tài)規(guī)劃的思想求X和Y的最長(zhǎng)公共子序列。21設(shè)計(jì)二選一3貪心算法背包問題有一個(gè)背包容量為，輸入個(gè)物品，每個(gè)物品有重量，以及物品放入背包中所得的收益。問選擇放入的物品，不超過背包的容量，且得到的收益最好。最短路徑已知圖，邊的權(quán)值矩陣，求某點(diǎn)到其他各點(diǎn)的路徑最短。21設(shè)計(jì)二選一4回溯法8-皇后問題:在國(guó)際象棋盤上放八個(gè)皇后，要求任一皇后吃不到別人，也不受其他皇后的攻擊，求出問題的所有解。21設(shè)計(jì)選做五、實(shí)驗(yàn)考核根據(jù)學(xué)生的實(shí)驗(yàn)預(yù)習(xí)、實(shí)驗(yàn)紀(jì)律、考勤、實(shí)驗(yàn)動(dòng)手能力及實(shí)驗(yàn)報(bào)告結(jié)果，進(jìn)行綜合評(píng)定，給出A、B、C。六、教材及主要教學(xué)參考書課程教材：1王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析.電子工業(yè)出版社.2007年5月主要參考書：1呂國(guó)英.算法設(shè)計(jì)與分析 .清華大學(xué)出版社. 2006.3(1)2王曉東. 算法設(shè)計(jì)與實(shí)驗(yàn)題解. 電子工業(yè)出版社 2006.9(1)3T. H. Cormen, C. E.