算法分析与设计复习题及参考答案_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
算法分析与设计复习题及参考答案
上传于||暂无简介
阅读已结束，如果下载本文需要使用0下载券
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩16页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢算法设计与分析复习题目及答案_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
算法设计与分析复习题目及答案
上传于||暂无简介
阅读已结束，如果下载本文需要使用0下载券
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩28页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢&&国之画&&&& &&
版权所有 京ICP备号-2
迷上了代码！参考书目——《计算机算法设计与分析 王晓东》
本文仅供博主备忘，诸多谬误，愿谅解
在基于划分子问题的基础上，衍生出两种优秀的方法——a. 动态规划 &b. 备忘录算法&
a. 动态规划的基础是最优子结构———若一个大问题可以划分成多个小问题，则在这多种划分中，必有一种划分，可使得作为宏观问题，这种划分得到的效果最优；而在每个划分出的子问题中，每个子问题也必有一个最优划分（否则用更好的划分来代替原子问题的划分，将会影响到宏观结果） & &
动态规划的过程是利用子结构，进行自底而上的算法设计，应为采用自底而上，故上面的问题依赖于下面问题的求解，下面的一些结果也直接提供给上层问题使用（作为上层问题的素材)。避免了重复计算（实际上采用自底向上的多循环结构。利用多维数组存储结果，就可以避免重复问题，举个例子，就像设计一个高级算法，底层的算法诸如排序算法，一次编写，可以供多个算法，多次使用）
弊处所在，就是没有在处理的过程中实时的进行处理，达到理想效果，而是用多次循环计算，用另外一个数组存储暂时所得的结果（用于拼接最后结果）——实际上，这也是自底向上的算法的通病，无法像修剪枝条一样砍掉其它部分。
b.利用备忘录方法呢，就可以在递归处理问题的基础上，将需要后来多次计算的问题进行缓存，减少了重复子问题的计算。但是书中所记的备忘录方法没有真正的将自上而下的精髓体现出来，若是将自上而下的思想结合最优子结构的思想，则可以对问题进行修剪枝条，在宏观出即可去掉一大部分的不需计算的方面，比如一个问题的划分可以有两种，选择了最优的一种，就可以将另一种非最优情况下的所有计算均省去，然后再对第一次的划分再次进行划分，其结构是树由根向叶，不断的择取最优的树干，最终至叶子，非最优树干直接不计算。
最终效果图
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：345次
排名：千里之外算法分析与设计
& &教学大纲
5.1课程定位
　　《算法分析与优化》是软件开发人员必修专业课，软件的效率和稳定性取决于软件中所采用的算法；对于一般程序员和软件专业学生，学习算法设计与分析课程，可以开阔编程思路，编写出优质程序。
5.2课程总体目标
　通过对常用的、有代表性的算法的研究，让学生理解并掌握算法设计的基本技术。培养学生分析算法复杂度的初步能力，锻炼其逻辑思维能力和想象力，并使之了解算法理论的发展。鼓励学生运用算法知识解决各自学科的实际问题，培养学生的独立科研的能力和理论联系实践的能力。
5.3教学内容及学时分配
本课程共48学时。
第一章 算法引论&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&4学时
算法的概念及其应用
了解算法的基本概念，算法与程序的联系，软件开发过程中算法的作用。
表达算法的抽象机制
掌握数据结构、抽象数据类型、面向对象编程等相关概念。了解和掌握java语言的特点，java类的组成。
算法复杂性的分析
掌握算法复杂度的基本概念以及时间和空间复杂度的估算方法。
第二章 递归与分治策略 &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&6学时
递归的概念
掌握递归的概念。掌握几种典型的递归应用实例：阶乘、Fibonacci数列、Hanoi塔问题等。掌握递归式的概念。
分治法的思想
掌握分治法的基本思想，分治法和递归技术的联系，分治法的步骤，分治法的应用场合。
二分搜索技术
掌握查找的概念。掌握二分搜索法的基本思想，求解过程，能够分析其复杂度。
大整数相乘
了解大整数相乘的应用意义，以及分治法如何求解该问题。
Strassen矩阵相乘
了解矩阵连乘的应用意义，以及分治法如何求解该问题。
掌握归并排序的基本思想，求解过程，能够分析其复杂度。
掌握快速排序的基本思想，求解过程，能够分析其复杂度。
最接近点对问题
了解矩阵连乘的应用意义，以及分治法如何求解该问题。
第三章 动态规划算法&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&11学时
动态规划算法的基本思想
掌握动态规划算法的基本思想。了解它与分治法的区别。了解最优解的概念。掌握动态规划算法的求解步骤
矩阵连乘问题
通过矩阵连乘问题的实例说明动态规划算法的基本思想和求解步骤。掌握动态规划算法求解该问题的技巧。能够认知相应的递归式。熟悉动态规划求解最优值的过程。
动态规划算法的基本要素
掌握动态规划算法的基本要素，掌握最优子结构性质和重叠子问题性质的概念。明确动态规划算法的应用场合。掌握备忘录方法的思想。
最长公共子序列问题
了解该问题的数学意义，了解动态规划算法求解该问题的步骤。
凸多边形最优三角剖分
了解该问题的数学意义，了解动态规划算法求解该问题的步骤。
掌握该问题和矩阵链相乘问题，语法树三者之间的共性。掌握互相转化的技巧。
了解该问题的研究意义，了解动态规划算法求解该问题的步骤。
了解该问题的数学意义，了解动态规划算法求解该问题的步骤。
流水作业调度
了解该问题的数学意义，了解动态规划算法求解该问题的步骤。
0-1背包问题
掌握背包问题的数学描述。掌握动态规划算法求解该问题的步骤。
最优二叉搜索树
掌握背包问题的研究意义。掌握动态规划算法求解该问题的步骤
第四章 贪心算法
&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&6学时
贪心算法的基本思想
掌握贪心算法的基本思想。理解找硬币问题是贪心算法的典型实例。掌握贪心算法的特点及其与动态规划算法的区别。
活动安排问题
了解该问题的实际意义以及贪心算法求解该问题的步骤。能够根据活动序列的起始和终止时间，用贪心算法求出最大相容活动集合。
贪心算法的基本要素
掌握贪心算法的两个基本要素：贪心选择性质和最优子结构性质的意义。掌握贪心算法的求解步骤。掌握贪心算法和动态规划算法的差别。
哈夫曼编码
掌握定长码、变长码、前缀码的概念。掌握哈夫曼码和哈夫曼树的概念。掌握求解哈夫曼编码的步骤。
最优装载问题
掌握个问题的数学描述以及相应贪心算法。
单源最短路径
掌握什么是单源最短路径以及相应的贪心算法。能够求解简单的单源最短路径。
最小生成树
掌握什么是最小生成树问题以及相应的贪心算法。能够求解简单的最小生成树。
多机调度问题
掌握什么是多机调度问题以及相应的贪心算法。
贪心算法的理论基础
初步了解贪心算法的理论基础，初步了解拟阵的概念。
第五章 回溯法
&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&& &&6学时
回溯法的算法框架
了解解空间等概念。掌握回溯法的基本思想和不同类型方法。
装载问题，批处理作业调度等
了解回溯法应用与这些问题的技巧
0-1背包问题，旅行售货员问题等。
了解回溯法应用与这项问题的技巧
回溯法的效率分析
掌握回溯法效率分析的技巧
第六章 分支限界法 &&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&& &&6学时
分支限界法的基本思想
掌握分支限界法的基本思想
单源最短路径问题，装载问题
了解分支限界法应用于这些问题的技巧
0-1背包问题，旅行售货员问题等
掌握分支限界法应用于这些问题的技巧
第七章 概率算法 &&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&2学时
数值概率算法，舍伍德算法，拉斯维加斯算法，蒙特卡罗算法
初步了解概率算法的基本思想，随机数，数值概率算法，舍伍德算法，拉斯维加斯算法，蒙特卡罗算法。
第八章 NP完全性理论&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&3学时
计算模型、P类和NP类问题，NP完全性理论
了解NP完全性问题；掌握P类与NP类问题的划分；掌握利用近似算法解决问题的基本思想，能对其可靠性进行分析
典型的NP完全问题
了解合取范式（CNF）顶点覆盖问题，哈密顿回路问题。
第九章 算法优化策略
&&&&&&&&&&&&&&&&&&&&&&&&&&&& & &&&& &&&&& &&&&& &&&&& &&&&&&&&2学时
算法设计策略的比较与选择，动态规划加速原理，问题的算法特征，优化数据结构
初步掌握算法设计策略的比较与选择方法，动态规划加速原理，问题的算法特征，优化数据结构的方法。
课程总结和复习 &&&& &&&&& &&&&& &&&&& &&&&& &&&&& &
&&& & &&& &
&&& & &&& & &&&&&&2学时
课程内容串讲、模拟题讲解
掌握主要算法的基本思想、对重点问题培养能够进行分析设计的能力。
5.4教材及参考书
《算法设计与分析》（第2版），王晓东 编著，清华大学出版社，2008年。
主要参考书：
《算法导论》（第2版），Thomas H.Cormen，Charles E.Leiserson 等著，潘金贵 顾铁成 等译，机械工业出版社。}