|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
華中科技大學博士研究生入學《算法設計與分析》考試大綱
（代碼：3542）
第一部分 考試說明
一、考試性質
《算法設計與分析》是華中科技大學計算機科學與技術及相關專業博士研究生入學考
試科目之一，以高等學校計算機學科優秀碩士畢業生能達到的及格或及格以上水平為評價標
準，要求考生全面、系統地掌握“算法設計與分析”的基本概念、基本原理和典型方法，能
靈活運用所學知識闡述求解實際問題的方法和途徑。目的在于考察考生理論素養與專業知
識，便于優秀人才的選拔。
考試對象為參加博士生入學考試的應屆或非應屆碩士畢業生，以及具有同等學歷的在
職人員。
二、評價目標
1．掌握算法的基本概念和分析算法的基本方法；
2．掌握分治策略、貪心方法、動態規劃、回溯法、分支-限界法、圖算法、概率算法、
近似算法、NP 完全性理論的基本原理。
3．熟練掌握求解典型問題的算法的設計思想和實現方法，并能靈活運用，以能有效求
解新的問題。
4．具有較高的算法設計能力和設計技巧，可能設計出解決實際問題的有效算法。
5．了解算法研究領域的現狀與趨勢。
三、考試形式與試卷結構
1．考試形式：閉卷、筆試。
2．答題時間：180 分鐘。
3．試卷題型：填空題、選擇題、改錯題、簡答題、計算題、證明題、算法設計與綜合
應用題。每年在上述題型中選用 3～5 種。重點考察對本課程知識點的掌握程度和綜合應用
能力。
第二部分 考查要點
1．基本概念
算法的基本定義、基本性質，算法復雜度分析的基本技術和方法，計算時間的漸進表示
及其相關性質。
2．遞歸算法設計技術
遞歸算法的實現機制，設計和分析遞歸算法的一般方法，消去遞歸；遞歸關系式的計算，
數學歸納法、主方法等基本方法的運用。
3．分治法
分治法的基本原理，典型問題如二分檢索、歸并排序、快速排序、選擇問題、Strassen
矩陣乘法、最近點對等的算法設計原理、實現技術及其應用。
4．貪心方法
貪心方法的基本原理和性質、最優子結構性，貪心解的最優性證明；典型問題如背包問
題、帶有限期的作業排序問題、活動選擇問題、Haffman 編碼、最優歸并模式、最小生成樹、
單源點最短路徑等的算法設計原理、實現技術及其應用。
5．動態規劃
動態規劃的基本原理和方法、最優性原理、無后效性、狀態轉移方程；典型問題如多段
圖、0/1 背包、每對節點之間的最短路徑、最優二分檢索樹、貨郎擔問題、矩陣鏈乘、裝配
線調度等的算法設計原理、實現技術及其應用。
6．搜索算法
寬度優先搜索、深度優先搜索、D-Search 搜索的原理、性質和異同；回溯法的原理和技
術、分支-限界法的原理和技術；а -в 截斷、LC-檢索的原理和方法；典型問題如雙連通分
圖、與或樹、對策樹、8-皇后問題、子集和數問題、圖的著色問題等的算法設計原理、實現
技術及其應用。
7．圖的算法設計
圖的基本定義；最小生成樹算法（Kruskal 算法和 Prim 算法）、最短路徑算法
（Bellman-Ford 算法、Dijkstra 算法、Floyd 算法）、最大流算法，相關算法的應用。
8．概率算法和近似算法
概率分析、隨機算法、近似算法的原理和方法；關于典型問題如頂點覆蓋、旅行商問題、
子集和數等問題的近似算法討論。
9．NP 完全理論
NP 完全性的概念、可歸約性、NP 完全性證明；了解典型 NP 完全問題如哈密頓回路問
題、旅行商問題、子集和數問題、頂點覆蓋問題等。
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
