科目代碼：2006

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

第一部分 課程評(píng)價(jià)目標(biāo)

一、課程目標(biāo)

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

二、基本要求

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

三、評(píng)價(jià)目標(biāo)

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

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

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

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

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

第二部分　考查要點(diǎn)

1.基本概念

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

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

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

3.分治法

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

4.貪心方法

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

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

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

6.圖的遍歷

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

7.隨機(jī)算法和近似算法

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

8.NP完全問題

NP完全性的概念、可滿足性、NP完全性證明;了解典型NP完全問題如頂點(diǎn)覆蓋、獨(dú)立集、團(tuán)集問題等。