算法分析与设计复习优秀PPT.ppt

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