武漢工程大學2020年碩士研究生復試

《算法設計與分析》考試大綱

第一部分 考試說明

一、考試性質

    《算法設計與分析》是武漢工程大學計算機科學與技術及相關專業碩士研究生入學考試科目之一，以高等學校計算機學科優秀本科畢業生能達到的及格或及格以上水平為評價標準，要求考生全面、系統地掌握“算法設計與分析”的基本概念、基本原理和典型方法，能靈活運用所學知識闡述求解實際問題的方法和途徑。目的在于考察考生理論素養與專業知識，便于優秀人才的選拔。

    考試對象為參加碩士生入學考試的應屆或非應屆碩士畢業生，以及具有同等學歷的在職人員。

二、評價目標

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

    2.掌握分治策略、貪心方法、動態規劃、回溯法、分支-限界法、圖算法、概率算法、近似算法、NP完全性理論的基本原理。

    3.熟練掌握求解典型問題的算法的設計思想和實現方法，并能靈活運用，以能有效求解新的問題。

    4.具有較高的算法設計能力和設計技巧，可能設計出解決實際問題的有效算法。

    5.了解算法研究領域的現狀與趨勢。

三、考試形式與試卷結構

    1.考試形式：閉卷、筆試、上機。

    2.答題時間：筆試120分鐘，上機90分鐘。

    3.試卷題型：填空題、選擇題、改錯題、簡答題、計算題、算法分析題、程序設計題。每年在上述題型中選用3種。重點考察對本課程知識點的掌握程度和綜合應用能力。

四、參考教材

1.王曉東編著《算法設計與分析》（清華大學出版社）

2.李春葆、李筱馳、等《算法設計與分析（第二版）》（清華大學出版社）

    3.蘇德富、鐘誠著《計算機算法設計與分析》（電子工業出版社）

    4.POJ部分測試題（poj.org）

第二部分 考查要點

1.算法分析基礎

1) 熟悉漸近表示法，掌握漸近符號O等的定義，能判斷一個較復雜的函數屬于哪個漸近增長階；

2) 熟悉一些算法復雜度分析的方法，比如說主定理法等，能對結構復雜的算法進行分析。

2.算法設計基礎

1) 熟悉算法設計的三大技巧：貪心算法、分而治之，動態規劃。

2) 能證明各種算法的正確性。

3) 能用這三大技巧設計相應的算法。

3.NP完備性理論及近似算法

1) 了解并掌握NP 完備性理論及其實際意義；

2) 熟悉多項式規約。掌握證明一個問題NP完全性的基本方法和思路；

3) 熟悉最小點覆蓋、最大獨立集等問題的NP完備性證明；

4) 了解并掌握近似算法的設計步驟與技巧，掌握點覆蓋等問題的近似算法的設計。

4.經典算法

    熟悉排序、最短路徑、最小生成樹、最大匹配、最大流、最大公共字符串等問題的一些經典算法。

5.其它智力算法問題