|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
福 州 大 學
2017 年博士研究生入學考試專業課課程（考試）大綱
一、考試科目名稱: 算法設計與分析
二、招生學院和專業：數學與計算機科學學院
基本內容:
第一部分 考試說明
一、 考試性質
《算法設計與分析》作為福州大學計算機科學與技術及相關專業博士研究生入學考試科目之
一，以高等院校計算機專業碩士教學的較高層次為基準，要求考生掌握算法設計的常用方法，
具備算法設計與復雜性分析的素質和能力，為考生后續能夠獨立進行算法的設計和計算復雜性
的分析奠定比較堅實的基礎。該考試目的在于考察考生的專業綜合素質和問題求解能力，便于
優秀人才的選拔?？荚噷ο鬄閰⒓硬┦可雽W考試的應屆或非應屆碩士畢業生，以及具有同等
學歷的在職人員。
二、 考核目標
1.掌握算法的基本概念和分析算法的基本方法;
2.掌握分治、動態規劃、貪心算法、分支限界法、圖的遍歷、隨機算法、近似算法、NP 完
全性問題的基本原理;
3.熟練掌握求解典型問題的算法設計思想和實現方法，能夠有效運用，以能高效解決新的
問題;
4.具有較強的算法設計和分析能力，具備設計出解決實際應用與科學研究問題的有效算法;
5.了解算法研究領域的現狀與發展。
三、 試卷結構
考試以閉卷筆試形式進行，題型包括填空題、選擇題、改錯題、簡答題、計算題、證明題、
算法設計綜合應用題。每年考試將從上述題型中抽取若干種（一般為 5 種左右），重點考察考生
的基礎知識、分析能力、設計及實際問題求解能力等。
第二部分 考察知識范圍
1.算法設計與分析的基本概念
算法的基本定義、基本性質，算法設計和算法復雜度分析的基本技術和方法，計算時間的
漸進表示及其相關性質。
2.遞歸算法設計技術
遞歸算法的特點和實現機制，設計和分析遞歸算法的一般方法，消去遞歸;遞歸關系式的計
算，數學歸納法、主方法等基本方法的運用。
3.分治方法
分治方法的基本原理，典型問題如二分檢索、合并排序、快速排序、線性選擇問題、Strassen
矩陣乘法、最近點對、循環賽日程表等問題的算法設計原理、實現技術及其應用。
4.動態規劃方法
動態規劃的基本原理和方法;使用動態規劃方法設計求解算法的適用問題的特點和基本步
驟;最優性原理、無后效性、狀態轉移方程;典型問題如 0/1 背包、每對節點之間的最短路徑、
最優二分檢索樹、最長公共子序列、矩陣鏈乘、裝配線調度等問題的算法設計原理、實現技術
及其應用;動態規劃方法的變種：備忘錄方法。
5. 貪婪方法
貪婪方法的基本原理和性質、最優子結構性，貪婪解的最優性證明;典型問題如背包問題、
活動選擇問題、Haffman 編碼、最小生成樹、單源點最短路徑等的算法設計原理、實現技術及
其應用。
6. 圖的算法設計
圖的基本定義與表示和圖的基本算法;廣度優先搜索、深度優先搜索、拓撲排序、最小生成
樹算法(Kruskal 算法和 Prim 算法)、最短路徑問題的算法(Bellman-Ford 算法、Dijkstra 算法、
Floyd 算法)、最大流問題的算法(Ford-Fulkerson 算法);相關算法的應用。
7.概率算法和近似算法
概率分析、隨機算法、近似算法的原理和方法;關于典型問題如頂點覆蓋、旅行商問題、集
合覆蓋、子集和等問題的近似算法討論。
8.NP 完全理論
NP 完全性的概念、可歸約性、NP 完全性證明;了解典型 NP 完全問題如哈密頓回路問題、旅
行商問題、子集和問題、頂點覆蓋問題等。
參考書目 (包括作者、書目、出版社、出版時間、版次)：
[1] 算法導論[M], Thomas H Cormen, Chzrles E Leiseron, Ronald L Rivest, etc，第二版，
機械工業出版社，2006.
編制人簽名： 博士點負責人簽名： 院長審核簽名：
年 月 日
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
