资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,算法设计与分析,*,算法设计与分析,1,考试及答疑安排,考试时间：,6,月,19,日（周四）,15:30-17:30,答疑安排,地点：教三楼918,6,月,18,日,： 15:00,点,18:00,点,注意考场纪律,禁止：,1.,夹带纸制品；,2.,使用手机、,PDA,等,算法设计与分析,2,复习要求,计算题,每章一道大题,算法设计与分析,3,第1章,算法复杂性的概念,时间、空间复杂性,5,种,渐进复杂性定义,O, o,，,的概念,!,证明,f,(n)=?(,g,(n),？,: 5,种渐近复杂性,算法时间复杂性分析方法,!,给定算法步骤，分析各步执行时间，分析算法复杂性,f,(,n,)=,O,(,g,(,n,),a, b;,渐近上界,f,(,n,)=,(,g,(,n,),a, b;,渐近下界,f,(,n,)=,(,g,(,n,),a,= b;,紧渐近界,f,(,n,)=,o,(,g,(,n,),a, b.,非紧下界,算法设计与分析,4,第,2,章,递归法的基本原理,/,步骤,分治法,基本原理,/,步骤、,适用条件,递归函数,(,了解,),用特征方程解递归方程的通解,1,）,!,线性齐次递归方程,2,）线性非齐次递归方程（不做要求）,算法设计与分析,5,第,2,章,原理、步骤、代码, fuzaxing,二分搜索,大整数乘,合并排序,快速排序,算法设计与分析,6,第,3,章 动态规划,基本原理、要素（了解）,最优子结构性质,应用范例,递推方程、算法步骤、代码,复杂性,1),最长公共子序列,2),最大子段和,3),矩阵连乘,4)0/1,背包,算法设计与分析,7,第,4,章 贪心算法,贪心算法基础（了解）,1,）基本要素,最优子结构性质、贪心选择性质,2,）步骤,3,）贪心算法与动态规划算法的差异,应用范例,:,贪心策略设计、算法步骤、代码,复杂性,（,1,）活动安排问题,（,2,）最优装载问题,（,3,）哈夫曼编码,（,4,）最小生成树,算法设计与分析,8,第,5,章 回溯法,原理（了解）,形式化表示，完全,/,部分,/,可行,/,最优,/,不可行解，搜索空间；,深度优先搜索策略；,子集树、排列树问题；,算法框架（了解）,递归回溯框架,迭代回溯框架；,算法设计与分析,9,第,5,章 回溯法,原理、算法步骤、代码,复杂性,（,1,）装载问题；,（,2,）,n,后问题；,（,3,）,图的,m,着色问题,（,4,）,旅行商问题,算法设计与分析,10,！第,6,章 分支限界法,原理与算法框架,解空间；,界限函数，剪枝与搜索过程；,应用范例,上下界限函数设计、算法步骤,/,代码、解空间树,复杂性,！,（,1,）单源最短路径问题,（,2,）旅行商问题,（,3,）,0-1,背包问题,start,lb=14,1,2,lb=14,1,3,lb=14,1,4,lb=16,1,5,lb=19,2,3,lb=16,2,4,lb=16,3,2,lb=16,2,5,lb=19,3,4,lb=15,3,5,lb=14,4,2,lb=18,4,5,lb=15,5,2,lb=19,5,4,lb=14,5,2,lb=20,4,2,lb=16,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,TSP,问题完全解界限,14,16,1.,树结点编号对应了结点搜索,/,生成顺序,2.,表示被丢弃的死结点,
展开阅读全文