算法设计与分析考试大纲.pdf

算法设计与分析考试大纲 本考试大纲涵盖了算法设计与分析的基础知识和高级概念，旨在考查学生对算法的理解和应用能力。以下是考试大纲的详细解释和知识点总结： 一、教学大纲 * 理解算法和程序的差别 * 理解判断问题和优化问题这两类计算问题 这些基础知识点是算法设计与分析的入门课程，学生需要了解算法和程序的区别，以及判断问题和优化问题的定义和区别。 二、算法分析与设计基础 * 理解指数增长的规模 * 掌握渐近符号 O、Ω、θ 的含义，能判断一个函数属于哪个渐近增长阶 * 理解贪心算法，会用贪心算法解工作安排问题（Interval scheduling），能证明其正确性 * 理解分治算法的思想 * 理解动态规划算法的思想，对动态规划类型的问题能建立起基本的递归关系式并能用从底至上的方法来求解 这些知识点是算法分析与设计的基础知识，学生需要了解算法的时间和空间复杂度，掌握渐近符号的含义，并了解贪心算法、分治算法和动态规划算法的思想和应用。 三、网络流 * 了解并掌握网络最大流问题和最小割问题及其算法 * 给出一个图能求出其对应的最大流或者最小割 网络流是算法设计与分析中的一个重要领域，学生需要了解网络最大流问题和最小割问题的定义、算法和应用。 四、NP 完备性理论 * 理解什么是多项式归约（polynomial-time reduction） * 知道怎样从一个问题多项式归约到另一个问题 * 掌握同一个问题的最优化问题如何多项时间归约到该问题的判断问题 * 熟悉 NP 和 NPC 的概念 * 牢记证明一个问题属于 NPC 的基本步骤 * 理解一些基本 NPC 问题的证明思路 * 可以证明一些简单问题的 NPC 性 NP 完备性理论是算法设计与分析中的一个高级概念，学生需要了解多项式归约的定义和应用，掌握 NP 和 NPC 的概念，并了解证明一个问题属于 NPC 的基本步骤。 五、近似算法 * 理解什么是近似算法 * 能为平衡装配（load balancing）问题设计一个近似算法，并且能证明其正确性 * 理解点覆盖问题的定价算法（Pricing method），证明该方法能得到一个 2 倍近似解 * 理解点覆盖问题的线性规划模型和松弛求解方法 * 理解背包问题任意精度的近似算法 近似算法是算法设计与分析中的一个重要领域，学生需要了解近似算法的定义和应用，并掌握近似算法的设计和证明。 六、智能算法 * 理解怎样用神经网络来进行建模 * 理解智能计算和普通计算的差别，智能计算的特点 智能算法是算法设计与分析中的一个高级概念，学生需要了解智能计算的定义和应用，并掌握神经网络的建模和应用。 七、答题注意事项 * 要求要写明计算过程的题目，不要只写答案 * 要求写算法的题目，不要写一个程序 * 证明题要注意逻辑和推导过程 这些注意事项是学生在考试中需要注意的重要问题，学生需要写明计算过程，写算法的题目，并注意逻辑和推导过程。