計(jì)算機(jī)算法設(shè)計(jì)與分析

PAGEPAGE3湖南師范大學(xué)碩士研究生入學(xué)考試自命題考試大綱考試科目代碼：[]考試科目名稱：計(jì)算機(jī)算法設(shè)計(jì)與分析一、試卷結(jié)構(gòu)1)試卷成績及考試時(shí)間本試卷滿分為100分，考試時(shí)間為180分鐘。2)答題方式：閉卷、筆試3)試卷內(nèi)容結(jié)構(gòu)計(jì)算機(jī)算法設(shè)計(jì)與分析部分100%4)題型結(jié)構(gòu)a:填空題，10小題，共20分b:簡答題，4小題，共20分c:解答題(包括證明題)，4小題，共60分二、考試內(nèi)容與考試要求算法概述考試內(nèi)容算法的概念和性質(zhì) 算法的復(fù)雜性概念和分析角度 計(jì)算時(shí)間的漸近表示及其相關(guān)性質(zhì) NP完全性理論中的基本概念考試要求（1）理解算法的概念和性質(zhì)。（2）理解程序與算法的區(qū)別和內(nèi)在聯(lián)系。（3）理解算法的復(fù)雜性概念和時(shí)間復(fù)雜度分析角度（最佳、最差和平均情況）。（4）掌握計(jì)算時(shí)間的漸近表示及其相關(guān)性質(zhì)。（5）掌握算法復(fù)雜度分析的基本技術(shù)和方法。（6）理解P和NP類問題的概念，了解Cook定理和幾個(gè)NP完全問題。遞歸算法設(shè)計(jì)與分析考試內(nèi)容遞歸的概念 遞歸算法的實(shí)現(xiàn)機(jī)制 設(shè)計(jì)和分析遞歸算法的一般方法 消去遞歸考試要求（1）理解遞歸的概念。（2）掌握遞歸算法的實(shí)現(xiàn)機(jī)制。（3）掌握設(shè)計(jì)和分析遞歸算法的一般方法。（4）了解如何消去遞歸。分治策略考試內(nèi)容分治法的基本思想和適用條件 分治法的效率分析 分治法應(yīng)用的經(jīng)典實(shí)例考試要求（1）掌握分治法的基本思想和適用條件。（2）掌握分治法的效率分析的一般性技巧。（3）掌握分治法應(yīng)用的經(jīng)典實(shí)例，如二分搜索法，快速排序，歸并排序，大整數(shù)乘法，Strassen矩陣乘法，循環(huán)賽安排，線性選擇問題等。掌握這些算法的基本思路、實(shí)現(xiàn)技術(shù)以及復(fù)雜度分析過程。（4）通過學(xué)習(xí)分治法，會(huì)用某高級(jí)語言對(duì)算法進(jìn)行描述。4、動(dòng)態(tài)規(guī)劃考試內(nèi)容動(dòng)態(tài)規(guī)劃的基本原理和應(yīng)用條件 動(dòng)態(tài)規(guī)劃的效率分析 動(dòng)態(tài)規(guī)劃應(yīng)用的經(jīng)典實(shí)例考試要求（1）掌握動(dòng)態(tài)規(guī)劃的基本思想。（2）掌握動(dòng)態(tài)規(guī)劃的兩個(gè)基本要素：最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問題性質(zhì)。（3）了解動(dòng)態(tài)規(guī)劃的一般性求解步驟，會(huì)將問題化為多階段圖，并能對(duì)具體問題寫出正確的遞推公式。（4）掌握動(dòng)態(tài)規(guī)劃應(yīng)用的經(jīng)典實(shí)例：多段圖、矩陣連乘、0/1背包、每對(duì)節(jié)點(diǎn)之間的最短路徑、最優(yōu)二分檢索樹、最長公共子序列以及最大子段和問題。針對(duì)這些實(shí)例，會(huì)用某高級(jí)語言對(duì)算法進(jìn)行描述，掌握分析動(dòng)態(tài)規(guī)劃算法效率分析的一般性方法。（5）理解動(dòng)態(tài)規(guī)劃與分治法的區(qū)別。5、貪心法考試內(nèi)容貪心法的基本原理和基本要素 貪心算法的效率分析和可靠性（正確性）分析 貪心法應(yīng)用的經(jīng)典實(shí)例考試要求（1）掌握貪心法的基本原理。（2）掌握動(dòng)態(tài)規(guī)劃的兩個(gè)基本要素：最優(yōu)子結(jié)構(gòu)性質(zhì)和貪心選擇性質(zhì)。針對(duì)一些簡單的問題，會(huì)證明算法的正確性。（3）掌握典型問題如背包問題、最優(yōu)裝載問題、帶有限期的作業(yè)排序問題、活動(dòng)安排問題、最小生成樹、單源點(diǎn)最短路徑等的算法設(shè)計(jì)原理、實(shí)現(xiàn)技術(shù)以及算法效率的分析。（4）掌握貪心法與動(dòng)態(tài)規(guī)劃算法的區(qū)別。6、回溯法考試內(nèi)容回溯法的基本思想 剪枝函數(shù)的設(shè)計(jì) 回溯法的效率分析 回溯法應(yīng)用的經(jīng)典實(shí)例考試要求（1）掌握利用回溯法解決問題的基本思想和算法的基本框架。（2）理解活結(jié)點(diǎn)、死結(jié)點(diǎn)和擴(kuò)展結(jié)點(diǎn)的概念。（3）掌握回溯法在下述問題上的應(yīng)用：n皇后問題、最優(yōu)裝載問題、0/1背包、圖的m著色問題和旅行售貨員問題。針對(duì)這些問題，掌握剪枝函數(shù)的設(shè)計(jì)和遞歸回溯法的實(shí)現(xiàn)，能準(zhǔn)確地分析回溯法的效率。7、分支限界法考試內(nèi)容分支限界法的基本思想 分隊(duì)列式分支限界法和優(yōu)先隊(duì)列式分支限界法 分支限界法應(yīng)用的經(jīng)典實(shí)例考試要求（1）掌握回溯法和分支限界法的不同。（2）掌握并區(qū)分隊(duì)列式分支限界法和優(yōu)先隊(duì)列式分支限界法的基本思想，能用多種不同方法解法同一問題，并分析各方法的效率。（3）掌握不同分支限界法在下述問題上的應(yīng)用：最優(yōu)裝載問題、0/1背包和旅行售貨員