华中科技大学：《计算机算法基础》 复习要点

复习

复习

第一章导引 掌握: 1算法的定义及其性质(1.1节) 2算法分析的基础知识(12节) 重要的约定和假设 关于O,Ω,Q的定义 了解: 3 SPARKS语言(13节) 4常用数据结构(14节) 5.递归与消去递归(1.5节)

第一章 导引 掌握： 1.算法的定义及其性质(1.1节) 2.算法分析的基础知识(1.2节) • 重要的约定和假设 • 关于O，Ω， 的定义 了解： 3.SPARKS语言(1.3节) 4.常用数据结构(1.4节) 5.递归与消去递归(1.5节) 

第二章分治法 掌握: 基本知识 分治法的基本思想:2.1节 关系式的化简: 1)递推关系式的化简作业题 2)常用求和公式 在统计语句的频率时,求和公式的一般形式为: ∑∫() g(n)≤i≤h(n) 特殊形式∑=(m)∑=m+1)12=m l≤i<n ∑2=n(n+1)2n+1)6=(n) 1≤i≤n

第二章 分治法 掌握： 1.基本知识 分治法的基本思想：2.1节 关系式的化简： 1）递推关系式的化简 作业题 2）常用求和公式 在统计语句的频率时，求和公式的一般形式为：  ( )ih(n) ( ) g n f i n( 1)/ 2 ( ) 2 1 i n n i n  = + =    特殊形式 ( ) 1 1 +    =  k i n k i n n( 1)(2 1)/ 6 ( ) 3 1 2 i n n n i n  = + + =   

第二章分治法(续) 2重要实例 二分检索算法及其算法分析:2.2节 基于 PARTITION的选择算法:2.6节 3分类算法及其应用:24、2.5节 般了解: 4找最大和最小元素:23节 5.最坏情况时间是(n)的选择算法:23节后半部分

第二章 分治法（续） 2.重要实例 • 二分检索算法及其算法分析：2.2节 • 基于PARTITION的选择算法：2.6节 3.分类算法及其应用：2.4、2.5节 一般了解： 4.找最大和最小元素：2.3节 5.最坏情况时间是O(n)的选择算法：2.3节后半部分

第三章贪心方法 掌握: 1.基本知识(3.1节) 基本概念:约束条件、目标函数、可行解、 最优解 贪心方法的适用对象:求输入的一个可行的 子集 贪心方法的一般策略:度量标准 贪心解是问题最优解证明的基本思想

第三章 贪心方法 掌握： 1.基本知识（3.1节） • 基本概念：约束条件、目标函数、可行解、 最优解 • 贪心方法的适用对象：求输入的一个可行的 子集 • 贪心方法的一般策略：度量标准 • 贪心解是问题最优解证明的基本思想

第三章贪心方法(续) 2重要实例 背包问题:最优度量标准的选择、最优解的证明 (32节) 带有限期的作业排序问题:度量标准和处理策略 作业集合可行性的判定(3.3节) 单源最短路径:给出一个图,能够写出算法的执行 轨迹(36节) 例题和实验

第三章 贪心方法（续） 2.重要实例 • 背包问题：最优度量标准的选择、最优解的证明 （3.2节） • 带有限期的作业排序问题：度量标准和处理策略、 • 作业集合可行性的判定（3.3节） • 单源最短路径：给出一个图，能够写出算法的执行 轨迹（3.6节） 例题和实验

30 15 迭代选取的 DIST 结点 (1)(2)(3)(4)(5)(6) 置初值 020115++1+∞ 1,3 019↓15 25 21,32 0191529↓25 5 1,3,2,5 01915292528↓ 61,325601915292528

4 5 2 6 3 1 10 10 15 3 10 4 15 20 30 迭代 选取的 结点 S DIST (1) (2) (3) (4) (5) (6) 置初值 1 2 3 4 － 3 2 5 6 1 1,3 1,3,2 1,3,2,5 1,3,2,5,6 0 20 15 +∞ +∞ +∞ 0 19 15 +∞ 25 +∞ 0 19 15 29 25 +∞ 0 19 15 29 25 28 0 19 15 29 25 28

第三章贪心方法(续) 般了解: 3最优归并模式(34节) 4最小生成树算法:(3.5节) ·Prm算法(保持连通) Kruskal算法(不保持连通) 要求:给出图例,能够可以画出相应的最小 成本生成树

第三章 贪心方法（续） 一般了解： 3.最优归并模式（3.4节） 4.最小生成树算法： （3.5节） • Prim 算法（保持连通） • Kruskal算法（不保持连通） • 要求：给出图例，能够可以画出相应的最小 成本生成树

第四章动态规划 掌握: 1.基本知识(4.1节) 1)基本概念 多阶段决策过程 最优性原理 2)动态规划求解的一般策略: 证明最优性原理成立 ·列出递推关系式:向前处理法、向后处理法

第四章 动态规划 掌握： 1.基本知识（4.1节） 1）基本概念 • 多阶段决策过程 • 最优性原理 2）动态规划求解的一般策略： • 证明最优性原理成立 • 列出递推关系式：向前处理法、向后处理法

第四章动态规划(续) 2重要实例 多段图问题:段的定义、 (42节)基于多段图的多阶段决策过程、 导出的递推关系式及算法 最优二分检索树:最优二分检索树的定义 (44节)最优二分检索树的多阶段决策过程 递推关系式、 基于递推关系式的W,C,R的计算 习题 0/1背包问题:0/1背包问题的定义、向后递推策略 (45节)序偶S的表示方法及其计算过程 习题

第四章 动态规划（续） 2.重要实例 • 多段图问题：段的定义、 （4.2节） 基于多段图的多阶段决策过程、 导出的递推关系式及算法 • 最优二分检索树：最优二分检索树的定义、 (4.4节) 最优二分检索树的多阶段决策过程、 递推关系式、 基于递推关系式的W,C,R的计算 习题 • 0/1背包问题：0/1背包问题的定义、向后递推策略、 (4.5节) 序偶Si的表示方法及其计算过程 习题