科目代碼：2006

科目名稱：算法設(shè)計與分析

第一部分 課程評價目標(biāo)

一、課程目標(biāo)

算法設(shè)計與分析，主要使學(xué)生掌握算法設(shè)計的常用方法，提高學(xué)生算法設(shè)計與復(fù)雜性分析的素質(zhì)和能力，為學(xué)生能夠獨立進行算法的設(shè)計和計算復(fù)雜性的分析奠定比較堅實的基礎(chǔ)，以便使學(xué)生在將來從事計算機領(lǐng)域或其它有關(guān)領(lǐng)域的研究中，能夠運用這些方法來設(shè)計解決一些常用的或較為復(fù)雜的實際問題的算法，并力爭做到快捷、有效，從而提高程序的質(zhì)量并較好地解決科學(xué)研究與實際應(yīng)用中所遇到的問題。

二、基本要求

要求學(xué)生掌握計算機科學(xué)技術(shù)領(lǐng)域中的一些常用的、經(jīng)典的算法設(shè)計技術(shù)，學(xué)會分析算法、估計算法的時空復(fù)雜性，在非數(shù)值計算的層面上，具備把實際問題抽象描述為數(shù)學(xué)模型的能力，同時能針對不同的問題對象設(shè)計有效的算法，用典型的方法來解決科學(xué)研究及實際應(yīng)用中所遇到的問題。并且具備分析算法效率的能力，能夠科學(xué)地評估有關(guān)算法和處理方法的效率。

三、評價目標(biāo)

1.掌握算法的基本概念和分析算法的基本方法;

2.掌握分治、動態(tài)規(guī)劃、貪心算法、分支限界法、圖的遍歷、隨機算法、近似算法、NP完全性問題的基本原理。

3.熟練掌握求解典型問題的算法設(shè)計思想和實現(xiàn)方法，能夠有效運用，以能高效解決新的問題。

4.具有較強的算法設(shè)計和分析能力，具備設(shè)計出解決實際應(yīng)用與科學(xué)研究問題的有效算法。

5.了解算法研究領(lǐng)域的現(xiàn)狀與發(fā)展。

第二部分　考查要點

1.基本概念

算法的基本定義、基本性質(zhì)，算法復(fù)雜度分析的基本方法。

2.遞歸算法設(shè)計技術(shù)

遞歸算法的實現(xiàn)機制，設(shè)計和分析遞歸算法的一般方法;歸納法等基本方法的運用。

3.分治法

分治法的基本原理，典型問題如二分檢索、合并排序、快速排序、矩陣乘法、大整數(shù)乘法、最近點對問題等的算法設(shè)計原理、實現(xiàn)技術(shù)及其應(yīng)用。

4.貪心方法

圖和貪心方法的基本原理和性質(zhì)，貪心解的最優(yōu)性證明;典型問題如最短路徑問題、最小耗費生成樹、文件壓縮等的算法設(shè)計原理、實現(xiàn)技術(shù)及其應(yīng)用。

5.動態(tài)規(guī)劃

動態(tài)規(guī)劃的基本原理和方法、最優(yōu)性原理、無后效性、狀態(tài)轉(zhuǎn)移方程;典型問題如最長公共子序列問題、矩陣鏈相乘、所有點對的的最短路徑、背包問題等的算法設(shè)計原理、實現(xiàn)技術(shù)及其應(yīng)用。

6.圖的遍歷

廣度優(yōu)先搜索、深度優(yōu)先搜索的原理、性質(zhì)和異同;回溯法的原理和技術(shù)、分支-限界法的原理和技術(shù);典型問題如8皇后問題、3著色問題等的算法設(shè)計原理、實現(xiàn)技術(shù)及其應(yīng)用。

7.隨機算法和近似算法

隨機算法、近似算法的原理和方法;關(guān)于典型問題如Las Vegas方法、 Monte Carlo方法、TSP問題、裝箱問題、頂點覆蓋、子集和問題等問題的近似算法討論。

8.NP完全問題

NP完全性的概念、可滿足性、NP完全性證明;了解典型NP完全問題如頂點覆蓋、獨立集、團集問題等。