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

什么叫算法
    算法（Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。算法+数据结构=程序，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。
    在讨论算法的复杂性时，有两个问题要弄清楚：
    (1 一个算法的复杂性用怎样的一个量来表达；
    (2 怎样计算一个给定算法的复杂性。
    找到求解一个问题的算法后，接着就是该算法的实现，至于是否可以找到实现的方法，取决于算法的可计算性和计算的复杂性，该问题是否存在求解算法，能否提供算法所需要的时间资源和空间资源。
第二章 数据处理与误差分析
一切科学实验都要进行测量，总会记录大量的数据。所有的测量均存在误差，大学物理实验当然也不例外。误差理论和数据处理是每一个实验都会遇到的问题，两者是不可分割的有机整体，已经成为一门广受科技界重视的科学。限于篇幅和学时，本章只介绍误差理论与数据处理的初步知识，有的只引用它的结论和计算公式，以满足大学物理实验的基本要求。
§2—1 测量与误差
1. 直接测量和间接测量
在大学物理实验中，我们不仅要定性地观察和描述物理现象及其变化，还要定量地测量某些物理量的值。研究物理现象、了解物质的性质及验证物理原理都离不开测量。所谓测量就是将被测的物理量与同类已知物理量进行比较，用已知量来表示被测量。这些已知量称作计量单位。测量时，待测量与已知量比较得到的倍数称为测量值。例如某一物体的长度是单位米的倍，则该物体的测量值为米。
在人类历史的不同时期、不同国家乃至不同地区，同一物理量有许多不同的计量单位。为了便于国际贸易以及科技文化的交流，国际计量大会于1960年确定了国际单位制，其国际代号为SI。国际单位制中有七个基本单位，它们分别是长度单位米(m，质量单位千克(kg，时间单位秒(s，电流强度单位安培(A，热力学温度单位开尔文(K，物质的量单位摩尔(mol，发光强度单位坎德拉(cd。
测量可分为直接测量和间接测量两类。直接测量是指某些物理量可以通过相应的测量仪器直接得到被测量的量值的方法。如用米尺量长度，用天平和砝码测物体的质量，用电桥或欧姆表测导体的电阻等。间接测量是指利用直接测得量与被测量之间已知的函数关系，经过计算而得到被测量值的方法。例如，用单摆测量重力加速度g时，先直接测出摆长L和摆动周期T，再依据公式g = 4π2L/T2进行计算，求出g值。再如要测量导体的电阻R，可用电压表测量导体两端的电压U，用电流表测量通过该导体的电流I，然后用公式R = U/I计算出导体的电阻。
2. 测量误差及其表示方法
任何测量过程中必然伴随有误差产生，这是因为任何测量仪器、测量方法都不可能绝对正确，测量环境不可能绝对稳定，测量者的观察能力和分辨能力也不可能绝对精细和严密。因此，分析测量中可能产生的各种误差，尽可能地消除其影响，并对测量结果中未能消除的误差做出估计，是科学实验中不可缺少的工作。为此，我们必须了解误差的概念、特性、产生的原因、消除的方法、以及对未能被消除的误差如何做出估计等有关知识。
1 误差的定义
大学物理实验 8
测量误差就是测量