算法的概念及误差分析方法

《算法的概念及误差分析方法》由会员分享，可在线阅读，更多相关《算法的概念及误差分析方法（9页珍藏版）》请在金锄头文库上搜索。

1、3.2算法3.2.1.1什么叫算法算法(Algorithm)是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用 计算机算法语言描述，算法代表用计算机解一类问题的精确、有 效的方法。算法+数据结构=程序，求解一个给定的可计算或可解 的问题，不同的人可以编写出不同的程序，来解决同一个问题， 这里存在两个问题：一是与计算方法密切相关的算法问题；二是 程序设计的技术问题。算法和程序之间存在密切的关系。算法是一组有穷的规则，它们规定了解决某一特定类型问题 的一系列运算，是对解题方案的准确与完整的描述。制定一个算 法，一般要经过设计、确认、分析、编码、测试、调试、计

2、时等 阶段。对算法的学习包括五个方面的内容：设计算法。算法设计工作是不可能完全自动化的，应学习了解已经被实践证明是有 用的一些基本的算法设计方法，这些基本的设计方法不仅适用于 计算机科学，而且适用于电气工程、运筹学等领域； 表示算 法。描述算法的方法有多种形式，例如自然语言和算法语言，各 自有适用的环境和特点；确认算法。算法确认的目的是使人们 确信这一算法能够正确无误地工作，即该算法具有可计算性。正 确的算法用计算机算法语言描述，构成计算机程序，计算机程序 在计算机上运行，得到算法运算的结果；分析算法。算法分 析是对一个算法需要多少计算时间和存储空间作定量的分析。分 析算法可以预测这一算法适合

3、在什么样的环境中有效地运行，对 解决同一问题的不同算法的有效性作出比较； 验证算法。用 计算机语言描述的算法是否可计算、有效合理，须对程序进行测 试，测试程序的工作由调试和作时空分布图组成。3.2.1.2 算法的特性算法的特性包括：确定性。算法的每一种运算必须有确 定的意义，该种运算应执行何种动作应无二义性，目的明确； 能行性。要求算法中有待实现的运算都是基本的，每种运算至少 在原理上能由人用纸和笔在有限的时间内完成；输入。一个 算法有 0 个或多个输入，在算法运算开始之前给出算法所需数据 的初值，这些输入取自特定的对象集合；输出。作为算法运 算的结果，一个算法产生一个或多个输出，输出是同输入

4、有某种 特定关系的量； 有穷性。一个算法总是在执行了有穷步的运 算后终止，即该算法是可达的。 满足前四个特性的一组规则不能称为算法，只能称为计算过程， 操作系统是计算过程的一个例子，操作系统用来管理计算机资 源，控制作业的运行，没有作业运行时，计算过程并不停止，而是处于等待状态。3.2.2 算法的描述算法的描述方法可以归纳为以下几种：(1) 自然语言；(2) 图形，如 N S 图、流程图，图的描述与算法语言的描 述对应；(3) 算法语言，即计算机语言、程序设计语言、伪代码；(4) 形式语言，用数学的方法，可以避免自然语言的二义性。用各种算法描述方法所描述的同一算法，该算法的功用是一 样的，允许

5、在算法的描述和实现方法上有所不同。人们的生产活动和日常生活离不开算法，都在自觉不自觉地 使用算法，例如人们到商店购买物品，会首先确定购买哪些物品， 准备好所需的钱，然后确定到哪些商场选购、怎样去商场、行走 的路线，若物品的质量好如何处理，对物品不满意又怎样处理， 购买物品后做什么等。以上购物的算法是用自然语言描述的，也 可以用其他描述方法描述该算法。图 3.3 用流程图描述算法的例子，其函数为：f (x)二o(x 0)(x o)图 3.3 是用流程图图形描述算法3.2.3 算法的复杂性算法的复杂性是算法效率的度量，在评价算法性能时，复杂 性是一个重要的依据。算法的复杂性的程度与运行该算法所需要

