下载文档原格式
《计算方法》教案（第一章误差）选用教材：普通高等教育“十一五”国家级规划教材《计算方法引论》（第三版）徐箤薇孙绳武编著主讲老师：刘鸣放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类似的方法来检查文件完整性，目前绝大多数大型软件公司或开源组织都是以这种方式来校验数据完整性，而且部分操作系统也使用此算法来对用户密码进行加密，另外，它也是目前计算机犯罪中数据取证的最常用算法。
A：《数值计算方法》课程教学大纲授课专业：信息与计算科学、数学与应用数学、统计学学时数：64+16学分数：5一、课程的性质和目的数值计算方法是综合性大学信息与计算科学专业的一门主要专业基础课程，同时也是许多理工科本科的专业课。
“数值计算方法”，它是以各类数学问题的数值解法作为研究对象，并结合现代计算机科学与技术为解决科学与工程中遇到的各类数学问题提供算法，它是平行于理论分析和科学实验的重要科学研究手段。
本课程的教学目的在于通过教与学，使学生系统掌握数值计算方法的基本概念和分析问题的基本方法，并通过上机实习为数值计算方法的进一步学习和解决科学与工程中的实际问题打好基础，使学生具备基本的算法分析、算法设计的能力和较强的编程能力。
二、课程教学的基本要求本课程的教学环节包括课堂讲授，实验（包括上机实验），习题课，答疑和期末考试。
通过上述基本教学步骤，要求学生理解并掌握数值计算中误差的概念、函数的数值逼近（多项式插值问题与函数的最佳逼近）、数值积分与数值微分、数值线性代数问题（线性方程组的数值解、数值求解矩阵的特征值与特征向量）、非线性方程的数值解法以及常微分方程（初、边值问题）的数值解法。
并通过上机实习，深入理解和掌握各类数学问题数值算法及了解数值计算中应注意的问题，为后续课程的学习奠定良好的基础。
本课程以课堂讲授为主（总共授课64学时），每章后配有一定数量的习题，巩固课堂所学的知识。
每一类算法应选做一定数量的实习题（全部安排16学时上机实习），以便深入理解数值算法的内容。
考核方式为闭巻考试。
三、课程教学内容第一章引论（3学时）要求理解与熟练掌握的内容有：数值计算中误差的基本概念；算法的数值稳定性问题。
一般理解与掌握的内容有：计算机中数的浮点表示。
难点：算法的数值稳定性。
第二章函数基本逼近（一）----插值逼近（10学时）要求理解与熟练掌握的内容有：代数多项式插值；差商；牛顿插值多项式；埃尔米特插值。
要求一般理解与掌握的内容有：样条函数插值；要求了解的内容有：B-样条及其性质。
软考⾃查：数据结构与算法基础数据结构与算法基础内容提要数组与矩阵线性表⼴义表树与⼆叉树图排序与查找算法基础及常见的算法数组1. 数组类型：存储地址计算2. ⼀维数组a[n]：a[i]的存储地址为：a+i*len3. ⼆维数组a[m][n]：a[i][j]的存储地址（按⾏存储）为：a+(i*n+j)*lena[i][j]的存储地址（按列存储）为：a+(j*n+i)*len稀疏矩阵例题设有如下所⽰的三⾓矩阵A[0..8,1..8]，将该三⾓矩阵的⾮零元素（即⾏下标不⼩于列下标的所有元素）按⾏优先压缩存储在数组M[1..m]中，则元素A[i,j](0<=i，j<=i)存储在数组M的（A）中。
数据结构的定义1.数据结构的概念2.数据逻辑结构线性结构⾮线性结构（树形结构：⽆环路，图：有环路）线性表的定义1、线性表的概念（a1,a2,...,a3)2、线性表常见的两种存储结构顺序存储结构（顺序表）链式存储结构（链表）线性表顺序表链表单链表循环链表双向链表链表的基本操作单链表删除结点单链表插⼊结点双向链表删除结点双向链表插⼊结点线性表-顺序存储与链式存储对⽐线性表-队列与栈例题输出受限的双端队列是指元素可以从队列的两端输⼊，但只能从队列的⼀端输出，如下图所⽰，若有e1,e2,e3,e4依次进⼊输出受限的双端队列，则得不到输出序列（D）A:e4,e3,e2,e1B:e4,e2,e1.e3C:e4,e3,e1,e2D:e4,e2,e3,e1⼴义表⼴义表是n个表元素组成的有限序列,是线性表的推⼴。
通常⽤递归的形式进⾏定义，记做:LS (a0，a1，....，an)。
注:其中LS是表名，ai是表元素，它可以是表(称做⼦表),也可以是数据元素(称为原⼦)。
其中n是⼴义表的长度(也就是最外层包含的元素个数),n=0的⼴义表为空表;⽽递归定义的重数就是⼴义表的深度,直观地说，就是定义中所含括号的基本运算:取表头head(Ls)和取表尾tail(Ls)。
学期授课计划
至学年第二学期
课程名称数据结构
授课班级
任课教师
课程类别必修总时数48 已开时数0
现开时数48 其中：课堂教学40 现场教学
课堂实验8 习题大作业
复习测验其它
学期授课计划审查意见
说明：审批意见主要应包括：①是否符合课程教学大纲要求；②教学进度是否适当合理；③重点、难点的把握是否准确；
④授课计划的内容是否完整、规范；⑤执行中的注意事项；⑥整改意见。
1、按照教学大纲做好授课计划，并附有授课计划说明。
按教学的顺序周，以两个课时为一个单元编写授课计划，每次课的目的
要求、作业布置情况应在计划中体现，重点、难点有所标注。
2、授课计划一式三份，任课教师、所在系部及教学科各保留一份。
3、授课计划须在学期开始前由各系部相关负责人审查通过，并签字后方能实施。
第1章绪论内容提要：◆数据结构研究的内容。
针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。
数据结构涵盖的内容：◆基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型。
数据——所有能被计算机识别、存储和处理的符号的集合。
数据元素——是数据的基本单位，具有完整确定的实际意义。
数据对象——具有相同性质的数据元素的集合，是数据的一个子集。
数据结构——是相互之间存在一种或多种特定关系的数据元素的集合，表示为：Data_Structure=（D, R）数据类型——是一个值的集合和定义在该值上的一组操作的总称。
抽象数据类型——由用户定义的一个数学模型与定义在该模型上的一组操作，它由基本的数据类型构成。
◆算法的定义及五个特征。
算法——是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。
算法的基本特性：输入、输出、有穷性、确定性、可行性◆算法设计要求。
①正确性、②可读性、③健壮性、④效率与低存储量需求◆算法分析。
时间复杂度、空间复杂度、稳定性学习重点：◆数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运算）。
◆用计算语句频度来估算算法的时间复杂度。
第二章线性表内容提要：◆线性表的逻辑结构定义，对线性表定义的操作。
线性表的定义：用数据元素的有限序列表示◆线性表的存储结构：顺序存储结构和链式存储结构。
顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
链式存储结构: 其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。
通过指针来实现！◆线性表的操作在两种存储结构中的实现。
数据结构的基本运算：修改、插入、删除、查找、排序1)修改——通过数组的下标便可访问某个特定元素并修改之。
核心语句:V[i]=x;顺序表修改操作的时间效率是O(1)2)插入——在线性表的第i个位置前插入一个元素实现步骤：①将第n至第i 位的元素向后移动一个位置；②将要插入的元素写到第i个位置；③表长加1。
