下载文档原格式
算法设计与分析课程报告第一章算法问题求解基础1、算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。
2、算法的特性①有穷性：一个算法必须保证执行有限步之后结束；②确切性：算法的每一步骤必须有确切的定义；③输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；④输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。
没有输出的算法是毫无意义的；⑤可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成3、算法与程序的关系：区别：程序可以不一定满足可终止性。
但算法必须在有限时间内结束；程序可以没有输出,而算法则必须有输出；算法是面向问题求解的过程描述，程序则是算法的实现。
联系：程序是算法用某种程序设计语言的具体实现；程序可以不满足算法的有限性性质。
4、算法描述方式：自然语言，流程图，伪代码，高级语言。
第二章算法分析基础1、算法复杂性分析：算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。
算法复杂性度量：期望反映算法本身性能，与环境无关。
理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响）。
一般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单位的开销作为标准。
算法复杂性C依赖于问题规模N、算法输入I和算法本身A。
即C=F(N, I, A)。
第五章分治法1、递归算法：直接或间接地调用自身的算法。
用函数自身给出定义的函数称为递归函数。
注：边界条件与递归方程是递归函数的二个要素。
实例：①阶乘函数；②Fibonacci数列；③Ackerman函数；④排列问题；⑤整数划分问题；⑥Hanoi塔问题优缺点：①优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。
②缺点：递归算法的运行效率低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
《算法分析与设计》课程复习资料一、名词解释：1.算法2.程序3.递归函数4.子问题的重叠性质5.队列式分支限界法6.多机调度问题7.最小生成树 二、简答题：1.备忘录方法和动态规划算法相比有何异同？简述之。
2.简述回溯法解题的主要步骤。
3.简述动态规划算法求解的基本要素。
4.简述回溯法的基本思想。
5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。
6.简要分析分支限界法与回溯法的异同。
7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？ 8.贪心算法求解的问题主要具有哪些性质？简述之。
9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。
10.简述分析贪心算法与动态规划算法的异同。
三、算法编写及算法应用分析题：1.已知有3个物品：(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。
2.按要求完成以下关于排序和查找的问题。
①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。
②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。
③给出上述算法的递归算法。
④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。
3.已知1()*()i i k k ij r r A a +=，k =1，2，3，4，5，6，r 1=5，r 2=10，r 3=3，r 4=12，r 5=5，r 6=50，r 7=6，求矩阵链积A 1×A 2×A 3×A 4×A 5×A 6的最佳求积顺序（要求给出计算步骤）。
4.根据分枝限界算法基本过程,求解0-1背包问题。
已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。
内容提要 NP完全性理论介绍清华大学 宋斌恒 • • • • • 计算模型与计算复杂度关系 问题分类：【P】与【NP】类 NP－难【hard】问题，NP完全集 第一个NPC问题和NPC问题集 如何证明一个问题是NPC问题清华大学 宋斌恒1清华大学 宋斌恒2引言• 脑力劳动机械化【吴文俊先生】 • 图灵机的停机问题：是否存在一个图灵机，他 可以回答其它图灵机是否停机【既算法是有界 的】 • 原则上是否存在一般数学问题的解题步骤的判 决问题【希尔波特第十问题变种】 • 图灵公理：凡是可计算的函数都可以用一台图 灵机来计算清华大学 宋斌恒 3NPC问题• P－NP－NPC问题定义及其猜想：NPC是 一类不可以在多项式时间内计算的问 题。
• 如果在量子计算模型中上述问题又如 何？清华大学 宋斌恒4下面介绍计算机械化的进程明代数学家程大位著《算法统 宗》中关于珠算的插图清华大学 宋斌恒5清华大学 宋斌恒61机械式手动计算机机械计算机• 法国数学家、哲学家帕斯卡在1642年发 明了一种机械计算机，并与1649年取得 专利。
帕斯卡的计算机采用一种齿轮系 统，其中一小轮转十个数字，下一个小 轮便转动一个数字，通过齿轮系的联 动，可以进行加法和减法的运算.清华大学 宋斌恒7清华大学 宋斌恒8图灵• 大半个世纪以来，数学家、计算机 科学家提出了各种各样的计算模型 都被证明是同图灵机器等价的。
这 一理论已被当成公理，它不仅是计 算机科学的基础，也是数学的基础 之一。
为纪念英国数学家Turing (1912-1954) 而设立的图灵奖成为计 算机界的诺贝尔奖.图灵机模型清华大学 宋斌恒9清华大学 宋斌恒10图灵机模型• 图灵机模型用一个无限长的带子作为无限存储 , 它还有一个读写头 ,这个读写头能在带子上读 , 写和移动 : 开始时 ,带子上只有输入串 ,其它地 方都是空的 .当它需要保存信息时 ,读写头就把 信息写在带子上 .为了读某个输入或写下的信 息 ,带子可能将读写头往回移动到这个信息所 在的地方 .这样读 ,写和移动 ,机器不停的计算 , 直到产生输出为止 .机器实现设置了两种状态 : 接受 或 拒绝清华大学 宋斌恒 11图灵机定义• 一个图灵机是一个7元组(Q,∑,Γ,δ,q0,q1,q2), 其中Q,∑,Γ都是有穷集合,并且 • 1) Q 是状态集. • 2) ∑是输入字母表,不包括特殊空白符号︺. • 3) Γ 是带字母表,其中: ︺∈Γ,∑是Γ的子 集. • 4) δ: Q×Γ→Q×Γ×{L,R}是转移函数. • 5) q0∈Q是起始状态. • 6) q1∈Q是接受状态. • 7) q2∈Q是拒绝状态,且 q2≠q1清华大学 宋斌恒 122多带图灵机,• 和普通图 灵机相似, 只是有多 个带子,每 个带子都 有自己的 读写头,用 于读和写. 如图清华大学 宋斌恒 13非确定性的图灵机• 在计算的任何时刻,机器可以在多种可能 性中选择一种继续进行【永远选择正确 的，可以理解为全部分支都计算完后选 出正确的】.它的计算是一课树,不同的分 枝对应着机器不同的可能性.如果某个计 算分枝导致接受状态,则接受该输入.与多 带图灵机相同的是,它的计算能力与普通 图灵机也是一样的.当然他的计算速度就 不一样了。
P问题、NP问题、NP完全问题和NP难问题在讲P类问题之前先介绍两个个概念：多项式，时间复杂度。
(知道这两概念的可以⾃动跳过这部分)1、多项式：axn-bxn-1+c恩....就是长这个样⼦的，叫x最⾼次为n的多项式....咳咳，别嫌我啰嗦。
有些⼈说不定还真忘了啥是多项式了。
例如第⼀次看到的鄙⼈→_→2、时间复杂度我们知道在计算机算法求解问题当中，经常⽤时间复杂度和空间复杂度来表⽰⼀个算法的运⾏效率。
空间复杂度表⽰⼀个算法在计算过程当中要占⽤的内存空间⼤⼩，这⾥暂不讨论。
时间复杂度则表⽰这个算法运⾏得到想要的解所需的计算⼯作量，他探讨的是当输⼊值接近⽆穷时，算法所需⼯作量的变化快慢程度。
举个例⼦：冒泡排序。
在计算机当中，排序问题是最基础的，将输⼊按照⼤⼩或其他规则排好序，有利于后期运⽤数据进⾏其他运算。
冒泡排序就是其中的⼀种排序算法。
假设⼿上现在有n个⽆序的数，利⽤冒泡排序对其进⾏排序，①⾸先⽐较第1个数和第2个数，如果后者>前者，就对调他们的位置，否则不变②接着⽐较第2个数和第3个数，如果后者>前者，就对调他们的位置，否则不变③⼀直向下⽐较直到第n-1和第n个数⽐较完，第⼀轮结束。
（这时候最⼤的数移动到了第n个数的位置）④重复前三步，但是只⽐较到第n-1个数（将第⼆⼤的数移动到第n-1个数位置）⑤持续每次对越来越少的元素重复上⾯的步骤，直到没有任何⼀对数字需要⽐较。
举个实例：5,4,3,2,1，对其进⾏排序，先是⽐较5跟4变成4,5,3,2,1，第⼀轮结束后变成43215，可以计算，当对其排序完正好要经过4+3+2+1=10次⽐较，当然这是最复杂的情况，即完全反序。
可以知道对于n个数，⾄多要经过1+2+...+n-1即(n^2-n)/2次⽐较才能排好序。
这个式⼦⾥n的最⾼次阶是2，可知道当n→∞时，⼀次性对其⽐较次数影响很⼩，所以我们把这个算法的时间复杂度⽐作：o(n^2)。
取其最⾼次，可以看出，这是⼀个时间复杂度为多项式的表⽰⽅式。
一、名词解释1.算法评价的主要标准算法的时间复杂度:针对问题指定基本运算，计数算法所做的基本运算次数2.时间和空间复杂度算法复杂度分为时间复杂度和空间复杂度。
其作用：时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。
（算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度。
）3.P和NP类问题所有多项式时间可解的判定问题组成的问题类称作P类.由所有多项式时间可验证的判定问题组成的问题类称作NP类4.数学建模当需要从定量的角度分析和研究一个实际问题时，人们就要在深入调查研究、了解对象信息、作出简化假设、分析内在规律等工作的基础上，用数学的符号和语言，把它表述为数学式子，也就是数学模型，然后用通过计算得到的模型结果来解释实际问题，并接受实际的检验。
这个建立数学模型的全过程就称为数学建模。
5.分而治之算法分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治法（divide-and-conquer）的基本思想：分治法的求解过程由以下三个阶段组成：（1）划分：把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。
（2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。
（3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。
6.贪婪算法贪心算法又叫登山法，它的根本思想是逐步到达山顶，即逐步获得最优解，以逐步的局部最优，达到最终的全局最优。
7.动态规划设计动态规划算法的步骤(1)找出最优解的性质，并刻划其结构特征。
(2)递归地定义最优值。
(3)以自底向上的方式计算出最优值。
(4)根据计算最优值时得到的信息，构造最优解8.蛮力算法利用枚举所有的情况，或者其它大量运算又不用技巧的方式，来求解问题的方法。
NP 类问题不难看出，上面定义的P 类语言只能用来描述那些存在有效算法（多项式时间）的问题。
然而，在实际中存在许多别的重要问题，对于它们，至今尚未找到有效的求解算法。
其中有一大类这样的问题，虽然不知道求解它们的有效算法，但是，一旦通过某种办法给出了其答案的一个猜测或估计，就能设计出一个多项式时间算法来验证其真实性(称为多项式时间可验证性)。
这类问题的分析和描述需要借助另一类图灵机作为计算模型。
非确定性单带图灵机(non-deterministic one-tape Turing machine)，简记为NDTM ，是一种假想的机器。
通常有两种方式描述它：多值模型和猜想模块模型。
多值模型认为它和确定性图灵机的共同之处是也包括：(a).带中字符集Γ，使得Γ⊂∑，且 ∑-Γ∈b ；(b).有限状态集},,{0q q q Q N Y ⊇；不同之处在于(c).多值转移函数},{2}),{\(:r l Q N Y q q Q ⨯Γ⨯→Γ⨯δ,},{),(r l Q S s q ⨯Γ⨯⊆ ，确定性图灵机在任一状态只能做一种运算，而非确定性图灵机在同一时刻可以独立、并行地完成(无限)多种运算（表现在转移函数的多值性），这显然是不现实的。
猜想模块模型是一种更形象、直观的描述方法。
可将NDTM 描述成：除多了一个猜想模块（guessing module ）外，NDTM 与DTM 有着完全相同的结构，而这个猜想模块带有自己的仅可对带写操作的猜想头，它提供写下猜想的方法，仅此而已。
非确定性图灵机（NDTM ）示意图基于这一模型，一个NDTM 程序可以类同于一个DTM 程序的方式来进行定义，并用相同的记号（包括带中字符集Γ，输入字符表∑，空白符号b ，状态集Q ，初始状态0q ，两个停机状态Y q 和N q ，以及状态转移函数},{}),{\(:r l Q q q Q N Y ⨯Γ⨯→Γ⨯δ猜想模块 有限状态控制器 … -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 … 猜想头 读写头但对于一个输入*∑∈x ，NDTM 程序的计算却与DTM 程序的不同，它把计算分为两个阶段：猜想阶段和检验阶段。
