算法分析与设计复习.ppt

考试范围 第一章至第六章考试题型 化简题 简述题 算法题分数分布 填空题每空2分 共30分判断题每个1分 共10分算法设计题2题 共30分程序设计题2题 共30分要求写程序时一定要先写出思路做为注释 并且在程序的关键地方也要有注释考试方式 闭卷 第一章算法概述 第二章递归与分治策略 第三章动态规划 第四章贪心算法 第五章回朔法 第六章分支限界法 算法分析与设计 第一章算法概述 理解算法的概念掌握算法的计算复杂性概念掌握算法渐近复杂性的数学表述 第一章算法概述 理解算法的概念算法是指解决问题的一种方法或一个过程 算法应满足的性质 有穷性 确定性 能行性 有0个或多个输入项 至少有一个输出项 第一章算法概述 掌握算法的计算复杂性概念算法的复杂性 算法执行所需的时间和空间的数量 与问题的规模 算法的输入数据及算法本身有关 最好情况 最坏情况 平均情况 第一章算法概述 掌握算法渐近复杂性的数学表述大O表示法 算法运行时间的上限 大 表示法 算法运行时间的下限 表示法 常见的多项式阶有 O 1 O logn O n O nlogn O n2 O n3 O 2n O n O nn 常见的指数阶有 第一章算法概述 1 渐近表达式2 下面程序段的时间复杂度是for i 0 i n i for j 0 j n j A i j 0 3 有如下递归过程 voidreverse intn printf d n 10 if n 10 0 reverse n 10 功能是什么 4 化简递归式子 第二章递归与分治策略 理解递归的概念掌握设计有效算法的分治策略通过范例学习分治策略设计技巧二分搜索技术找最大和最小元素合并排序快速排序练习 要求解问题具有的性质 最优子结构和子问题独立性质求解问题的步骤 将要求解的较大规模的问题分割成k个更小规模的子问题 对这k个子问题分别求解 如果子问题的规模仍然不够小 则再划分为k个子问题 如此递归的进行下去 直到问题规模足够小 很容易求出其解为止 将求出的小规模的问题的解合并为一个更大规模的问题的解 自底向上逐步求出原来问题的解 第二章递归与分治策略 练习伪造硬币问题求最大最小值问题有重复元素的排列问题半数集问题整数因子分解问题 第三章动态规划 理解动态规划算法的概念掌握动态规划算法的基本要素最优子结构性质重叠子问题性质掌握设计动态规划算法的步骤动态规划算法与分治策略和贪心算法的异同通过范例学习动态规划策略设计技巧及练习 第三章动态规划 动态规划算法与分治策略和贪心算法的异同动态规划算法与贪心算法比较的异同是 都是将问题的求解过程化为多步决策 区别是 贪心法每采用一次贪心策略便做出唯一决策 求解过程只产生一个决策序列 求解过程为自顶向下 不一定得到最优解 动态规划的求解过程产生多个决策序列 下一步的选择总是依赖上一步的结果 求解过程多为自底向上 总能得到最优解 动态规划算法与分治法类似 其基本思想也是将待求解问题分解成若干个子问题 但是经分解得到的子问题往往不是互相独立的 不同子问题的数目常常只有多项式量级 在用分治法求解时 有些子问题被重复计算了许多次 如果能够保存已解决的子问题的答案 而在需要时再找出已求得的答案 就可以避免大量重复计算 从而得到多项式时间算法 因此 相同点是都具有最优子结构的性质 要求解问题具有的性质 最优子结构和子问题重叠性求解问题的步骤 分析最优解的结构 给出计算局部最优解值的递归关系 递归的定义最优值 自底向上计算局部最优解的值 计算最优值 根据最优解的值构造最优解 第三章动态规划 通过范例学习动态规划策略设计技巧及练习最短路问题0 1背包问题矩阵乘法链最长单调递增子序列二维0 1背包问题最大k乘积问题 第四章贪心算法 理解贪心算法的概念掌握贪心算法的基本要素最优子结构性质贪心选择性质通过应用范例学习贪心设计策略练习 第四章贪心算法 通过应用范例学习贪心设计策略活动安排问题最优装载背包问题多机调度问题哈夫曼编码单源最短路径问题最小生成树问题 第四章贪心算法 练习找零钱问题汽车加油问题数列极差问题删数问题最优分解问题 第五章回朔法 理解回溯法的深度优先搜索策略掌握用回溯法解题的算法框架通过应用范例学习回溯法的设计策略练习 步骤 针对所给问题 定义问题的解空间确定解空间结构 以深度优先方式搜索解空间 约束条件和限界函数 第五章回朔法 通过应用范例学习回溯法的设计策略子集和问题装载问题批处理作业调度n后问题最大团问题图的m着色问题练习最小重量机器设计问题工作分配问题