《算法设计与分析-15-复习及答疑-v2详解优秀PPT.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析-15-复习及答疑-v2详解优秀PPT.ppt（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法设计与分析1考试及答疑支配n考试时间：n 7月2日（周四）15:30-17:30 n答疑支配n地点：教三楼918n7月2日：08:00点12:00点n留意考场纪律n 禁止：n 1.夹带纸制品；n 2.运用手机、PDA等2复习要求n计算题计算题 5道大题算法设计与分析3第1章n算法困难性的概念n时间、空间困难性n5种渐进困难性定义n O,o,的概念n!证明n f(n)=?(g(n)n？:5种渐近困难性n留意：O、与o、在定义上的区分：n存在正常数c和n0，使得对全部n n0有n对于任何正常数c0，存在正数n0 0nf(n)=O(g(n)a b;渐近上界渐近上界nf(n)=(g(n)a b;渐
2、近下界渐近下界 nf(n)=(g(n)a=b;紧渐近界紧渐近界nf(n)=o(g(n)a b.非紧下界非紧下界 算法设计与分析4第1章n 算法时间困难性分析方法n!给定算法步骤，分析各步执行时间，分析算法时间困难性算法设计与分析5第2章n 递归法的基本原理/步骤n分治法基本原理/步骤、适用条件n递归函数(了解)n用特征方程解递归方程的通解 1）!线性齐次递归方程线性齐次递归方程 2）线性非齐次递归方程（不做要求）算法设计与分析6第 2 章 原理、步骤/代码/伪代码、时间困难性,计算例子快速排序合并排序线性时间选择平面最近点对 算法设计与分析7第 3章 动态规划n 基本原理、要素（了解）n最优子
3、结构性质n应用范例n 原理、递推方程、步骤/代码/伪代码、时间困难性,计算例子n最长公共子序列n最大子段和n凸多边形最优三角剖分n背包问题算法设计与分析8第 4章 贪心算法n 贪心算法基础（了解）n 1）基本要素n 最优子结构性质、贪心选择性质n 2）贪心算法与动态规划算法的差异n应用范例:原理、步骤/代码/伪代码、时间困难性,计算例子n（1）活动支配问题n（2）哈夫曼编码n（3）单源最短路径n（4）最小生成树算法设计与分析9第 5 章 回溯法n原理（了解）n 形式化表示，完全/部分/可行/最优/不行行解，搜寻空间；n 深度优先搜寻策略；n 子集树、排列树问题；n算法框架（了解）n 递归回溯框
4、架n 迭代回溯框架；算法设计与分析10第 5 章 回溯法原理、步骤/代码/伪代码、时间困难性,计算例子装载问题（背包问题）n皇后问题图的m着色问题旅行商问题算法设计与分析11第 6 章 分支限界法n原理与算法框架（了解）n 解空间；n 界限函数，剪枝与搜寻过程；n 应用范例n原理、上下界限函数设计、步骤/代码/伪代码、时间困难性n、解空间树,计算例子！n（1）0-1背包问题12问题完全解界限40,100w=0,v=0ub=100,S=?,?,?,?w=4,v=40ub=40+(10-4)*6,S=1,?,?,?w=0,v=0ub=0+10*6,S=0,?,?,?11123w=4+7=11,S=1,1,?,?w=4,v=40ub=40+0+(10-4)*5,S=1,0,?,?45无效死结点(wC)w=4+5=9,v=65 ub=65+(10-4-5)*4,S=1,0,1,?w=4,v=40ub=40+(10-4)*4,S=1,0,0,?67无效死结点(wC)w=9,v=65 ub=65,S=1,0,1,09w=12,S=1,0,1,18剪枝条件:ub 40物品2单位价值物品3单位价值物品4单位价值物品4单位价值