下载文档原格式
《计算方法》教案（第一章误差）选用教材：普通高等教育“十一五”国家级规划教材《计算方法引论》（第三版）徐箤薇孙绳武编著主讲老师：刘鸣放2010年3月于河南大学一．基本内容提要1. 误差的来源2. 浮点数、误差、误差限和有效数字3. 相对误差和相对误差限4. 误差的传播5. 在近似计算中需要注意的一些问题二．教学目的和要求1. 熟练掌握绝对误差、绝对误差限、相对误差、相对误差限和有效数字的概念及其相互关系；2. 了解误差的来源以及误差传播的情况，掌握在基本算术运算中误差传播后对运算结果误差限的计算方法和函数求值中的误差估计；3. 理解并掌握几种减少误差避免错误结果应采取的措施，了解选用数值稳定的算法的重要性。
三．教学重点1.绝对误差、绝对误差限、相对误差、相对误差限和有效数字的概念及其相互关系，误差传播，减少误差避免错误结果应采取的措施。
四．教学难点1.误差传播；2. 数值稳定算法的选用。
五．课程类型新知识理论课；六．教学方法结合课堂提问，以讲授为主。
七．教学过程如下：Introduction1.《计算方法》课程介绍计算方法是用数值的方法研究研究科学与工程中的计算问题；它的内容主要包括：近似值的计算和误差估计两个方面；主要工具：计算机；地位：这门课已成为工科各专业，特别是计算机科学与技术、土木工程、机械、数学等专业的必修基础课。
2.发展状况几十年来，计算方法效率的提高是与计算机速度的提高几乎同步地、同比例地前进的。
这里简述一下国家重点基础研究计划项目（简称973项目）“大规模科学计算研究”（1999-2004）的主要内容，可以帮助同学们了解我国科学计算界所关心的问题。
此项目由石钟慈院士等人为首组织，集中了我国计算数学、计算物理、计算力学、计算机、以及材料、环境能源等领域60多名专家，跨学科，跨部门通力合作研究以下几个方面的主要内容：（1）复杂流体的高精度计算，含天气预报数值模拟研究；（2）新材料的物理性质机理多尺度计算研究，含超导、超硬度合金等问题的计算研究；（3）地质油藏模拟与波动问题及其反问题计算研究；（4）基础计算方法的理论创新与发展；（5）大规模计算软件系统的基础理论和实施。
第一章绪论一、内容提要1 数据结构研究的内容。
2 基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型、多形数据类型。
3 算法的定义及五个特征。
4 算法描述：类PASCAL语言。
5 算法设计要求。
6 算法分析。
二、学习重点1 数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运算）。
2 抽象数据类型的定义、表示和实现方法。
3 类PASCAL书写规范，过程（函数）中值参和变参的差别，过程调用规则。
4 用计算语句频度来估算算法的时间复杂度。
三、例题解析1 写出以下各语句执行次数（左边括号内数字为语句序号）(1) FOR i:=1 TO n DO(2) FOR j:=1 to n DO(3) [ c[I,j] := 0;(4) FOR k:=1 TO n DO(5)(5)c[I,j]:=c[I,j]+a[I,k]*b[k,j]][答案]：各语句执行次数（频度）分别为n+1，n(n+1), n2 , n2(n+1), n3[分析]：最容易发生的错误，是将第一个语句的执行次数答成n。
2 编写最优算法，从小到大依次输出顺序读入的三个整数PROC asscending;{本算法对读入的三个整数进行排序，然后按从小到大输出}{算法中核心语句如下}read(a,b,c);IF a>bTHEN [t:=a; a:=b; b:=t]; {a,b按正序排序} IF b>cTHEN [t:=c; c:=b; {c为最大}IF a<t THEN b:=t {b为中间值}ELSE [b:=a; a:=t] {a,b正序}WRITELN(a:4,b:4,c:4);ENDP; {assending}[分析]：本题正确算法有多种，但上面是最优算法：最好情况下只经过两次比较且无数据移动，而在最坏情况下，也只是经过三次比较，七个赋值语句就完成了排序。
在本课程教学中，强调“好”的算法, 不仅仅是结果正确, 而且是最优的算法。
第一章算法初步
本章概览
内容提要
算法是数学及其应用科学的重要组成部分，是计算机科学的重要基础，现代算法在科学技术、社会发展中发挥着越来越大的作用，并日益融入社会生活的许多方面，算法思想已经成为现代人应具备的一种数学素养.在信息时代的高中数学中，培养学生寻求问题的机械化解法是非常重要的，这样便于学生在学习数学和数学的应用中使用计算机技术.本章的主要内容有，算法的意义与框图、基本算法语句.本章的重点是理解算法的概念，掌握算法的三种基本结构，运用基本算法语句编制程序解决实际问题.难点是高斯消去法、循环语句.
算法概念是高中数学课程中的新内容.教材在本章一开始引出的鸡兔同笼问题，是我们熟悉的实际问题.通过算术方法与方程方法的联系，引入了求解二元一次方程组的高斯消去法的算法步骤.明白算法并不神秘，要在已有知识的基础上顺利接受算法的概念.
学法指导
注重实践，体会算法思想.算法是实践性很强的内容，只有通过自身的实践解决几个算法设计问题，才能体会到算法的思想.所以学习中可通过模仿、操作、探索，学习设计程序框图表达解决问题的过程，经历将具体问题的程序框图转化为程序语言的过程.
学习中需注意的几个问题：
①从熟知的问题出发，体会算法是程序化的；
②学会用自然语言描述算法，学会一些基本逻辑结构和语句；
③变量和赋值是算法的一个重点，设置恰当的变量，并给变量赋值，是构造算法的关键；
④不必刻意追求最优的算法，把握算法的结构和程序化思想才是我们的重点.
另外学习中可按照：实例→数学语言算法→程序框图→基本算法语言（计算机程序语言的基础）这一循序渐进的方法.。
第一章 序论一、内容提要本章主要讲述了数字信号的定义、特点和处理方法，并且简要地回顾了我们后面所涉及的一些常用的模拟信号知识。
1．数字信号定义、特点和方法信号可定义为传递信息的函数，或者信息的物理表现形式。
各种信号在数学上可表示为一个或者几个独立变量的函数。
如果我们以信号的时间为独立变量，则时间变量既可以是连续的，也可以是离散的，从而信号可以分为模拟信号（或称为连续时间信号）和离散信号（或称为离散时间信号）。
模拟信号除了是时间的连续函数外，它在一定的时刻都有理论上无限精确的数值（幅值），且此值在一定的范围内随时间连续变化，即模拟信号表现为时间连续，幅度连续。
而离散信号定义在离散时间上的信号，只在特定的时间上有精确的数值，在其他时间上数值为零或未知。
若离散信号的幅值是连续的，则取样数据信号；若将离散信号的幅度也进行离散化处理（量化），然后将离散幅度值编码为二进制数码序列，则为数字信号，其特点是时间和幅度都是离散的。
所以说数字信号是离散信号的特例，是离散信号最重要的子集。
数字信号处理是研究如何用数字或符号序列来表示信号以及如何对这些序列进行处理的一门学科。
信号处理是对信号进行某种变换（处理），包括滤波、变换、分析、估计、检测、压缩、识别等，从而更容易获得人们所需要的信息。
信号处理系统按所处理信号的种类分为：模拟系统、时域离散系统、数字系统。
与模拟信号处理相比，数字信号处理具有精度高、可靠性高、灵活性强、便于大规模集成化、易于加密、易于处理低频信号等显著特点。
数字信号处理实际上就是进行各种数学函数运算，许多数字信号处理算法都是在时域和频域两个域中进行，实现的方法有软件、硬件和软硬结合。
2．傅立叶变换的定义傅立叶变换的表达式为：()()1()()2j t j t H h t e dth t H e d π∞-Ω-∞∞Ω-∞Ω==ΩΩ⎰⎰傅立叶变换是信号处理中最重要的工具之一，它主要用于分析信号的频谱。
“计算机程序设计”教学大纲一、课程性质、目的和任务性质：“计算机程序设计”是面向非计算机类各专业的必修计算机类基础课程，是计算机教育的基础和重点。
目的：使学生掌握一门高级程序设计语言，掌握结构化程序设计和面向对象程序设计的基本方法，同时了解初步的数据结构与算法等方面的知识，具有把各个领域的基本计算和数据处理问题变成计算机应用程序的能力，为后续课程的学习创造条件。
任务：介绍计算机程序设计语言的基本知识和程序设计的方法与技术，同时包括程序设计方法学、数据结构与算法基础等方面的内容。
二、教学基本要求1．C++语言基础知识掌握变量与常量的定义与使用方法；掌握基本数据类型和表达式的使用方法，掌握C++的基本语句。
理解结构化和面向对象程序设计的基本思想和有关概念，掌握C++程序的基本框架和上机调试计算机程序的过程。
2．数组、指针与引用掌握数组的定义、初始化和访问方法；掌握字符串使用方法；理解指针和引用的概念，掌握指针使用方法，理解指针与数组的关系，了解动态内存管理方法。
3．函数掌握函数的定义与函数调用方法，理解变量的生命周期、作用域和存储类别（自动、静态、寄存器、外部），掌握C++库函数的使用方法。
4．类与对象的基础知识理解类与对象的基本概念，掌握类及其成员的声明、定义、访问方法，对象的创建与使用方法；掌握构造函数与析构函数的定义与使用；掌握静态数据成员与静态成员函数的定义与使用。
5．类的复用掌握类的组合语法；掌握派生类的定义和访问权限，类的数据成员与成员函数的继承；理解多态性概念及虚函数机制的要点；了解运算符重载。
6．输入/输出流理解C++流的概念，掌握数据的格式输入输出，掌握文件的I/O操作。
7．综合程序设计能力掌握利用所学到的面向对象的程序设计方法，编制含有多个类的程序；掌握根据实际问题和给定的算法，设计类结构并编码实现，解决小型问题。
8．程序调试掌握C++程序调试的基本方法；理解程序错误的种类和产生的原因，掌握排除语法错误的基本技能；掌握程序调试的基本技能（如设置断点、单步执行、查看中间运行结果等）。
数据摘要算法介绍(SHA、MD5和CRC32)一、数据摘要算法概述数据摘要算法是密码学算法中非常重要的一个分支，它通过对所有数据提取指纹信息以实现数据签名、数据完整性校验等功能，由于其不可逆性，有时候会被用做敏感信息的加密。
数据摘要算法也被称为哈希（Hash）算法或散列算法。
常用的数据摘要算法主要以下几大类：1、CRC8、CRC16、CRC32CRC（Cyclic RedundancyCheck，循环冗余校验）算法出现时间较长，应用也十分广泛，尤其是通讯领域，现在应用最多的就是 CRC32算法，它产生一个4字节（32位）的校验值，一般是以8位十六进制数，如FA 12 CD45等。
CRC算法的优点在于简便、速度快，严格的来说，CRC更应该被称为数据校验算法，但其功能与数据摘要算法类似，因此也作为测试的可选算法。
在 WinRAR、WinZIP 等软件中，也是以 CRC32 作为文件校验算法的。
一般常见的简单文件校验（Simple FileVerify – SFV）也是以CRC32算法为基础，它通过生成一个后缀名为 .SFV 的文本文件，这样可以任何时候可以将文件内容CRC32运算的结果与 .SFV 文件中的值对比来确定此文件的完整性。
与 SFV 相关工具软件有很多，如MagicSFV、MooSFV等。
2、MD2 、MD4、MD5这是应用非常广泛的一个算法家族，尤其是 MD5（Message-Digest Algorithm5，消息摘要算法版本5），它由MD2、MD3、MD4发展而来，由RonRivest（RSA公司）在1992年提出，目前被广泛应用于数据完整性校验、数据（消息）摘要、数据加密等。
MD2、MD4、MD5都产生16字节（128位）的校验值，一般用32位十六进制数表示。
MD2的算法较慢但相对安全，MD4速度很快，但安全性下降，MD5比MD4更安全、速度更快。
目前在互联网上进行大文件传输时，都要得用MD5算法产生一个与文件匹配的、存储MD5值的文本文件（后缀名为.md5或.md5sum），这样接收者在接收到文件后，就可以利用与 SFV类似的方法来检查文件完整性，目前绝大多数大型软件公司或开源组织都是以这种方式来校验数据完整性，而且部分操作系统也使用此算法来对用户密码进行加密，另外，它也是目前计算机犯罪中数据取证的最常用算法。
