北京邮电大学算法设计与分析期末复习及答疑_第1页
北京邮电大学算法设计与分析期末复习及答疑_第2页
北京邮电大学算法设计与分析期末复习及答疑_第3页
北京邮电大学算法设计与分析期末复习及答疑_第4页
北京邮电大学算法设计与分析期末复习及答疑_第5页
已阅读5页，还剩6页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、算法设计与分析1考试及答疑安排n考试时间： 6月19日（周四）15:30-17:30 n答疑安排n地点：教三楼918n6月18日： 15:00点18:00点n注意考场纪律 禁止：禁止： 1. 1. 夹带纸制品；夹带纸制品； 2. 2. 使用手机、使用手机、PDAPDA等等算法设计与分析2复习要求n计算题计算题 每章一道大题算法设计与分析3第1章n算法复杂性的概念n时间、空间复杂性n5种渐进复杂性定义 O, o, ， , 的概念的概念n! 证明证明 f(n)=?(g(n) ？: 5种渐近复杂性n算法时间复杂性分析方法n! 给定算法步骤，分析各步执行时间，分析算法复杂性给定算法步骤，分析各步执行时

2、间，分析算法复杂性nf(n)= O(g(n) a b; 渐近上界渐近上界nf(n)= (g(n) a b; 渐近下界渐近下界 nf(n)= (g(n) a = b; 紧渐近界紧渐近界nf(n)= o(g(n) a b. 非紧下界非紧下界 算法设计与分析4第2章n 递归法的基本原理/步骤n分治法基本原理/步骤、适用条件n递归函数(了解)n用特征方程解递归方程的通解 1）! 线性齐次递归方程线性齐次递归方程 2）线性非齐次递归方程（不做要求）算法设计与分析5第 2 章 原理、步骤、代码, fuzaxingn二分搜索n大整数乘n合并排序n快速排序 算法设计与分析6第 3章 动态规划n 基本原理、要素

3、（了解）最优子结构性质n应用范例 递推方程、算法步骤、代码,复杂性1)最长公共子序列2)最大子段和3)矩阵连乘4)0/1背包 算法设计与分析7第 4章 贪心算法n 贪心算法基础（了解） 1）基本要素 最优子结构性质、贪心选择性质 2）步骤 3）贪心算法与动态规划算法的差异n应用范例: 贪心策略设计、算法步骤、代码,复杂性（1）活动安排问题（2）最优装载问题（3）哈夫曼编码（4）最小生成树算法设计与分析8第 5 章 回溯法n原理（了解） 形式化表示，完全/部分/可行/最优/不可行解，搜索空间； 深度优先搜索策略； 子集树、排列树问题；n算法框架（了解） 递归回溯框架 迭代回溯框架；算法设计与分析

4、9第 5 章 回溯法原理、算法步骤、代码,复杂性n（1）装载问题；n（2） n后问题；n（3）图的图的m着色问题着色问题n（4）旅行商问题旅行商问题算法设计与分析10！第 6 章 分支限界法n原理与算法框架 解空间； 界限函数，剪枝与搜索过程；n 应用范例 上下界限函数设计、算法步骤/代码、解空间树,复杂性！（1）单源最短路径问题（2）旅行商问题（3）0-1背包问题startlb=1412lb=1413lb=1414lb=1615lb=1923lb=1624lb=1632lb=1625lb=1934lb=1535lb=1442lb=1845lb=1552lb=1954lb=1452lb=2042lb=1612345 678 9

人人文库> 全部分类> 教育资料 > 备课教案

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论