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

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

武漢工程大學(xué)

本文來(lái)源：http://m.zhongzhouzhikong.com/wuhangongchengdaxue/cankaoshumu_388934.html