算法设计与分析课程报告

《算法设计与分析课程报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、算法设计与分析课程报告第一章算法问题求解基础1、算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。2、算法的特性①有穷性：一个算法必须保证执行有限步之后结朿；②确切性：算法的每一步骤必须有确切的定义；③输入：一个算法有0个或多个输入，以刻画运算对象的初始怡况，所谓0个输入是指算法本身定除了初始条件；④输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；⑤可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成3、算法与程序的关系：区别：程序可以不一定满足可终止性。但算法必须在有限时间内结束；程

2、序可以没有输出，而算法则必须有输出；算法是面向闷题求解的过程描述，程序则是算法的实现。联系：程序是算法用某种程序设计语言的具体实现；程序可以不满足算法的有限性性质。4、算法描述方式：自然语言，流程图，伪代码，高级语言。第二章算法分析基础1、算法复杂性分析：算法a杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。算法复杂性度量：期望反映算法本身性能，与环境无关。理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响）。一般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单位的开销作为标准。算法杂性C依赖于问题规模N、算法输入I和算

3、法本身A。即C=F（N,IA）o第五章分治法1、递归算法：直接或间接地调用自身的算法。用函数自身给山定义的函数称为递归函数。注：边界条件与递归方程是递归函数的二个要素。实例：①阶乘函数；②Fibonacci数列；③Ackerman函数；④排列问题；⑤整数划分闷题：⑥Hanoi塔问题优缺点：①优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性,因此它为设计算法、调试程序带來很大方便。②缺点：递归算法的运行效率低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。2、分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破

4、，分而治之。（将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原來W题的解）分治法所能解决的问题一般具有以下几个特征：①该问题的规模缩小到一定的程度就可以容易地解决；②该问题可以分为若干个规模更小的相同问题，即该问题具有最有子结构性质；③利用该问题分解山的子问题的解可以合并为该问题的解：④该fu）题所分解出的各个子闷题是相互独立的，即子fu）题之间不包含公共的子问题。第六章贪心法1、贪心算法的思想：采用逐步构造最优解的方法。每个阶段，都作出一个看上去最有的决定。决策一旦做出，就不可再更改。其特点如下：①不能保证最后求得的解是最佳的，即：多半是近似解（

5、少数问题除外）；②策略容易发现（少数问题除外）；③策略多样，结果也多样；④算法实现过程中，通常用到辅助算法：排序：（1）活动问题安排描述：活动安排问题是要在所给的活动集合中选出最大的相容活动子集合，是付以用贪心算法有效求解的很好例子。该问题要求商效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动多的活动能兼容地使用公共资源。贪心算法的证明多使用反证法。贪心算法的两个重要性质：①贪心选择性：所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到；B

6、j:在当前状态下做出局部最优，然后解这个选择时候产生的子问题。从全局看来,

7、运用贪心策略解决的问题在程序的运行中无回溯过程；②最优子结构性质：当一个问题的最优解包含着其它的子问题的最优解时，称此问题具有最优子结构性质。该性质是可川动态规划或贪心算法求解的一个关键特性。贪心算法和动态算法的差异：两者虽然都要求具有最优子结构性质，但是能用动态规划算法求解的问题不一定能用贪心算法来求解。0-1背包问题描述：给定n种物品和一个背包。物品i的重呈是Wi,其价值是Vi,背包的容量是C。问:应如何选择装入背包中的物品的总价值最大？注：在选择装入背包的物品时，对每种物品i中只有两种选择，即装入背包或不装入背包。不能将物品i装入部分的物品i。背包问题描述：与0-1

8、背包问题相似，所不同的是在选择物品装入背包时，可以选择物品的一部分，而不一定要全部装入背包。分析：两个问题相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能。（2）背包问题的贪心算法描述：首先计算每种物品单位重量的价值Vi/Wi,然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量米超过C，则选择单位重量价值次高的物品并尽可能多的装入背包。依此策略一直到背包装满为止。第七章动态规划法1、动态规划算法总体思想：与分治法类似，其基本思想也是将待求解的问题分解成若干