|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
1
湖南師范大學碩士研究生入學考試自命題考試大綱
考試科目代碼：[] 考試科目名稱：計算機算法設計與分析
一、試卷結構
1) 試卷成績及考試時間
考試時間為 180 分鐘。
2)答題方式：閉卷、筆試
3)試卷內容結構
計算機算法設計與分析部分 100%
4)題型結構
a: 填空題，10 小題， 占 20%
b: 簡答題，4 小題， 占 20%
c: 解答題(包括證明題)，4 小題，占 60%
二、考試內容與考試要求
1、 算法概述
考試內容
算法的概念和性質 算法的復雜性概念和分析角度 計算時間的漸近表示及其相關性質
NP 完全性理論中的基本概念
考試要求
（1）理解算法的概念和性質。
（2）理解程序與算法的區別和內在聯系。
（3）理解算法的復雜性概念和時間復雜度分析角度（最佳、最差和平均情況）。
（4）掌握計算時間的漸近表示及其相關性質。
（5）掌握算法復雜度分析的基本技術和方法。
（6）理解 P 和 NP 類問題的概念，了解 Cook 定理和幾個 NP 完全問題。
2、 遞歸算法設計與分析
考試內容
遞歸的概念 遞歸算法的實現機制 設計和分析遞歸算法的一般方法 消去遞歸
考試要求
（1）理解遞歸的概念。
（2）掌握遞歸算法的實現機制。
2
（3）掌握設計和分析遞歸算法的一般方法。
（4）了解如何消去遞歸。
3、 分治策略
考試內容
分治法的基本思想和適用條件 分治法的效率分析 分治法應用的經典實例
考試要求
（1）掌握分治法的基本思想和適用條件。
（2）掌握分治法的效率分析的一般性技巧。
（3）掌握分治法應用的經典實例，如二分搜索法，快速排序，歸并排序，大整數乘法，Strassen
矩陣乘法，循環賽安排，線性選擇問題等。掌握這些算法的基本思路、實現技術以及復雜度
分析過程。
（4）通過學習分治法，會用某高級語言對算法進行描述。
4、動態規劃
考試內容
動態規劃的基本原理和應用條件 動態規劃的效率分析 動態規劃應用的經典實例
考試要求
（1）掌握動態規劃的基本思想。
（2）掌握動態規劃的兩個基本要素：最優子結構性質和重疊子問題性質。
（3）了解動態規劃的一般性求解步驟，會將問題化為多階段圖，并能對具體問題寫出正確
的遞推公式。
（4）掌握動態規劃應用的經典實例：多段圖、矩陣連乘、0/1 背包、每對節點之間的最短路
徑、最優二分檢索樹、最長公共子序列以及最大子段和問題。針對這些實例，會用某高級語
言對算法進行描述，掌握分析動態規劃算法效率分析的一般性方法。
（5）理解動態規劃與分治法的區別。
5、貪心法
考試內容
貪心法的基本原理和基本要素 貪心算法的效率分析和可靠性（正確性）分析 貪 心 法
應用的經典實例
考試要求
（1）掌握貪心法的基本原理。
（2）掌握動態規劃的兩個基本要素：最優子結構性質和貪心選擇性質。針對一些簡單的問
題，會證明算法的正確性。
（3）掌握典型問題如背包問題、最優裝載問題、帶有限期的作業排序問題、活動安排問題、
最小生成樹、單源點最短路徑等的算法設計原理、實現技術以及算法效率的分析。
（4）掌握貪心法與動態規劃算法的區別。
6、回溯法
考試內容
回溯法的基本思想 剪枝函數的設計 回溯法的效率分析 回溯法應用的經典實例
考試要求
（1）掌握利用回溯法解決問題的基本思想和算法的基本框架。
（2）理解活結點、死結點和擴展結點的概念。
（3）掌握回溯法在下述問題上的應用：n 皇后問題、最優裝載問題、0/1 背包、圖的 m 著
3
色問題和旅行售貨員問題。針對這些問題，掌握剪枝函數的設計和遞歸回溯法的實現，能準
確地分析回溯法的效率。
7、分支限界法
考試內容
分支限界法的基本思想 分隊列式分支限界法和優先隊列式分支限界法 分支限界法
應用的經典實例
考試要求
（1）掌握回溯法和分支限界法的不同。
（2）掌握并區分隊列式分支限界法和優先隊列式分支限界法的基本思想，能用多種不同方
法解法同一問題，并分析各方法的效率。
（3）掌握不同分支限界法在下述問題上的應用：最優裝載問題、0/1 背包和旅行售貨員問題。
針對這些問題，掌握剪枝函數的設計，了解算法的實現機制，能準確地分析各算法的效率。
三、參考書目
王曉東. 計算機算法設計與分析（第 4 版）. 電子工業出版社, 2012
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
