计算机算法分析与设计复习.doc

计算机算法分析与设计复习本文由1005285869贡献 ppt文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。 复习 本课程的目标 学习算法设计可以在分析解决问题的过程中， 学习算法设计可以在分析解决问题的过程中，培养学生的 逻辑思维和缜密概括的能力， 逻辑思维和缜密概括的能力，培养学生的软件开发设计 能力. 能力 通过对算法设计策略的系统学习与研究， 通过对算法设计策略的系统学习与研究，理解和掌握算法 设计的主要方法，培养对算法分析的能力， 设计的主要方法，培养对算法分析的能力，为独立地设 计算法和对给定算法进行复杂性分析奠定坚实的理论基 础。 题型 1、填空题（5*1） 、填空题（ ） 2、选择题（5*1） 、选择题（ ） 1、阅读程序题（30分）（习题或例题的变化，每题 习题或例题的变化， 、阅读程序题（ 分）（习题或例题的变化 每题10 算法基本工具及技巧、分治法、动态规划法） 分 算法基本工具及技巧、分治法、动态规划法） 2、算法理解题（40分 分治 动态规划 贪心 回溯 分支限 、算法理解题（ 分 ）（例题 每题8分 例题， 界法 ）（例题，每题8分） 3、算法设计题（20分 动态规划 回溯 ）（习题或例题的 ）（习题或例题的 、算法设计题（ 分 变化） 变化） 第 1章 1、了解用计算机求解问题的步骤，了解算法的定义、基本特征。 、了解用计算机求解问题的步骤，了解算法的定义、基本特征。 2、掌握评价算法的标准：正确性、可维护性、可读性、时间复杂 、掌握评价算法的标准：正确性、可维护性、可读性、 空间复杂度。 度、空间复杂度。 3、掌握算法时间复杂度的几种数量级的形式和它们的排列顺序。 、掌握算法时间复杂度的几种数量级的形式和它们的排列顺序。 算法基本工具和优化技巧 掌握循环与递归的程序设计 例题：数字的不同、 例题：数字的不同、信息数字化 习题：实验作业（ 个 习题：实验作业（3个） 第2章 递归与分治策略 基本思想： 基本思想：将一个规模较大的问题分解为与原问题相同的若干个规 模较小且互相独立的子问题，以便各个击破，分而治之。 模较小且互相独立的子问题，以便各个击破，分而治之。 分治法的基本步骤在每一层递归上都有三个步骤： 分治法的基本步骤在每一层递归上都有三个步骤： 分解、解决、 分解、解决、合并 适合用分治法策略的问题 ： 1）分解的子问题与原问题具有相同或相似的结构 ） 2）分解的子问题是可以独立求解的子问题。 ）分解的子问题是可以独立求解的子问题。 例题：残缺棋盘、全排列、合并排序、 例题：残缺棋盘、全排列、合并排序、快速排序 习题： 算法实现题2-14 整数因子分解问题 习题： 算法实现题 第3章 动态规划 动态规划算法与分治法类似， 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成 若干个子问题，但是经分解得到的子问题往往不是互相独立的。 若干个子问题，但是经分解得到的子问题往往不是互相独立的。 用一个表来记录所有已解决的子问题的答案， 用一个表来记录所有已解决的子问题的答案，不管该子问题以后 是否被用到，只要它被计算过，就将其结果填入表中， 是否被用到，只要它被计算过，就将其结果填入表中，这就是动 态规划法的基本思想。 态规划法的基本思想。 动态规划基本步骤： 动态规划基本步骤： 找出最优解的性质，并刻划其结构特征。 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 递归地定义最优值。 以自底向上的方式计算出最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 根据计算最优值时得到的信息，构造最优解。 例题：矩阵连乘积、最长公共子序列、资源分配问题 例题：矩阵连乘积、最长公共子序列、 习题：算法分析题3 习题：算法分析题3-1 最长单调递增子序列 算法实现题3 算法实现题3-6 石子合并 数列极差问题 ? ? ? 第4章 贪心算法 从问题的某一个初始解出发逐步逼近给定的目标， 从问题的某一个初始解出发逐步逼近给定的目标，每一步都作一个 不可回溯的决策,尽可能地求得最好的解 尽可能地求得最好的解。 不可回溯的决策 尽可能地求得最好的解 。 当达到某算法中的某 一步不需要再继续前进时，算法停止。 一步不需要再继续前进时，算法停止。 贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择 贪心策略的选择。 贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。 例题：活动安排、最优装载、单源点最短路径、最小生成树 例题：活动安排、最优装载、单源点最短路径、 习题： 习题：算法实现题 4-1 会场安排问题 4-13 数列极差问题 第5章 回溯法 1、理解回溯法的深度优先搜索策略。 、理解回溯法的深度优先搜索策略。 掌握用回溯法解题的算法框架 （1）子集树算法框架 ） （2）排列树算法框架 ） 通过应用范例学习回溯法的设计策略。 通过应用范例学习回溯法的设计策略。 回溯法 回溯法的基本思想： 回溯法的基本思想： (1)针对所给问题，定义问题的解空间； 针对所给问题， 针对所给问题 定义问题的解空间； (2)确定易于搜索的解空间结构； 确定易于搜索的解空间结构； 确定易于搜索的解空间结构 (3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免 以深度优先方式搜索解空间， 以深度优先方式搜索解空间 无效搜索。 无效搜索。 例题： 背包问题、 例题：0-1背包问题、批处理作业调度、装载问题、旅行售货商问 背包问题 批处理作业调度、装载问题、 题。 习题：算法实现题5-3、5-4 、5-13 习题：算法实现题 、 第6章 分支限界法 思路：分支搜索法也是一种在问题解空间上进行尝试搜索算法。 思路：分支搜索法也是一种在问题解空间上进行尝试搜索算法。所 分支”是采用广度优先的策略，依次生成E-结点所有分支 结点所有分支， 谓“分支”是采用广度优先的策略，依次生成 结点所有分支， 也就是所有的儿子结点。 也就是所有的儿子结点。一个活结点最多有一次机会成为扩展结 点 分支限界法与回溯法比较： 分支限界法与回溯法比较： （1）求解目标：回溯法的求解目标是找出解空间树中满足约束条 ）求解目标： 件的所有解， 件的所有解，而分支限界法的求解目标则是找出满足约束条件的 一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 一个