算法設(shè)計與分析教學(xué)大綱及實驗大綱

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

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

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

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

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

6、二章 遞歸與分治策略82103第三章 動態(tài)規(guī)劃82104第四章 貪心算法62105第五章 回溯法446第六章 分支限界法447第七章 隨機化算法227第八章 NP完全性問題44合 計40646五、 使用教材及主要參考書課程教材：1. 王曉東.計算機算法設(shè)計與分析.電子工業(yè)出版社.2007年5月主要參考書：1. 呂國英.算法設(shè)計與分析 .清華大學(xué)出版社. 2006.3(1) 2. 王曉東. 算法設(shè)計與實驗題解. 電子工業(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)論（第二版）（影印版），高等教育出版社六、 考核方式考核方式：平時作業(yè)、課堂回答問題及考勤、實驗占30%，期末考試占70%。 制定：高艷霞執(zhí)筆，教研室集體討論 審定： 批準： 2007年11月算法設(shè)計與分析實驗教學(xué)大綱課程名稱（中、英文）：算法設(shè)計與分析、Design and Analysis of Algorithm課程編號： 課程總學(xué)時/學(xué)分： 45/3 實驗總學(xué)時： 6適用專業(yè)：計算機科學(xué)與技術(shù)專業(yè)、網(wǎng)絡(luò)工程、軟件工程一、實驗教學(xué)目標算法設(shè)計與分析旨在教會學(xué)生處理各

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

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

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