算法分析与设计考试大纲

1、石河子大学信息科学与技术学院硕士研究生入学考试算法设计与分析考试大纲算法设计与分析是石河子大学电子信息专业硕士研究生入学考试科目之一，以高等学校计算机学科优秀本科毕业生能达到的及格或及格以上水平为评价标准，要求考生全面、系统地掌握“算法设计与分析”的基本概念、基本原理和典型方法，能灵活运用所学知识阐述求解实际问题的方法和途径。目的在于考察考生理论素养与专业知识，便于优秀人才的选拔。一、考试基本要求1掌握算法的基本概念和分析算法的基本方法; 2掌握分治策略、贪心方法、动态规划、回溯法、分支-限界法、概率算法、近似算法、NP完全性理论的基本原理。 3熟练掌握求解典型问题的算法的设计思想和实现方法，

2、并能灵活运用，以能有效求解新的问题。 4具有较高的算法设计能力和设计技巧，可能设计出解决实际问题的有效算法。 5了解算法研究领域的现状与趋势。二、考试方式与时间硕士研究生入学算法设计与分析考试为笔试，考试时间为120分钟。三、考试主要内容和要求（一）考试内容1、算法复杂度性分析1）理解算法的复杂性概念；2）掌握计算时间的渐进表示及其相关性质；3）掌握算法复杂度分析的基本方法。2、递归与分治策略1）理解递归和分治的概念，掌握递归和分治算法的适用条件；2）掌握递归和分治算法的实现机制；3）掌握设计和分析递归和分治算法的基本方法；4）掌握如何消除递归的技巧和方法。3、动态规划1）掌握动态规划的基本思

3、想以及两个基本要素；2）熟悉动态规划的求解步骤和实现机制；3）掌握动态规划应用的经典案例，比如0/1 背包、最短路径、最大字段和以及最长公共子序列等4）理解动态规划和分治方法的区别。4、贪心算法1）掌握贪心算法的基本原理和基本要素；2）掌握动态规划和贪心算法的区别；3）掌握经典问题的贪心算法设计原理、实现技术以及效率分析，比如背包问题、最优装载问题、单源点最短路径等。5、回溯法1）掌握回溯法的基本思想和基本框架；2）理解活结点、死结点和扩展结点的概念；3）熟练分析回溯法的效率；4）掌握回溯法在经典问题上的应用，比如最优装载、0/1 背包、图着色等。6、分支限界法1）掌握分支限界法的基本原理；2

4、）掌握并区分队列式分支限界法和优先队列式分支界定法的基本思想与区别；3）能够实现多种分支限界算法求解同一问题，并准确分析各自的效率；4）掌握分支限界法与回溯法的不同；5）掌握分支限界法在经典问题上的应用，比如最优装载、0/1 背包等。7、概率和近似算法1）掌握两种方法的基本原理；2）掌握两者之间的区别；3）针对简单问题能够分析设计相应算法。（二）考试要求1、基本要求：要求考生掌握递归、分治策略、贪心方法、动态规划、回溯法、分支限界法等经典算法的基本原理和思想，熟练掌握求解典型问题的算法设计思想和实现方法，从而全面、系统地掌握“算法设计与分析”的基本概念、基本原理和典型方法，进而具备较高的算法设计能力与技巧，可设计出解决实际问题的有效算法。2、分值比例：算法复杂度分析： 10递归与分治策略： 20动态规划： 20贪心算法： 20回溯法： 10分支限界法： 15近似或概率算法：5%2、题型分布：单项选