2021武漢工程大學算法設(shè)計與分析研究生考試大綱 正文

武漢工程大學2021年碩士研究生復試
《算法設(shè)計與分析》考試大綱
第一部分 考試說明
一、考試性質(zhì)
    《算法設(shè)計與分析》是武漢工程大學計算機科學與技術(shù)及相關(guān)專業(yè)碩士研究生入學考試科目之一，以高等學校計算機學科優(yōu)秀本科畢業(yè)生能達到的及格或及格以上水平為評價標準，要求考生全面、系統(tǒng)地掌握“算法設(shè)計與分析”的基本概念、基本原理和典型方法，能靈活運用所學知識闡述求解實際問題的方法和途徑。目的在于考察考生理論素養(yǎng)與專業(yè)知識，便于優(yōu)秀人才的選拔。
    考試對象為參加碩士生入學考試的應(yīng)屆或非應(yīng)屆碩士畢業(yè)生，以及具有同等學歷的在職人員。
二、評價目標
    1.掌握算法的基本概念和分析算法的基本方法;
    2.掌握分治策略、貪心方法、動態(tài)規(guī)劃、回溯法、分支-限界法、圖算法、概率算法、近似算法、NP完全性理論的基本原理。
    3.熟練掌握求解典型問題的算法的設(shè)計思想和實現(xiàn)方法，并能靈活運用，以能有效求解新的問題。
    4.具有較高的算法設(shè)計能力和設(shè)計技巧，可能設(shè)計出解決實際問題的有效算法。
    5.了解算法研究領(lǐng)域的現(xiàn)狀與趨勢。
三、考試形式與試卷結(jié)構(gòu)
    1.考試形式：閉卷、筆試、上機。
    2.答題時間：筆試120分鐘，上機90分鐘。
    3.試卷題型：填空題、選擇題、改錯題、簡答題、計算題、算法分析題、程序設(shè)計題。每年在上述題型中選用3種。重點考察對本課程知識點的掌握程度和綜合應(yīng)用能力。
四、參考教材
1.王曉東編著《算法設(shè)計與分析》（清華大學出版社）
2.李春葆、李筱馳、等《算法設(shè)計與分析（第二版）》（清華大學出版社）
    3.蘇德富、鐘誠著《計算機算法設(shè)計與分析》（電子工業(yè)出版社）
    4.POJ部分測試題（poj.org）
第二部分 考查要點
1.算法分析基礎(chǔ)
1) 熟悉漸近表示法，掌握漸近符號O等的定義，能判斷一個較復雜的函數(shù)屬于哪個漸近增長階；
2) 熟悉一些算法復雜度分析的方法，比如說主定理法等，能對結(jié)構(gòu)復雜的算法進行分析。
2.算法設(shè)計基礎(chǔ)
1) 熟悉算法設(shè)計的三大技巧：貪心算法、分而治之，動態(tài)規(guī)劃。
2) 能證明各種算法的正確性。
3) 能用這三大技巧設(shè)計相應(yīng)的算法。
3.NP完備性理論及近似算法
1) 了解并掌握NP 完備性理論及其實際意義；
2) 熟悉多項式規(guī)約。掌握證明一個問題NP完全性的基本方法和思路；
3) 熟悉最小點覆蓋、最大獨立集等問題的NP完備性證明；
4) 了解并掌握近似算法的設(shè)計步驟與技巧，掌握點覆蓋等問題的近似算法的設(shè)計。
4.經(jīng)典算法
    熟悉排序、最短路徑、最小生成樹、最大匹配、最大流、最大公共字符串等問題的一些經(jīng)典算法。
5.其它智力算法問題
 

武漢工程大學

本文來源：http://www.qiang-kai.com/wuhangongchengdaxue/cankaoshumu_388934.html