6、 的计算机资源的多少有关，所需要的资源越多，表明该算法的复 杂性越高；所需要的资源越少，表明该算法的复杂性越低。计算机的资源，最重要的是运算所需的时间和存储程序和数 据所需的空间资源，算法的复杂性有时间复杂性和空间复杂性之 分。算法在计算机上执行运算，需要一定的存储空间存放描述算 法的程序和算法所需的数据，计算机完成运算任务需要一定的时 间。根据不同的算法写出的程序放在计算机上运算时，所需要的 时间和空间是不同的，算法的复杂性是对算法运算所需时间和空 间的一种度量。不同的计算机其运算速度相差很大，在衡量一个 算法的复杂性要注意到这一点。对于任意给定的问题，设计出复杂性尽可能低的算法是在设 计算

7、法时考虑的一个重要目标。另外，当给定的问题已有多种算 法时，选择其中复杂性最低者，是在选用算法时应遵循的一个重 要准则。因此，算法的复杂性分析对算法的设计或选用有着重要 的指导意义和实用价值。在讨论算法的复杂性时，有两个问题要弄清楚：(1) 一个算法的复杂性用怎样的一个量来表达；(2) 怎样计算一个给定算法的复杂性。找到求解一个问题的算法后，接着就是该算法的实现，至于 是否可以找到实现的方法，取决于算法的可计算性和计算的复杂 性，该问题是否存在求解算法，能否提供算法所需要的时间资源 和空间资源。第二章 数据处理与误差分析一切科学实验都要进行测量，总会记录大量的数据。所有的测量均存在误差，大学物

8、理实验 当然也不例外。误差理论和数据处理是每一个实验都会遇到的问题，两者是不可分割的有机 整体，已经成为一门广受科技界重视的科学。限于篇幅和学时，本章只介绍误差理论与数据 处理的初步知识，有的只引用它的结论和计算公式，以满足大学物理实验的基本要求。21 测量与误差1. 直接测量和间接测量在大学物理实验中，我们不仅要定性地观察和描述物理现象及其变化，还要定量地测量某些 物理量的值。研究物理现象、了解物质的性质及验证物理原理都离不开测量。所谓测量就是 将被测的物理量与同类已知物理量进行比较，用已知量来表示被测量。这些已知量称作计量 单位。测量时，待测量与已知量比较得到的倍数称为测量值。例如某一物体

9、的长度是单位米 的1.1196倍，则该物体的测量值为1.1196米。在人类历史的不同时期、不同国家乃至不同地区，同一物理量有许多不同的计量单位。为了 便于国际贸易以及科技文化的交流，国际计量大会于1960年确定了国际单位制，其国际代号 为SI。国际单位制中有七个基本单位，它们分别是长度单位米m),质量单位千克(kg),时间 单位秒(s)，电流强度单位安培(A),热力学温度单位开尔文(K),物质的量单位摩尔(mol)， 发光强度单位坎德拉(cd)。测量可分为直接测量和间接测量两类。直接测量是指某些物理量可以通过相应的测量仪器直 接得到被测量的量值的方法。如用米尺量长度,用天平和砝码测物体的质量,

10、用电桥或欧姆 表测导体的电阻等。间接测量是指利用直接测得量与被测量之间已知的函数关系,经过计算 而得到被测量值的方法。例如，用单摆测量重力加速度g时，先直接测出摆长L和摆动周期T, 再依据公式g = 4 n2L/T2进行计算，求出g值。再如要测量导体的电阻R,可用电压表测量导 体两端的电压U,用电流表测量通过该导体的电流I,然后用公式R = U/I计算出导体的电阻。2. 测量误差及其表示方法任何测量过程中必然伴随有误差产生,这是因为任何测量仪器、测量方法都不可能绝对正确, 测量环境不可能绝对稳定,测量者的观察能力和分辨能力也不可能绝对精细和严密。因此, 分析测量中可能产生的各种误差,尽可能地消

11、除其影响,并对测量结果中未能消除的误差做 出估计,是科学实验中不可缺少的工作。为此,我们必须了解误差的概念、特性、产生的原 因、消除的方法、以及对未能被消除的误差如何做出估计等有关知识。1) 误差的定义大学物理实验 8测量误差就是测量值x与被测量的真值p之差值，若用6表示，则有M 6 二x （2-1-1）反映了测量值偏离真值的大小，即反映了测量结果的可靠程度。所谓真值是指该物理量本 身客观存在的真实量值，但由于客观实际的局限性，真值一般是不知道的。通常我们只能测 得物理量的近似真值，故对测量误差的量值范围也只能给予估计。国际上规定用不确定度（Uncertainty ）来表征测量误差可能出现的量

