第一部分：程序设计思路、辨识结果分析和算法特点总结 (2)
一：RLS遗忘因子法 (2)
RLS遗忘因子法仿真思路和辨识结果 (2)
遗忘因子法的特点： (3)
二：RFF遗忘因子递推算法 (4)
仿真思路和辨识结果 (4)
遗忘因子递推算法的特点： (5)
三：RFM限定记忆法 (5)
仿真思路和辨识结果 (5)
RFM限定记忆法的特点： (7)
四：RCLS偏差补偿最小二乘法 (7)
仿真思路和辨识结果 (7)
RCLS偏差补偿最小二乘递推算法的特点： (9)
五：增广最小二乘法 (9)
仿真思路和辨识结果 (9)
RELS增广最小二乘递推算法的特点： (11)
六：RGLS广义最小二乘法 (12)
仿真思路和辨识结果 (12)
RGLS广义最小二乘法的特点： (14)
七：RIV辅助变量法 (14)
仿真思路和辨识结果 (14)
RIV辅助变量法的特点： (16)
八：Cor-ls相关最小二乘法（二步法） (17)
仿真思路和辨识结果 (17)
Cor-ls相关最小二乘法（二步法）特点： (18)
九：MLS多级最小二乘法 (19)
仿真思路和辨识结果 (19)
MLS多级最小二乘法的特点： (22)
十：yule_walker辨识算法 (23)
仿真思路和辨识结果 (23)
yule_walker辨识算法的特点： (24)
第二部分：matlab程序 (24)
一：RLS遗忘因子算法程序 (24)
二：RFF遗忘因子递推算法 (26)
三：RFM限定记忆法 (28)
四：RCLS偏差补偿最小二乘递推算法 (31)
五：RELS增广最小二乘的递推算法 (33)
六;RGLS 广义最小二乘的递推算法 (36)
七：Tally辅助变量最小二乘的递推算法 (39)
八：Cor-ls相关最小二乘法（二步法） (42)
九：MLS多级最小二乘法 (45)
十yule_walker辨识算法 (49)
第一部分：程序设计思路、辨识结果分析和算法特点总结
一：RLS遗忘因子法
RLS遗忘因子法仿真思路和辨识结果
仿真对象如下：
其中， v(k )为服从N(0,1)分布的白噪声。输入信号u(k)采用M 序列，幅度为 1。M 序列由 9 级移位寄存器产生，x(i)=x(i-4)⊕x(i-9)。
选择如下辨识模型：
加权阵取Λ=I。
衰减因子β = 0.98，数据长度 L = 402。
辨识结果与理论值比较，基本相同。辨识结果可信：
Estimate =
-1.4666
0.6503
0.9736
0.3035
遗忘因子法的特点：
对老数据加上遗忘因子，以降低老数据对辨识的影响，相对增加新数据对辨识的影响，不会出现“数据饱和”现象。如模型噪声是有色噪声，则?是有偏估计量。常用作其他辨识方式的起步，以获得其他方式的初始值。
二：RFF遗忘因子递推算法
仿真思路和辨识结果
辨识模型与遗忘因子法所用模型相同。
其中， 0 ≤μ≤1为遗忘因子，此处取0.98。数据长度L=402，初始条件：
参数a1 a2 b1 b2的估计值:
ans =
-1.4977
0.6863
1.1903
0.4769
待估参数变化过程如图所示：
遗忘因子递推算法的特点：
从上面两个例子可以看出对于相同的仿真对象，一次算法和递推算法结果基本一致，但递推算法可以实现在线实时辨识，而且可以减少计算量和存储量。
三：RFM限定记忆法
仿真思路和辨识结果
辨识模型与遗忘因子法所用模型相同。
辨识结果与理论值比较，基本相同。辨识结果可信：参数 a1 a2 b1 b2 的估计值为：
Theta_a =
-1.5128
0.7099
0.8393
0.4416
待估参数的过渡过程如下：
RFM限定记忆法的特点：
辨识所使用的数据长度保持不变，每增加一个新数据就抛掉一个老数据，使参数估计值始终只依赖于有限个新数据所提供的新消息，克服了遗忘因子法不管多老的数据都在起作用的缺点，因此该算法更能有效的克服数据饱和现象。
四：RCLS偏差补偿最小二乘法
仿真思路和辨识结果
辨识模型与遗忘因子法所用模型相同。
辨识结果与理论值比较，基本相同。辨识结果可信：参数a1 a2 b1 b2的估计值为：
ans =
-1.4916
0.7005
1.0365
0.4271
RCLS偏差补偿最小二乘递推算法的特点：
算法思想：：在最小二乘参数估计值的基础上，引进补偿项σW2C-1D ?0，则获得了参数的无偏估计。针对模型噪声来说，RCLS算法的适应能力比RLS更好。
五：增广最小二乘法
仿真思路和辨识结果
考虑如下仿真对象：
其中，为服从N(0,1)分布的白噪声。输入信号采用 M 序列，幅度为 1。M 序列由 9 级移位寄存器产生，x(i)=x(i-4)⊕x(i-9)。
选择如下的辨识模型：
观测数据长度取L =402 。加权阵取Λ=I。
辨识结果与理论值比较，基本相同，同时又能获得噪声模型的参数估计。辨识结果可信：
参数a1、a2、b1、b2、d1、d2估计结果：
ans =
-1.5000
0.7000
1.0001
0.5002
-0.9999
0.2000
RELS增广最小二乘递推算法的特点：
增广最小二乘的递推算法对应的噪声模型为滑动平均噪声，扩充了参数向量和数据向量H（k）的维数，把噪声模型的辨识同时考虑进去。最小二乘法只能获得过程模型的参数估计，而增广最小二乘法
同时又能获得噪声模型的参数估计，若噪声模型为平均滑动模型，，则只能用RELS算法才能获得无偏估计。当数据长度较大时，辨识精度低于极大似然法。
六：RGLS广义最小二乘法
仿真思路和辨识结果
模型结构选择：
模型结构选用：
其中，各个参数的真值为：
广义最小二乘算法为：
辨识结果与理论值比较，基本相同，同时又能获得噪声传递系数的参数估计。辨识结果可信：
参数a1 a2 b1 b2的估计结果：
ans =
-1.5058
0.6972
0.9316
0.4833
噪声传递系数c1 c2的估计结果：
ans =
0.6203
0.2210
RGLS广义最小二乘法的特点：
该算法用于自回归输入模型，是一种迭代的算法。其基本思想是基于对数据先进行一次滤波处理，后利用普通最小二乘法对滤波后的数据进行辨识，进而获得无偏一致估计。但是当过程的输出信噪比比较大或模型参数较多时，这种数据白色化处理的可靠性就会下降，辨识结果往往会是有偏估计。数据要充分多，否则辨识精度下降。模型阶次不宜过高。初始值对辨识结果有较大影响。
七：RIV辅助变量法
仿真思路和辨识结果
辨识模型与遗忘因子法所用模型相同,只不过此处噪声为有色噪声，
产生过程为：e(k)=v(k)+0.5v(k-1)+0.2v(k-2),v(k)为0均值的不相关随机噪声。
按照Tally法选取辅助变量x(k)=z(k-n d), n d为误差传递函数的阶数，此处为2.则有
辅助变量法的递推公式可写成：
辨识结果与理论值比较，基本相同。辨识结果可信：
参数a1 a2 b1 b2的估计结果：
ans =
-1.5314
0.7461
0.9999
0.4597
RIV辅助变量法的特点：
适当选择辅助变量，使之满足相应条件，参数估计值就可以是无偏一致。估计辅助变量法的计算量与最小二乘法相当，但辨识效果却比最小二乘法好的多。尤其当噪声是有色的，而噪声的模型结构又不好确定时，增广最小二乘法和广义最小二乘法一般都不好直接应用，因为他们需要选用特定的模型结构，而辅助变量法不需要确定噪声的模型结构，因此辅助变量法就显得更为灵活，但辅助变量法不能同时获得噪声模型的参数估计。
八：Cor-ls相关最小二乘法（二步法）
仿真思路和辨识结果
辨识模型与遗忘因子法所用模型相同：
，
e(k)=v(k)+0.5v(k-1)+0.2v(k-2),v(k)为0均值的不相关随机噪声。Cor-ls的递推公式可写成:
其中：，
M（k）为输入M序列。
初始条件：
辨识结果与理论值比较，基本相同，辨识结果可信：
参数a1 a2 b1 b2的估计结果：
ans =
-1.4896
0.6858
1.0168
0.4362
Cor-ls相关最小二乘法（二步法）特点：
把辨识分成两步进行：第一步：利用相关分析法获得对象的非参数模型（脉冲响应或相关函数）；第二步：利用最小二乘法、辅助变量法或增广最小二乘法等，进一步求的对象的参数模型。如果模型噪声与输入无关，则Cor-ls相关最小二乘法（二步法）可以得到较好的辨识结果。Cor-ls相关最小二乘法（二步法）实质上是先对数据进行一次相关分析，滤除了有色噪声的影响，再利用最小二乘法必然就会改善辨识结果。能适应较宽广的噪声范围，计算量不大，初始值
对辨识结果影响较小。但要求输入信号与噪声不相关。
九：MLS多级最小二乘法
仿真思路和辨识结果
仿真对象如下:
其中，u (k)是输入变量，此处为 M 序列；v (k ) 是零均值、方差为 1 的不相关随机噪声，通过控制λ的大小来控制信噪比。
辨识模型结构选用:
其中，
辨识过程如下：
第一级，辅助模型参数辨识
原模型可写为:
利用最小二乘法可获得辅助模型的参数无偏一致估计值:
数据长度 L=400，
第二级，过程模型参数辨识:
根据最小二乘算法可以获得过程模型的参数估计值为:
第三级，噪声模型参数辨识:
网络教育课程考试复习题及参考答案算法分析与设计一、名词解释：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。已知，=1，2，3，4，5，6，=5，=10，=3，=12，=5，=50，=6，kijr*r1234567ii1求矩阵链积A×A×A×A×A×A的最佳求积顺序（要求给出计算步骤）。1234564.根据分枝限界算法基本过程,求解0-1背包问题。已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。 5.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。6.试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：①删除一个字符。②插入一个字符。③将一个字符改为另一个字符。请写出该算法。7.对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。be2g212ad323182cf2h 8.试写出用分治法对数组A[n]实现快速排序的算法。9.有n个活动争用一个活动室。已知活动i占用的时间区域为[s，f ]，活动i,j相容的条件是：sj≥f ii，问题的解表示为(x| x =1，2…，n,)，x表示顺序为i的活动编号活动，求一个相容的活动子集，iiii且安排的活动数目最多。xxx10.设、、是一个三角形的三条边，而且x+x+x=14。请问有多少种不同的三角形？给出解答过程。12312311.
第一章算法概述 1.算法：解决问题的一种方法或过程；由若干条指令组成的有穷指令。 2.算法的性质： 1)输入：有零个或多个输入 2)输出：有至少一个输出 3)确定性：每条指令是清晰的、无歧义的 4)有限性：每条指令的执行次数和时间都是有限的 3.算法与程序的区别 程序是算法用某种程序设计语言的具体实现 程序可以不满足算法的有限性 4.算法复杂性分析 1)算法的复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复 杂性，需要空间资源的量称为空间复杂性 2)三种时间复杂性：最坏情况、最好情况、平均情况 3)可操作性最好且最有实际价值的是最坏情况下的时间复杂性 第二章递归与分支策略 1.递归概念：直接或间接调用自身的算法 2.递归函数：用函数自身给出定义的函数 3.递归要素：边界条件、递归方程 4.递归的应用 ?汉诺塔问题 void Hanuo(int n,int a,int b,int c) { if(n==1) return; Hanuo(n-1,a,c,b); move(a,b) Hanuo(n-1,c,b,a); } ?全排列问题 void Perm(Type list[],int k,int m) { //产生list[k,m]的所有排列 if(k == m) { for(int i = 0;I <= m;i++) cout< 摘要 软件测试是保证软件质量和可靠性重要手段，在这方面发挥着其它方法不可替代的作用。然而，软件测试是一个复杂的过程，需要耗费巨大的人力、物力和时间，约占整个软件开发成本的40%～50%。因此，提高软件测试工具的自动化程度对于确保软件开发质量、降低软件开发成本非常重要。而提高测试用例生成的自动化程度又是提高测试工具乃至整个测试过程自动化程度的关键所在，本文主要针对这一问题进行了研究和设计。 本文在分析软件测试和算法基本概念的基础上，提出软件测试用例的设计是软件测试的难点之一。论文提出了基于算法的测试用例生成的内含是应用算法来求解一组优化的测试用例，其框架包括了测试环境构造、算法及测试运行环境三部分，论文给出了基于算法的测试用例生成的模型。最后以三角形分类程序为例应用算法进行测试用例生成的模拟，结果显示，应用算法进行测试用例生成可行。 关键词：软件测试测试用例算法 ABSTRACT Software test is the important means that guarantee software quality and reliability，and in this respect，it plays the role that other method cannot replace. However software test is a complex process , it needs to consume huge manpower，material resources and time，which takes the 40%~50% of entire software development cost approximately . Therefore，raising the automation level of software test tool is very important for ensure software development quality and reduction software development cost . And then，the most important is raising the automation level of the test case generation for raising the automation level of test tool and even entire test process，so this paper study and design mainly according to this problem. Based on the analysis of basic concepts of software testing and genetic algorithm, this article proposes that software test case design is one of the difficulties of software testing. Paper presents the inherent in software test case designing based on genetic algorithm is using genetic algorithm to solve a set of optimization test cases, and the framework includes three parts which are test environment construction, genetic algorithm and the environment for test . Paper presents the model of software test case generation based on genetic algorithm. Finally, we take the triangle categorizer as an example, simulate software test case generation based on genetic algorithm. The results display that software test case generation basing on genetic algorithm is possible. KEY WORDS: software test , test case , genetic algorithm 《系统辨识与建模》（MATLAB编程） 信研0701 孙娅萍2007000694 编程第四次作业 仿真模型参数为：a=[-1.5 0.7];b=[1.0 0.5]，由下式递推产生502组数据，并形成如下矩阵： z(k)=1.5z(k–1)-0.7z(k–2)+1.0u(k–1)+0.5u(k–2)+v(k) 试用一次完成最小二乘法辨识系统模型。 程序部分： %************************************************************% % ***** 二阶系统的最小二乘一次完成算法辨识程序*****% % 系统辨识的输入信号u是6阶的M序列，长度是500； L = 500; u = load('u.txt'); u2 = load('u2.txt'); u1 = load('u1.txt'); z = zeros(1,L+1); for k = 3 : (L+1) % 理想输出作为系统观测值 z(k) = 1.5 * z(k-1) - 0.7 * z(k-2) + u(k-1) + 0.5 * u(k-2); end % 绘制输入信号和输出观测值的图形 figure(1) i = 1 : 1 : L; subplot(2,1,1) plot(i,u) k = 1 : 1 : (L+1); subplot(2,1,2) plot(k,z) z = z' z1 = load('z1.txt'); z2 = load('z2.txt'); z3 = load('z3.txt'); Na = 2; Nb = 2; % 定义Na、Nb； for i = 1 : (Na+Nb) if ((i == 1)) H = -1 * z2; end if (i == 2) H = -1 * z1; end if (i == (Na+1)) H = u2; end 一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ B ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ） 大学算法分析与设计复习总结 为了拿大学的那悲剧的学分，好好弄懂以下所有知识点吧。把老师的复习的提纲，特意汇总了所有考点，方便童鞋们复习。不喜勿喷！！！ 这本书是《算法设计与分析》王红梅编著 一共有以下12章，我们学了1、3、4、5、6、7、8、9 分别是“绪论、蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分治限界法 第1章绪论 考点： 1、算法的5个重要特性。（P3） 答：输入、输出、有穷性、确定性、可行性 2、描述算法的四种方法分别是什么，有什么优缺点。（P4） 答： 1. 自然语言优点：容易理解；缺点：容易出现二义性，并且算法都很冗长。 2. 流程图优点：直观易懂；缺点：严密性不如程序语言，灵活性不如自然语言。 3. 程序设计语言优点：用程序语言描述的算法能由计算机直接执行；缺点：抽象性差，是算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及其编程技巧。 伪代码优点：表达能力强，抽象性强，容易理解 3、了解非递归算法的时间复杂性分析。(P13) 要点：对非递归算法时间复杂性的分析，关键是建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。 非递归算法分析的一般步骤是： （1）决定用哪个（或哪些）参数作为算法问题规模的度量。 （2）找出算法的基本语句。 （3）检查基本语句的执行次数是否只依赖问题规模。 （4）建立基本语句执行次数的求和表达式。 （5）用渐进符号表示这个求和表达式。 [例1.4]：求数组最小值算法 int ArrayMin(int a[ ], int n) { min=a[0]; for (i=1; i 算法递归典型例题 实验一：递归策略运用练习 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 源程序： （3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？ （4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？ （5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？ （6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？ （7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？ 四、实验过程 （一）题目一：…… 1.题目分析 由已知可得，运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一 天的金牌剩余数，且每天的金牌数应为6的倍数。 2.算法构造 设运动会举行了N天， If(i==N)Gold[i]=N; Else gold[i]=gold[i+1]*7/6+i; 一、 递推最小二乘法 递推最小二乘法的一般步骤： 1. 根据输入输出序列列出最小二乘法估计的观测矩阵?： ] )(u ... )1( )( ... )1([)(T b q n k k u n k y k y k ------=? 没有给出输出序列的还要先算出输出序列。 本例中， 2)]-u(k 1),-u(k 2),-1),-y(k -[-y(k )(T =k ?。 2. 给辨识参数θ和协方差阵P 赋初值。一般取0θ=0或者极小的数，取σσ,20I P =特别大，本例中取σ=100。 3. 按照下式计算增益矩阵G ： ) ()1()(1)()1()(k k P k k k P k G T ???-+-= 4. 按照下式计算要辨识的参数θ： )]1(?)()()[()1(?)(?--+-=k k k y k G k k T θ?θθ 5. 按照下式计算新的协方差阵P ： )1()()()1()(---=k P k k G k P k P T ? 6. 计算辨识参数的相对变化量，看是否满足停机准则。如满足，则不再递推；如不满足， 则从第三步开始进行下一次地推，直至满足要求为止。 停机准则：ε???<--) (?)1(?)(?max k k k i i i i 本例中由于递推次数只有三十次，故不需要停机准则。 7. 分离参数：将a 1….a na b 1….b nb 从辨识参数θ中分离出来。 8. 画出被辨识参数θ的各次递推估计值图形。 为了说明噪声对递推最小二乘法结果的影响，程序5-7-2在计算模拟观测值时不加噪 声， 辨识结果为a1 =1.6417，a2 = 0.7148，b1 = 0.3900，b2 =0.3499，与真实值a1 =1.642， a2 = 0.715， b1 = 0.3900，b2 =0.35相差无几。 程序5-7-2-1在计算模拟观测值时加入了均值为0，方差为0.1的白噪声序列，由于噪 声的影响，此时的结果为变值，但变化范围较小，现任取一组结果作为辨识结果。辨识结果为a1 =1.5371， a2 = 0.6874， b1 = 0.3756，b2 =0.3378。 程序5-7-2-2在计算模拟观测值时加入了有色噪声，有色噪声为 E(k)+1.642E(k-1)+0.715E(k-2)，E(k)是均值为0，方差为0.1的白噪声序列，由于有色噪声的影响，此时的辨识结果变动范围远比白噪声时大，任取一组结果作为辨识结果。辨识结果为a1 =1.6676， a2 = 0.7479， b1 = 0.4254，b2 =0.3965。 可以看出，基本的最小二乘法不适用于有色噪声的场合。 自动寻峰 由于谱结构的复杂和统计涨落的影响，从谱中正确地找到全部存在的峰是比较困难的。尤其是找到位于很高本底上的弱峰，分辨出相互靠得很近的重峰更为困难。 谱分析对寻峰方法的基本要求如下： (1)比较高的重峰分辨能力。能确定相互距离很近的峰的峰位。 (2)能识别弱峰，特别是位于高本底上的弱峰。 (3)假峰出现的几率要小。 (4)不仅能计算出峰位的整数道址，还能计算出峰位的精确值，某些情况下要求峰位的误差小于0.2道。 很多作者对寻峰方法进行了研究，提出了很多有效的寻峰方法。 目的： 判断有没有峰存在 确定峰位(高斯分布的数学期望)，以便把峰位对应的道址，转换成能量 确定峰边界为计算峰面积服务(峰边界道的确定，直接影响峰面积的计算) 分为两个步骤：谱变换和峰判定 要求：支持手动/自动寻峰，参数输入，同时计算并显示峰半高宽、精确峰位、峰宽等信息，能够区分康普顿边沿和假峰 感兴区内寻峰 人工设置感兴趣大小，然后在感兴区内采用简单方法寻峰 重点研究：对感兴区内的弱峰寻峰、重峰的分解 对于一个单峰区，当峰形在峰位两侧比较对称时，可以由峰的FWHM计算峰区的左、右边界道址。峰区的宽度取为3FWHM,FWHM的值可以根据峰位m p由测量系统的FWHM 刻度公式计算。由于峰形对称，左、右边界道和峰位的距离都是 1.5FWHNM mi L =INT(m p -1.5FWHM 0.5) m R=INT(m p1.5FWHM 0.5) 式中m p是峰位，INT的含义是取整数。 对于存在有低能尾部的峰，其峰形函数描述(参见图)。 y m =H EXP[ —(^ —m p r / 2^2 ] m》mp 一 J 2 y m =HEXP[J(2m-2m p J)/2；「] , m< m p_ J 式中H为峰高，mp为峰位，匚是高斯函数的标准偏差，J为接点的道址和峰位之间的距离。在峰位的左侧，有一个接点，其道址为mp-J。在接点的右侧，峰函数是高斯函数。在接点的左侧，峰函数用指数曲线来描述。这时峰区的左、右边界道址为 m L=INT(m p-1.12FWHM 2/ J -0.5J 0.5) m R =INT(m p 1.5FWHM 0.5) 全谱自动寻峰 基于核素库法：能量刻度完成后，根据核素库中的能量计算对应的道址，在各个道址附 近(左右10道附近)采用简单的寻峰方法(导数法) 方法： 根据仪器选择开发 IF函数法/简单比较法(适于寻找强单峰，速度快) ○1优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 ○2缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 边界条件与递归方程是递归函数的二个要素 应用分治法的两个前提是问题的可分性和解的可归并性 以比较为基础的排序算法的最坏倩况时间复杂性下界为0(n·log2n)。 回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。 舍伍德算法设计的基本思想: 设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为 这显然不能排除存在x∈Xn使得的可能性。希望获得一个随机化算法B，使得对问题的输入规模为n的每一个实例均有 拉斯维加斯( Las Vegas )算法的基本思想: 设p(x)是对输入x调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x均有p(x)>0。 设t(x)是算法obstinate找到具体实例x的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x求解成功或求解失败所需的平均时间，则有： 解此方程可得： 蒙特卡罗(Monte Carlo)算法的基本思想: 设p是一个实数，且1/2 算法设计心得体会 算法设计与分析学习心得 班级：物联网1201 姓名：刘潇学号：29 一、实验内容： 这学期的算法与设计课，老师布置了这四个问题，分别是货郎担问题，动态生成二维数组，对话框下拉列表，排序问题。 二、学习掌握： 基本程序描述： 货郎担问题：货郎担问题属于易于描述但难于解决的著名难题之一，至今世界上还有不少人在研究它。货郎担问题要从图g的所有周游路线中求取具有最小成本的周游路线，而由始点出发的周游路线一共有！条，即等于除始结点外的n一1个结点的排列数，因此货郎担问题是一个排列问题。货郎担的程序实现了利用穷举法解决货郎担问题，可以在城市个数和各地费用给定的情况下利用穷举法逐一计算出每一条路线的费用，并从中选出费用最小的路线。从而求出问题的解 费用矩阵：费用矩阵的主要内容是动态生成二维数组。首先由键盘输入自然数，费用矩阵的元素由随机数产生，并取整，把生成的矩阵存放在二维数组中，最后把矩阵内容输出到文件和屏幕上。它采用分支界限法，分支限界法的基本 思想是对包含具有约束条件的最优化问题的所有可行解的解空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集，并为每个子集内的解计算一个下界或上界。动态生成二维n*n的数组程序利用指针表示数组的行和列，并逐一分配空间，在输入n的数值后，系统自动分配空间，生成n*n的数组，并产生随机数填充数组，最后将结果输入到指定文件中。 Mfc：在下拉列表框中添加内容程序，在下拉列表对应的函数中利用addstring添加需要的内容。首先定义下拉列表框为ccombox型，并定义其属性名，利用addstring函数可以任意添加需要的内容。a排序问题:快速排序的运行时间与划分是否对称有关，其最坏情况发生在划分过程中产生的两个区域分别包含n-1个元素和1个元素的时候。其算法的时间复杂度为O(n 2),在最好的情况下每次划分的基准恰好为中值，可得其算法时间复杂度为O(n㏒n)。算法的实现和理解和代码实现完全是两回事，想要完全掌握一种算法，需要动手实践，用代码实现，才能理解透彻，真正掌握。b 对话框下拉列表：这个项目简单易懂，轻松实现。 三.疑问与总结： 货郎担的问题，我认为穷举法相对比而言是比较初级的方法，费时耗力，适合在练习时选用，但是在实际问题中不建议采用。克鲁斯卡尔或者普里姆算法求取最小生成树的方 递归算法的优缺点： ○ 1优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 ○2缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 边界条件与递归方程是递归函数的二个要素 应用分治法的两个前提是问题的可分性和解的可归并性 以比较为基础的排序算法的最坏倩况时间复杂性下界为0(n·log2n)。 回溯法以深度优先的方式搜索解空间树T ，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T 。 舍伍德算法设计的基本思想: 设A 是一个确定性算法，当它的输入实例为x 时所需的计算时间记为tA(x)。设Xn 是算法A 的输入规模为n 的实例的全体，则当问题的输入规模为n 时，算法A 所需的平均时间为 这显然不能排除存在x ∈Xn B ，使得对问题的输入规模为n 拉斯维加斯( Las Vegas )算法的基本思想: 设p(x) 是对输入x 调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x 均有p(x)>0。 设t(x)是算法obstinate 找到具体实例x 的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x 蒙特卡罗(Monte Carlo)算法的基本思想: 设p 是一个实数，且1/2 调研分析总结报告 一、题目：深入理解傅氏与拉氏变换 二、完成人：第六组 杨锦涛PPT讲解及完成两个变换的意义与作用 岳雄完成PPT制作及实例的寻找 易全政完成调研分析总结报告与资料的修改补充 易雪媛完成寻找两个变换之间的联系和区别 尹柯立完成实例的筛选与补充 三、摘要 从时域到频域的分析方法是我们在实际问题解决过程中常用的 方式。对于一个杂乱无章的信号，当从时域方面很难开展的时候我们就会考虑从频域方面来进行相关的研究，以便找到相关的特征。而对于普通的函数通过傅里叶变换便可以得到一些我们所需求的东西，但是有类似于ex这样的衰减函数，我们就需要通过使用拉普拉斯变换，转化到复频域上面找到相关的特征。而本调研报告里面我们就是通过理解傅氏与拉氏变换，探讨两种变化间的区别及联系，以及在实际问题中的应用来加强我们对这两个变换的理解与应用。 四、引言 时域到实频域，这是傅氏变换；时域到复频域，这是拉氏变换。理解这两个变换的区别与联系，在实际应用中来谈论这两种变换的应用。以前在其他们课程里面了解过了很多关于傅里叶的知识，但是对于拉普拉斯却有些陌生，通过此次调研报告，我们将更加深入的理解 这两个变换给我们的学习、生活带来的便利。 五、调研材料分析 一）傅立叶变换 1）定义： 表示能将满足一定条件的某个函数表示成三角函数（正弦和/或 余弦函数）或者它们的积分的线性组合。在不同的研究领域，傅立叶变换具有多种不同的变体形式，如连续傅立叶变换和离散傅立叶变换。最初傅立叶分析是作为热过程的解析分析的工具被提出的。 2）性质： 3）意义： 傅里叶变换在物理、数论、组合数学、信号处理等方面都有广泛的应用（例如在信号处理里面，傅里叶变换的典型用途是将信号分为幅度分量和频率分量）。 傅里叶变换就是将一个信号分解成无数的正弦波信号，通过合成得到相应的信号。对一个信号做傅里叶变换就可以得到其频域特性（幅度与相位两个方面）。 傅里叶变换简单通俗理解就是把看似杂乱无章的信号考虑成由 一定振幅、相位、频率的基本正弦（余弦）信号组合而成，傅里叶变换的目的就是找出这些基本正弦（余弦）信号中振幅较大（能量较高）信号对应的频率，从而找出杂乱无章的信号中的主要振动频率特点。如减速机故障时，通过傅里叶变换做频谱分析，根据各级齿轮转速、齿数与杂音频谱中振幅大的对比，可以快速判断哪级齿轮损伤。 二）拉普拉斯变换 1）定义： 拉普拉斯变换法是通过积分变换，把已知的时域函数变换为复频域函数，从而把时域微分方程变换为复频域代数方程。 2）性质： 大学算法分析与设计复习总结 第1章绪论 考点： 1、算法的5个重要特性。（P3） 答：输入、输出、有穷性、确定性、可行性 2、描述算法的四种方法分别是什么，有什么优缺点。（P4） 答： 1.自然语言优点：容易理解；缺点：容易出现二义性，并且算法都很冗长。 2.流程图优点：直观易懂；缺点：严密性不如程序语言，灵活性不如自然语言。 3.程序设计语言优点：用程序语言描述的算法能由计算机直接执行；缺点：抽象性差，是算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及其编程技巧。 4.伪代码优点：表达能力强，抽象性强，容易理解 3、了解非递归算法的时间复杂性分析。(P13) 要点：对非递归算法时间复杂性的分析，关键是建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。 非递归算法分析的一般步骤是： （1）决定用哪个（或哪些）参数作为算法问题规模的度量。 （2）找出算法的基本语句。 （3）检查基本语句的执行次数是否只依赖问题规模。 （4）建立基本语句执行次数的求和表达式。 （5）用渐进符号表示这个求和表达式。 [例1.4]：求数组最小值算法 int ArrayMin(int a[ ], int n) { min=a[0]; for (i=1; i 通用分支递归式： 使用扩展递归技术求解下列递推关系式（1） （2） Program算法设计与分析基础中文版答案 习题 5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. Hint: 根据除法的定义不难证明: 如果d整除u和v, 那么d一定能整除u±v; 如果d整除u,那么d也能够整除u的任何整数倍ku. 对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。 数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r) 6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? Hint: 对于任何形如0<=m 设sqrt(x)是求平方根的函数) 算法Quadratic(a,b,c) 描述将十进制整数表达为二进制整数的标准算法 a.用文字描述 b.用伪代码描述 解答： a.将十进制整数转换为二进制整数的算法 输入：一个正整数n 输出：正整数n相应的二进制数 第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n 第二步：如果n=0，则到第三步，否则重复第一步 第三步：将Ki按照i从高到低的顺序输出 b.伪代码 算法 DectoBin(n) .n]中 i=1 while n!=0 do { Bin[i]=n%2; n=(int)n/2; i++; } while i!=0 do{ print Bin[i]; i--; } 9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进. 算法 MinDistance(A[0..n-1]) 算法分析与设计 学习总结 题目:算法分析与设计学习总结 学院信息科学与工程学院专业2013级计算机应用技术 届次 学生姓名 学号2０１31１0６57 二○一三年一月十五日 算法分析与设计学习总结 本学期通过学习算法分析与设计课程，了解到:算法是一系列解决问题的清晰指令,代表着用系统的方法描述解决问题的策略机制。算法能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。算法设计与分析是计算机科学与技术的一个核心问题。 设计的算法要具有以下的特征才能有效的完成设计要求，算法的特征有：（1）有穷性。算法在执行有限步后必须终止。(2)确定性。算法的每一个步骤必须有确切的定义。(3)输入。一个算法有0个或多个输入,作为算法开始执行前的初始值，或初始状态。(4）输出。一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。 (5)可行性。在有限时间内完成计算过程。 算法设计的整个过程,可以包含对问题需求的说明、数学模型的拟制、算法的详细设计、算法的正确性验证、算法的实现、算法分析、程序测试和文档资料的编制。算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法和并行算法。 经典的算法主要有: 1、穷举搜索法 穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，bing从中找出那些符合要求的候选解作为问题的解。 穷举算法特点是算法简单，但运行时所花费的时间量大。有些问题所列举书来的情况数目会大得惊人，就是用高速计算机运行,其等待运行结果的时间也将使人无法忍受。我们在用穷举算法解决问题是，应尽可能将明显不符合条件的情况排除在外，以尽快取得问题的解。 2、迭代算法 迭代法是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或方程组)的过程，为实现这一过程所使用的方法统称为迭代法。迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为ｆ(ｘ)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行： （1）选一个方程的近似根，赋给变量x0。 (2)将ｘ0的值保存于变量x1，然后计算g(x1),并将结果存于变量x0。 (3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（２）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。 3、递推算法 递推算法是利用问题本身所具有的一种递推关系求问题解的一种方法。它把问题分成若干步，找出相邻几步的关系,从而达到目的。 4、递归算法 递归算法是一种直接或间接的调用自身的算法。 能采用递归描述的算法通常有这样的特征：为求解规模为ｎ的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模 通常,一个函数在调用另一个函数之前,要作如下的事情:a)将实在参数,返回地址等信息传递给被调用函数保存; b)为被调用函数的局部变量分配存储区;c)将控制转移到被调函数的入口. 从被调用函数返回调用函数之前,也要做三件事情:a)保存被调函数的计算结果;b)释放被调函数的数据区;c)依照被调函数保存的返回地址将控制转移到调用函数.所有的这些,不论是变量还是地址,本质上来说都是"数据",都是保存在系统所分配的栈中的. ok,到这里已经解决了第一个问题:递归调用时数据都是保存在栈中的,有多少个数据需要保存就要设置多少个栈,而且最重要的一点是:控制所有这些栈的栈顶指针都是相同的,否则无法实现同步. 下面来解决第二个问题:在非递归中,程序如何知道到底要转移到哪个部分继续执行?回到上面说的树的三种遍历方式,抽象出来只有三种操作:访问当前结点,访问左子树,访问右子树.这三种操作的顺序不同,遍历方式也不同.如果我们再抽象一点,对这三种操作再进行一个概括,可以得到:a)访问当前结点:对目前的数据进行一些处理;b)访问左子树:变换当前的数据以进行下一次处理;c)访问右子树:再次变换当前的数据以进行下一次处理(与访问左子树所不同的方式). 下面以先序遍历来说明: void preorder_recursive(Bitree T) /* 先序遍历二叉树的递归算法*/ { if (T) { visit(T); /* 访问当前结点*/ preorder_recursive(T->lchild); /* 访问左子树*/ preorder_recursive(T->rchild); /* 访问右子树*/ } } visit(T)这个操作就是对当前数据进行的处理, preorder_recursive(T->lchild)就是把当前数据变换为它的左子树,访问右子树的操作可以同样理解了. 现在回到我们提出的第二个问题:如何确定转移到哪里继续执行?关键在于一下三个地方:a)确定对当前数据的访问顺序,简单一点说就是确定这个递归程序可以转换为哪种方式遍历的树结构;b)确定这个递归函数转换为递归调用树时的分支是如何划分的,即确定什么是这个递归调用树的"左子树"和"右子树"c)确定这个递归调用树何时返回,即确定什么结点是这个递归调用树的"叶子结点". 这本书是《算法设计与分析》王红梅编著 一共有以下12章，我们学了1、3、4、5、6、7、8、9 分别是“绪论、蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分治限界法 第1章绪论 考点： 1、算法的5个重要特性。（P3） 答：输入、输出、有穷性、确定性、可行性 2、描述算法的四种方法分别是什么，有什么优缺点。（P4） 答： 1. 自然语言优点：容易理解；缺点：容易出现二义性，并且算法都很冗长。 2. 流程图优点：直观易懂；缺点：严密性不如程序语言，灵活性不如自然语言。 3. 程序设计语言优点：用程序语言描述的算法能由计算机直接执行；缺点：抽象性差，是算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及其编程技巧。 伪代码优点：表达能力强，抽象性强，容易理解 3、了解非递归算法的时间复杂性分析。(P13) 要点：对非递归算法时间复杂性的分析，关键是建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。 非递归算法分析的一般步骤是： （1）决定用哪个（或哪些）参数作为算法问题规模的度量。 （2）找出算法的基本语句。 （3）检查基本语句的执行次数是否只依赖问题规模。 （4）建立基本语句执行次数的求和表达式。 （5）用渐进符号表示这个求和表达式。 [例1.4]：求数组最小值算法 int ArrayMin(int a[ ], int n) { min=a[0]; for (i=1; i return min; } 问题规模：n 基本语句：a[i]基于FPGA的递归最小二乘算法的研究与实现
最小二乘一次完成算法(程序)
算法设计与分析复习题目及答案
大学算法分析与设计复习总结
算法设计及分析递归算法典型例题
几种最小二乘法递推算法的小结
多道γ能谱分析软件中寻峰算法比较总结
递归算法的优缺点
算法设计心得体会(2)
递归算法的优缺点
算法设计与分析调研分析总结
大学算法分析与设计复习总结
算法设计与分析基础课后习题答案
算法设计与分析学习总结
递归算法工作栈的变化详解
算法设计与分析_总结0
相关主题
文本预览