算法分析與設計考試大綱

1、石河子大學信息科學與技術學院碩士研究生入學考試算法設計與分析考試大綱算法設計與分析是石河子大學電子信息專業(yè)碩士研究生入學考試科目之一，以高等學校計算機學科優(yōu)秀本科畢業(yè)生能達到的及格或及格以上水平為評價標準，要求考生全面、系統(tǒng)地掌握“算法設計與分析”的基本概念、基本原理和典型方法，能靈活運用所學知識闡述求解實際問題的方法和途徑。目的在于考察考生理論素養(yǎng)與專業(yè)知識，便于優(yōu)秀人才的選拔。一、考試基本要求1掌握算法的基本概念和分析算法的基本方法; 2掌握分治策略、貪心方法、動態(tài)規(guī)劃、回溯法、分支-限界法、概率算法、近似算法、NP完全性理論的基本原理。 3熟練掌握求解典型問題的算法的設計思想和實現(xiàn)方法，

2、并能靈活運用，以能有效求解新的問題。 4具有較高的算法設計能力和設計技巧，可能設計出解決實際問題的有效算法。 5了解算法研究領域的現(xiàn)狀與趨勢。二、考試方式與時間碩士研究生入學算法設計與分析考試為筆試，考試時間為120分鐘。三、考試主要內(nèi)容和要求（一）考試內(nèi)容1、算法復雜度性分析1）理解算法的復雜性概念；2）掌握計算時間的漸進表示及其相關性質；3）掌握算法復雜度分析的基本方法。2、遞歸與分治策略1）理解遞歸和分治的概念，掌握遞歸和分治算法的適用條件；2）掌握遞歸和分治算法的實現(xiàn)機制；3）掌握設計和分析遞歸和分治算法的基本方法；4）掌握如何消除遞歸的技巧和方法。3、動態(tài)規(guī)劃1）掌握動態(tài)規(guī)劃的基本思

3、想以及兩個基本要素；2）熟悉動態(tài)規(guī)劃的求解步驟和實現(xiàn)機制；3）掌握動態(tài)規(guī)劃應用的經(jīng)典案例，比如0/1 背包、最短路徑、最大字段和以及最長公共子序列等4）理解動態(tài)規(guī)劃和分治方法的區(qū)別。4、貪心算法1）掌握貪心算法的基本原理和基本要素；2）掌握動態(tài)規(guī)劃和貪心算法的區(qū)別；3）掌握經(jīng)典問題的貪心算法設計原理、實現(xiàn)技術以及效率分析，比如背包問題、最優(yōu)裝載問題、單源點最短路徑等。5、回溯法1）掌握回溯法的基本思想和基本框架；2）理解活結點、死結點和擴展結點的概念；3）熟練分析回溯法的效率；4）掌握回溯法在經(jīng)典問題上的應用，比如最優(yōu)裝載、0/1 背包、圖著色等。6、分支限界法1）掌握分支限界法的基本原理；2

4、）掌握并區(qū)分隊列式分支限界法和優(yōu)先隊列式分支界定法的基本思想與區(qū)別；3）能夠實現(xiàn)多種分支限界算法求解同一問題，并準確分析各自的效率；4）掌握分支限界法與回溯法的不同；5）掌握分支限界法在經(jīng)典問題上的應用，比如最優(yōu)裝載、0/1 背包等。7、概率和近似算法1）掌握兩種方法的基本原理；2）掌握兩者之間的區(qū)別；3）針對簡單問題能夠分析設計相應算法。（二）考試要求1、基本要求：要求考生掌握遞歸、分治策略、貪心方法、動態(tài)規(guī)劃、回溯法、分支限界法等經(jīng)典算法的基本原理和思想，熟練掌握求解典型問題的算法設計思想和實現(xiàn)方法，從而全面、系統(tǒng)地掌握“算法設計與分析”的基本概念、基本原理和典型方法，進而具備較高的算法設計能力與技巧，可設計出解決實際問題的有效算法。2、分值比例：算法復雜度分析： 10遞歸與分治策略： 20動態(tài)規(guī)劃： 20貪心算法： 20回溯法： 10分支限界法： 15近似或概率算法：5%2、題型分布：單項選