12、值范围，它也是对被测量的真值所处的量值范 围的评定。有时为了使用上的需要，在实际测量中，常用被测量的实际值来代替真值。而实际值是指满 足规定精确度的用来代替真值使用的量值（又称约定真值）。例如，在检定工作中，把高一 等级精度的标准所测得的量值称为实际值。如，用 0.5级电流表来测得某电路的电流为 2.100A，用0.2级电流表测得为2.102A，贝I后者视为实际值。2） 误差的表示方法误差6 常称为绝对误差，其大小不同，反映了测量结果的优劣不等，但它只能适用于同一 物理量。例如，20mm厚的平板，用千分尺测得的绝对误差分别为0.005mm和0.003mm,则 显然后者优于前者。但若要比较两个不

13、同的物理量，女D20m m和 2m m厚的两块平板，用千分 尺测得它们的绝对误差都为0.005m m,若用绝对误差来评价，则测量误差相同。显然，用绝 对误差表示没有能反映出它的本质特征。另外，若要比较两类不同物理量的测量优劣，如某 物长20mm,绝对误差为0.05mm,某物质量为17.03g,绝对误差为0.02g，因绝对误差数值与 单位都不同而无法比较。基于上述两种情况，还需引入相对误差的概念，即100%rE8=x（2-1-2） 所以相对误差也称为百分误差。由上式可见相对误差是不带单位的一个纯数，所以它既可评 价量值不同的同类物理量的测量，也可评价不同类物理量的测量，以判断它们之间的优劣。3.

14、 误差的分类及其处理方法按照误差的特点与性质，误差可分为系统误差、随机误差（也称偶然误差）和粗大误差三类。1） 系统误差 在同一条件下（指方法、仪器、人员及环境不变），多次测量同一量值时，绝对值和符号保 持不变的误差；或在条件改变时，按一定规律变化的误差，称为系统误差。系统误差的来源 大致有以下几个方面： 21 测量与误差 9 仪器误差：由于仪器本身的缺陷或未按规定条件使用仪器而造成的误差。如仪表指 针在测量前没有调准到零位而带来的测量误差；米尺本身由于刻度划分得不准，或因环境温 度的变化导致米尺本身长度的伸缩带来的测量误差均属于这一类型。 理论或方法的误差：由于所依据的理论及公式本身的近似性

15、、测量时未能达到公式 理想化的条件或实验方法不完善而带来的误差。如用伏安法测电阻，由于没有考虑电流表或 电压表内阻带来的测量误差。 环境误差：由于外界环境，如温度、湿度、电场、磁场和大气压强等因素的影响而 带来的误差。 个人误差：由于观测者本身的感官，特别是眼睛或其它器官的不完善以及心理因素 而导致的习惯性误差。这种误差，往往是因人而异，如停表计时，有人反应较慢，所以计时 总是失之过长。系统误差可以通过校准仪器、改进实验装置和实验方法，或对测量结果进行理论上的修正来 加以消除或尽可能减小。然而发现和减小实验中的系统误差并非易事，这需要实验者深入了 解实验的原理、方法与步骤，熟悉所使用仪器的特点

16、和性能，还要在实验中不断积累理论知 识和实践经验，才能找出产生系统误差的原因以及消除、减小系统误差的方法。2） 随机误差随机误差是在对同一被测物理量进行多次测量过程中，绝对值与符号都以难以预知的方式变 化着的误差。这种误差是由于实验中各种因素的微小变化而引起的，如温度、气流、光照强 度、电磁场的变化引起的环境变化；观测者在判断、估计读数上的偏差等使得多次测量值在 某一值附近有涨落。就某一次测量而言，这种涨落完全是随机的，其大小和方向都是难以预 测的。但对某个量进行足够多次的测量，随机误差总是按照一定的统计规律分布。常见的一 种情况是：测量值比真值大或比真值小的概率相等；误差较小的数据比误差大的数据出现的 概率大；同时，绝对值很大的误差出现的概率趋于零。这是称之为正态分布（即高斯分布）