算法设计与分析论文

算法设计与分析论文（通用8篇）

算法设计与分析论文 篇1

算法设计与分析学习心得

班级：物联网1201 姓名：刘潇 学号：1030612129

一、实验内容：

这学期的算法与设计课，老师布置了这四个问题，分别是货郎担问题，动态生成二维数组，对话框下拉列表，排序问题。

二、学习掌握：

基本程序描述：

（1）货郎担问题：货郎担问题属于易于描述但难于解决的著名难题之一，至今世界上还有不少人在研究它。货郎担问题要从图g的所有周游路线中求取具有最小成本的周游路线，而由始点出发的周游路线一共有（n一1）！条，即等于除始结点外的n一1个结点的排列数，因此货郎担问题是一个排列问题。货郎担的程序实现了利用穷举法解决货郎担问题，可以在城市个数和各地费用给定的情况下利用穷举法逐一计算出每一条路线的费用，并从中选出费用最小的路线。从而求出问题的解

（2）费用矩阵：费用矩阵的主要内容是动态生成二维数组。首先由键盘输入自然数，费用矩阵的元素由随机数产生，并取整，把生成的矩阵存放在二维数组中，最后把矩阵内容输出到文件和屏幕上。它采用分支界限法，分支限界法的基本思想是对包含具有约束条件的最优化问题的所有可行解的解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集，并为每个子集内的解计算一个下界或上界。动态生成二维n*n的数组程序利用指针表示数组的行和列，并逐一分配空间，在输入n的数值后，系统自动分配空间，生成n*n的数组，并产生随机数填充数组，最后将结果输入到指定文件中。

（3）Mfc：在下拉列表框中添加内容程序，在下拉列表对应的函数中利用addstring添加需要的内容。首先定义下拉列表框为ccombox型，并定义其属性名，利用addstring函数可以任意添加需要的内容。a排序问题:快速排序的运行时间与划分是否对称有关，其最坏情况发生在划分过程中产生的两个区域分别包含n-1个元素和1个元素的时候。其算法的时间复杂度为O(n 2),在最好的情况下每次划分的基准恰好为中值，可得其算法时间复杂度为O(n㏒n)。算法的实现和理解和代码实现完全是两回事，想要完全掌握一种算法，需要动手实践，用代码实现，才能理解透彻，真正掌握。b对话框下拉列表：这个项目简单易懂，轻松实现。三.疑问与总结：

货郎担的问题，我认为穷举法相对比而言是比较初级的方法，费时耗力，适合在练习时选用，但是在实际问题中不建议采用。克鲁斯卡尔或者普里姆算法求取最小生成树的方法来解决货郎担的问题是更适合现实解决问题的。我认为程序可以用switch函数来将函数分成几个部分更人性化，比如分为解决问题的的选项，输出结果选项，退出程序选项等。再有就是费用矩阵的值可以从文件中读取，而结果也可以直接放在指定文件中，这样在实际应用中比较广泛。

动态生成二维数组的程序我认为如果按照规范性，我的方法是中规中矩的，毕竟再向下延伸，生成三维的数组，需要三层的指针来实现。但是就程序的简化程度和计算机处理时间来说，我认为这样双层指针的算法有些太占用内存，毕竟要给行和列各分配n个空间。我通过与同学的交流，我发现可以用1位数组来实现二维的n*n的数组。首先分配n*n的空间，然后通过循环在一行的数据达到n时自动换行。这样程序得到了一定的简化，并且减少了一定的内存使用。我认为这种方法是比较贴合实际的。

四.心得体会

在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。

如果一个算法有缺陷，或不适合某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。算法设计与分析是计算机科学与技术的一个核心问题。因此，学习算法无疑会增强自己的竞争力，提高自己的修为，为自己增彩。

算法设计与分析论文 篇2

当前并行计算已应用在生物计算、石油勘测、化学分子计算、地球物理模拟等多个领域中。并行算法主要针对每个处理节点,必须同时顾及数据共享一致性等问题中。

1 并行算法

1.1 并行算法定义及目标

算法的定义是,对解题方法的进行详细描述,有一组可以针对某种问题进行针对性解决运算的又穷规则。而并行算法则是将每一个进程整合到一起,构成一个集合,进程与进程之间可以相互协调相互作用,最终实现问题的针对性解决。通俗来讲,并行算法就是运行在并行计算机上,针对特定的问题和数据处理的算法。实际上并行算法就是把多个不同的任务一一映射到处理机上,或者将需要解决的多维问题分别映射到处理机上,然后进行相关的运算或求解。

通常我们以空间和时间两个维度的复杂性,综合表示出某个算法的复杂性,这是站在计算复杂性来看的。如若站在算法树结构去看的话,串行算法一般情况下均表现出深且窄,究其原因是因传统串行算法是设计对象是一维问题。递推算法,作为一种串行算法,在进行庞大数据计算时,它的实现是需要对算法树深度进行增加。

尽力降低时间复杂度,是并行算法的终极目标,但实现此目标一般都要增加空间复杂度。所以在并行算法中,在每个时间都将可允许计算量分别增加,其目的是最大限度降低算法计算的步数,采用浅而宽的这种独特的结构。实现的另一种办法是对每一时刻计算的复杂度进行增加,其目的是最大可能的降低时间复杂度,也就是说由之前的时间复杂度转变成了空间复杂度。

1.2 并行算法分类

并行算法的种类非常多,分类标准也均有所不同。按照基础运算对象进行分类,有数值和非数值两周并行算法。

按照并行运算过程中,各进程的执行时间进行分类,有同步、异步和独立三种不同的并行算法。

按照进程处理机中,它们各自承担所要计算任务量进行分类,有大粒度、中粒度和小粒度三种并行算法。

1.3 并行算法设计方法

并行算法的设计需要参照系统类型以及系统的特征,对某一问题针对性在处理机上进行并行解决。

并行算法的设计一般有三种办法:

对已有的串行算法进行检查,对算法中的并行性进行开发,并加以优化;

根据问题本身的特征出发,设计一个完全不同的并行算法;

在已有算法的基础上,根据问题的特征进行修改,处理类似的问题;

第一种设计方法中,如若该串行算法已经有内在相关顺序性,就非常难做并行的优化;第二种设计方法中,对现有算法进行修改,则要熟知问题的特殊性;第三种设计方法,凭空创新设计出一个算法,技巧性非常强,不但没什么章法,而且技术水平达不到。

针对并行算法的设计,目前最为普遍的设计方法有平衡树技术、分治策略技术、流水线技术以及倍增技术等等。

1.4 并行算法计算模型

并行计算模型是指从所有并行机中,把共性存在的基本特征分离出来,最终形成一个抽象的并行计算处理机,且要在具体并行机至上。它与顺序计算中的Von Neumann模型非常相似。根据普渡报告分析,并行计算模型,必须能够保证并行计算处理机针对哪种计算,表现出超强的计算能力。

并行计算的模型、算法设计以及并行机的相互关系,如图1所示:

并行计算模型在并行算法中,有着至关重要的作用。它作为一种常见物质基础提供给并行算法,进行相关研究;它还可以拿出一个简单便利的框架结构,用于并行算法的设计以及开发分析;因其适用性较强,看适用在许多种类的并行处理机上,使得新的并行算法充满生命力。

2 并行排序的基本思想

并行排序算法是参照快速排序算法的分治方法,首先在主进程内,把其宿主机上等待排序的某一数组分割为n块,文件的大小决定n的值。然后再把n块数据推送到对应数量的从进程中,从进程对其已经接受的数据在宿主机上进行串行排序,最后所有从进程将已排好序的数据回传给主进程,同时数据要放回到原数值的位置上,完成了并行排序。

按照此思想进行排序,缺点是不能确定算法的性能。可以借鉴负载均衡的思想,对该算法做出一些改进。从进程接受到数据后,不再对数据进行划分,只需要将其分为相同大小的n块,并将n块推送到对应的n个从进程中,由从进程来对分到的数据进行排序操作,排序完成后将已排序的数据传回给主进程。最后主进程只需要对接收到的n块排序数据进行归并排序,至此就完成了数据的排序工作。

3 算法设计

3.1 算法基本思想

本文并行排序的算法思想是,首先形成部分有序的数据库,然后依次读入将数据顺序分成的数据块,快的大小不能超出内存的大小。最后再对每一个小块进行排序,排序的结果保存到临时的文件中。

3.2 算法设计

假设需要排序的数据总量为N,分为n个数据块,每个数据块的数据量为A,即N=n A,每一块数据块进行排序的耗费的时间为t (A)。设立三个A的函数,readblock ( ) 读入数据块、sortblock ( ) 数据块的排序、writeblock( )保存已排序的数据块,分三个步骤完成数据排序。排序耗费的总时间t(A)由三个函数执行总时间的决定,分别记作tr(A)、ts(A)、tw(A)。

即:t(A)= tr(A)+ts(A)+tw(A)

完成所有数据排序的时间为:

T(A)=N( tr(A)+ts(A)+tw(A))= n tr(A)+n ts(A)+n tw(A)

如果只需要某一个进程对数据处理的话,即串行执行上述三个步骤,如图2所示:

但是因为readblock( )、sortblock( )、writeblock( )三者在排序的时候所占用的系统资源均不相同。若如想要数据读入readblock( )和数据保存writeblock( )二者同时进行的话,就需要把排序前数据和已排序的数据分布安防在两个不同的硬盘上,而且还不会争夺I/0资源。另外,因为这两个模块占用的CPU资源特别少,数据排序sortblock( )也可以并行运行,互不影响。所以说我们通过使用单机进行数据的排序,提高了排序算法的效率。

合理的并行算法运行时,必须根据数据块的特性制定。本文上述三个block相互排斥,在并行运算时,必须遵循以下规则:第M个数据块的readblock ( )、sortblock( )、writeblock( )结束之后,方能开始第M+1个数据块对应的readblock()、sortblock()、writeblock();第M个数据块的readblock( )结束之后方能开始sortblock();第M个数据块的sortblock( )结束之后,方能开始writeblock( )。总之,要保证三个进程并行运行完成对数据的排序工作,如图3所示:

三个进程并行运行可以充分利用系统的CPU、I/0资源,当开始运行后,任一时间都会有readblock ( )、sortblock( )、writeblock( )并行运行。这样保证了进程运行时不存在等待的情况,同时正好是重要路由算法求得的最优执行方案。

在调用三个进程之前,必须要先创建进程,应用进程创建函数。程序执行时顺序完成数据的读入、数据排序和数据的保存。多次测量执行时间后,取平均值,以此为依据启动三个进程。最终,多进程的并行排序得以实现。

4 结束语

当前数据信息量高速增长,信息化建设也逐步推进,人们对数据处理速度提出了更高的要求,计算机速度要求也越来越高,也成为许多学者和专家积极研究探索的重要课题。

算法设计与分析论文 篇3

关键词：算法设计与分析课程；动态演示；WPF；C#

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）20-0078-02

Abstract： A learning software of algorithm design and analysis course is designed and implemented by using WPF and C# language under the environment of Visual Studio 2010. The bubble sort， the eight queen problem， the tower of Hanoi problem and the knapsack problem are chosen as demonstration of the greedy method， backtracking method， divide and conquer method and dynamic programming， trying to vividly display the demonstration process of above classical algorithms.

Key words： Algorithm design and analysis course； Dynamic demonstration； WPF； C#

算法演示程序是以圖形解释算法，动态演示能够帮助学生加深算法理解，在脑海中形成算法执行过程的直观生动的印象，进而提高算法的教学效果[1]。许多算法演示系统的设计与实现的思想都来源于M.Brown等制作的BLASA系统[2]，随着可视化技术的发展，算法演示程序能够更加生动地展现出求解问题的过程。一个良好的演示系统应当具有丰富的媒体表现力、深入的细节演示效果、灵活的交互能力以及适当的游戏功能四个特性[3]。

1 整体框架

本软件基于微软推出的用户界面框架WPF[4-5]，并在Visual Studio 2010平台下设计与开发的。它提供了可视化界面，用户可直观看到分治法、贪心法、动态规划法和回溯法四种经典算法策略的求解过程[6]，软件的整体框架如图1所示。

2 具体实现

2.1 分治法

本文选择了汉诺塔问题进行分治算法的演示。汉诺塔问题中，每个盘子在柱子上的运作方式与栈结构非常类似：只能移动最上面的盘子。程序中设置了三个栈用于模拟当前三个柱子的状态。

盘子在移动过程中只涉及了四个方向：向上出盘、向左或右边移动、向下入盘。程序设置了一个方向变量direction，出盘过程中，盘子在越过柱子顶部时始终保持了方向direction=0。进程在发现direction为0时会控制盘子一次向上移动一个单位，当盘子的下边界越过了柱子的上边界，direction改变，根据相应信息，将direction设置为向左或者向右方向，左右移动过程以及向下入盘过程的移动方式和判断方法和出盘过程类似，不再赘述。

2.2 贪心法

选取冒泡排序演示贪心算法。我们采用球来表示每一个待排元素[7]，并用其透明度表示元素值的大小。用户输入球体的数目和初试排列状态（程序提供了三种状态：随机排列、逆序排列、正序排列）后，系统内部动态分配等长的球体数组。这些元素都是实例化的对象，能够被添加到画布上。

利用WPF中的Double Animation动画类来实现，它通过指定一个double类型的初始值From和同类型的终值To，使被关联的控件形成动画。如：以下代码可实现Name为lblTest的控件在一秒钟的时间内宽度增加50的动态效果。同样，球体在画布中的位置也是属性，可用动画改变。

一般排序算法都分为两个基本操作：比较和交换。本软件的冒泡排序演示程序就是利用这两个基本操作来进行演示的。如图2所示，若无需交换，则给出提示文字；若需要交换，则利用动画将相应两个球的位置颠倒。

2.3 动态规划法

本文选择0-1背包问题演示动态规划法。具体演示过程：用户完成输入后，点击演示进入演示状态。程序采用单步演示的方式，用户单击按钮，程序演示一步。利用二维数组的列数代表背包的总重量，用户可以修改。程序中使用Grid控件模拟二维数组，Grid内部的Label控件需要动态生成，见如下代码。其中thingCount为物品总数，bagWeight为背包承重，lblC是用于方便访问指定单元格的Label而设置的Label类型数组。

动态规划求中间值的代码如下。其中，第005行的判断表示当前第i个物品的价值与前i-1个物品在背包承重为j-W_arr[i]时的最大价值之和，是否比前i-1个物品在背包承重为j时的最大价值高。

2.4 回溯法

本文选择8皇后问题演示回溯法，图3和4是8皇后问题的相关演示效果图。演示程序中有一个皇后放置的试探过程，如图3所示，黑色棋子表示当前已放好的皇后位置，红色的棋子表示正在试探中。若红色棋子试探成功，则将黑色棋子放在该位置。

在该程序的另一个功能中，用户可以自己放置棋子，来感受8皇后的探索过程。本程序提供了一个错误提示的小功能，若当前棋子与棋盘上某个棋子有冲突，即在同行同列或者同一对角线，那么就会有红线闪烁，表明无法放置，如图4所示。

3 结束语

本软件在设计过程中，参照良好算法演示系统的设计要求，提供了交互功能和图形演示跟踪的功能。在算法的教学过程中能让学生接触直观的操作演示，可更好地让学生知其所以然[8]，也更快地让学生具有利用计算机解决问题的思维方式。不足之处在于它不支持算法跟踪功能，无法从代码上深刻认识算法。

参考文献：

[1]Matthew MacDonald著， 王德才 译. WPF编程宝典——C#2010版[M].

[2]刘铁猛. 深入浅出WPF[M]. 北京： 水利电力出版社， 2010.

[3]陈慧南. 算法设计与分析——C++语言描述[M]. 2版.北京： 电子工业出版社， 2012.

[4]孙永新， 闫大顺. 动画演示与算法教学研究[J]. 现代计算机， 2009（10）： 81-83

[5]张文升， 周青云， 周晓聪. 算法演示系统研究与应用[J]. 计算机应用与软件， 2008， 10：41-43.

[6]李健. 汉诺塔算法演示系统的设计与实现[J]. 现代计算机， 2011（24）： 76-80.

[7]田军， 李丰军. 基于VB程序的冒泡排序算法演示[J]. 电脑知识与技术， 2011（36）： 9410-9412.

算法设计与分析论文 篇4

1.课程基本信息

课程编号：

课程名称（中文）：算法设计与分析

课程名称（英文）：The design and analysis of algorithms 开课学期： 见培养方案与教学计划 课程类别： 专业基础课程

课程学时数与学分： 56学时（4学分，不含实验课时，4学时/周）

实验学时数与学分： 28学时（学分计算并入计算机科学实验课程，4学时/次/周）先修课程： 高等数学或数学分析，线性代数或高等代数，概率论与数理统计，离散数学，高级语言程序设计，数据结构

教学形式： 课堂讲授 + 课外教学 + 实验教学（实验课程实行单列）使用教材：

张德富，算法设计与分析，国防工业出版社，2009,8。教学参考书：

[1] T.H.Cormen, C.E.Leiserson, R.L.Rivest and C.Stein, Introduction to Algorithms(the second edition)，The MIT Press，2001 该书国内已引进，见《算法导论（第二版）》（影印版，中文本），高等教育出版社，2003 [2] M.H.Alsuwaiyel，Algorithms Design Techniques and Analysis，World Scientific Publishing Company，1998 M.H.Alsuwaiyel，吴伟昶 等译，《算法设计技巧与分析》（中文版），电子工业出版社，2004 [3] Sartaj Sahni著，汪诗林等译，《数据结构、算法与应用--C++语言描述》，机械工业出版社，2003 [4] 王晓东编著，《计算机算法设计与分析》，电子工业出版社，2005 [5] Gilles Brassard, Paul Bratley.《FUNDAMENTALS OF ALGORITHMICS》(算法基础)，清华大学出版社，2005 注：[1]和[2]两本书为主要教学参考书。

大纲制定者： 张德富、赵致琢、苏 畅（厦门大学计算机科学系）大纲审定者： 赵致琢（厦门大学计算机科学系）

2．课程性质、类别与任务

“算法设计与分析”是计算机科学与技术专业一门重点专业基础课程，也是学科核心专业基础课程之一，属于必修课程。本课程主要介绍算法的基础知识，包括抽象计算模型、算法基本概念、算法复杂性分析基础、算法设计的基本方法、以及算法复杂性理论基础。通过本课程的学习，要求学生理解并熟练掌握：了解可支持算法运行的抽象机器计算模型，算法的定义和复杂性概念，算法设计的基本技术方法，包括递归与分治法、贪心法、动态规划方法、回溯法、分支限界法以及高级图论算法等，理解并掌握算法复杂性的分析方法、NP完全性理论基础等计算复杂性的基本知识以及完全性证明概要。通过教学和实践，培养学生运用数学工具和方法分析问题和从算法的角度运用数学工具解决问题的基本能力，培养学生设计算法和分析算法复杂性的基本能力，训练学生的逻辑思维能力和想象力，从而使他们能够正确地分析和评价一个算法，进一步设计出真正有效或更有效的算法，并使之了解算法理论的基础知识和发展概况。在教学中，鼓励学生运用算法知识解决各个学科的实际计算问题，培养学生初步的独立开展科研工作的能力和理论联系实践，解决实际问题的能力，同时，为后续课程以及将来的研究工作提供必要的算法设计与分析的基础。

此外，配合实验课程的教学，学生应理论联系实际，理论指导实践，通过规范地完成一系列算法设计实验进一步巩固所学的相关书本知识，在知识、能力、素质上得到进一步的提高。

3．课程教学的基本要求（教学内容和教学重点）

“算法设计与分析”内容的重点是各种常用的算法设计方法和复杂性分析方法，包括递归与分治法、贪心法、动态规划方法、回溯法、分支限界法，以及高级图论算法、时空复杂性的分析方法、NP完全性理论基础。课程教学的基本要求是通过教学活动，使每一个学生较好地掌握课程的主要内容，同时具备对实际问题应用所学知识设计出有效算法并编程实现这些算法的能力。课程的教学内容主要包括如下知识点，其中，属于重点的内容用黑体标示，今后教学改革拟增加的内容用“{„„}”标示，部分非重要内容用括弧标注为“一般了解”： 基本概念：问题;抽象计算模型；算法的概念；算法正确性;算法效率；问题下界 算法的评估：时间复杂性和空间复杂性分析；算法的最优、最差和平均效率；渐近复杂性符号和基本效率类型；非递归算法的数学分析；{概率分析（一般了解）；分摊分析（一般了解）；算法的经验分析；算法可视计算方法}； 递归：递归设计；递归算法转非递归算法；递归算法的设计实例；递归算法的数学分析，{三种求解递归方程的方法}；

分治法：分治法的基本思想；分治法设计的特点；分治法的时间复杂性；分治法的应用（大整数乘法和Strassen矩阵乘法；棋盘覆盖）； 基本的排序算法及其复杂性分析：插入排序；堆排序；快速排序；排序算法复杂度分析及其比较（此处的教学重点在于算法分析，透过算法分析从中深入了解算法的特性，进一步揭示设计更为有效的算法的思路和途径）； 动态规划方法：动态规划的基本要素（含最优性原理）；矩阵连乘问题；0/1背包问题；装配线的调度问题；最长公共子序列；

贪心算法：贪心算法的基本要素；背包问题；哈夫曼编码；活动选择问题；{贪心算法的理论基础（一般了解）}；

回溯法：回溯法的基本思想；装载问题；0/1背包问题；旅行商问题；批处理的作业调度问题；n皇后问题；子集合问题；回溯法的效率分析；

分支限界法（分支定界法）：分支限界算法的基本思想；装载问题；0/1背包问题；旅行商问题；批处理的作业调度问题；分支限界法的效率分析；

网络与高级图论算法：最短路径问题（Prim算法；Kruskal算法；Dijkstra算法；Warshall算法和Floyd算法）；最大流问题（Ford-Fulkerson标号算法等）；最小费用最大流问题（最小费用算法等）；{匹配问题及其求解算法}； 问题的复杂性：NP完全性理论基础（P类与NP类问题，NP完全性问题及其归约；NP完全性证明；典型的NP完全问题）；{ 如何求算法复杂性的下界（一般了解）}。

4．关于教学目标、教学内容的建议和教学过程中应该注意的事项

算法设计与分析是计算机科学的核心问题之一。由于计算机科学与技术的大多数研究都与算法紧密相关，因此，高起点的算法理论基础逐步成为了高素质计算机科学与技术专门人才应该具备的必要的理论修养。设计算法的目的是要解决大量实际问题，对于较复杂的问题要求能设计出有效的算法。大量的研究实践表明，一个问题求解质量和效率的高低，主要取决于算法设计的质量。因此，算法设计与分析的重点是掌握算法的概念和基础理论，运用数学工具分析问题，从计算方法的角度如何给出非数值计算问题的计算方法、采用算法设计的常用方法设计算法，掌握分析和估计算法复杂性的方法，并特别注意以下几点：

第一，在介绍算法的基本概念时，应该着重介绍计算模型、算法的概念、考察算法的角度和算法评估的标准、复杂性分析的方法以及算法研究的目标与实际问题的关系；

第二，在介绍一些数据结构已经学习过的排序算法时，不应过多强调算法设计，而应该重点结合算法分析技术，用分析的方法评价算法的优劣，从分析结果得到设计更优算法的启示。在介绍高级的数据结构时，重点应放在对数据结构的复杂性分析上；

第三，在介绍算法设计的基本方法（例如分治法、贪心法、动态规划方法、回溯法与分支限界法）时，应该通过对大量经典问题的算法设计与分析，使学生逐渐掌握算法设计与分析的技巧，并特别注意各种算法的比较分析。例如，递归与分治、贪心与动态规划、回溯与分支限界；

第四，在介绍NP完全性理论时，应该着重从问题的分类以及各类问题的性质、相互关系入手进行研究，揭示问题的本质，从而为算法的设计提供方法指导。另外，应该着重掌握问题的转化及NP完全性理论的有关证明思想；

第五，在介绍线性规划问题及其相应算法时，应该着重介绍该算法的应用；

第六，鼓励教师将自己的研究或最新算法设计与分析的思想，结合到教学过程之中，鼓励和帮助学生运用所学的知识去解决实际问题，掌握理论与实践相结合的思想方法。第七，鼓励教师结合学科范型（也称范式），将学科方法论的内容融入教学过程之中（对教师暂不作基本要求），以帮助学生建立与“算法设计与分析”课程内容相关的科学的思想方法。

5．课外教学要求

本课程的课外教学内容和形式主要由学生阅读经典教材，任课教师辅导、答疑、批改作业、实践环节等几部分构成。本课程要求学生在有时间的情况下，尽可能完成教材中所有的习题。学生应在任课教师的帮助下，认真听课，反复思考，大量完成作业，在学习中反复进行阅读、思考、做习题，通过阅读、思考、做习题、分析、联想、概括、归纳、总结等多种有效的方式方法，比较全面、准确地掌握课程的主要内容和教学重点。

任课教师（包括助教）每周安排1次辅导、答疑，每次2小时。每次辅导、答疑至少应有一位教师参加，一般不得合并执行。主讲教师应批改全班学生作业量的5%，参加辅导、答疑的次数不少于总次数的1/5，以掌握教学的效果，调控教学进度。

课程对学生作业的质量要求是：正确、简洁、规范。

要求做题正确，意味着学生必须掌握基本概念、基本原理、基本方法、基本技术等课程的基本知识，基本知识不掌握，就很难正确解答问题，这是对学生知识水平和解决问题能力的考核。要求做题简洁和规范，意味着在正确解题的情况下，不应该存在“拖泥带水”和“东拉西扯”的问题，书面表达简练、规范，与教材中例题求解的表述基本一致。这些，正反映出学生在这方面训练有素，这是对学生素质的考核。

6．课程的实验教学

实验课程将安排一些有代表性的上机实验单元与本课程相呼应，目的是通过实验让学生体会理论与实践高度统一的学科特点，进一步认识理论、抽象、算法设计等三个过程及其相互关系，形成对学科范型更深入的体会和认识。它要求学生从分析问题出发，利用所学的算法设计技术去解决某一实际问题。通过实验工作，借助程序设计语言，掌握运用数据结构、算法和程序解决一些实际问题的方法。

学生应按照理论联系实际，理论指导实践的要求，在实际操作中规范地完成各项实验。通过实验工作，借助程序设计语言，设计并实现算法，进一步掌握运用数学工具，分析问题，提出求解方法，设计算法，分析算法的复杂性，对算法进行科学的评价等方面得到严格的训练。

实验教学按照实验单元进行，一个实验单元完成后或相近内容的一组实验单元完成后，每一个学生要撰写和提交实验报告。任课教师应依据每一个学生的实验报告和完成实验的情况，在学期结束时给出学生该门课程的学术评语和成绩，并与四个学年所有实验课程评语一起，最终产生对学生的实践能力作出综合评定的学术评语与成绩。学术评语应着重从发展的眼光和视角，考察学生是否能够理论联系实际，理论指导实践，按照实验课程的教学要求，规范地完成实验单元，较好或基本掌握了实验教学的内容。

在实验课程单列之前，课程的实践环节拟安排28学时（实际执行7次共7*4=28学时），教学内容由大纲确定，实验课程单列之后，实验考核成绩单独计算，不计入课程考核成绩。各实验单元和内容如下：

实验单元一：用贪心法求解一个具体问题的实验（程序实现）； 实验单元二：用动态规划方法求解一个具体问题的实验（程序实现）； 实验单元二：用回溯法求解一个具体问题的实验（程序实现）； 实验单元四：用分支限界法求解一个具体问题的实验（程序实现）； 实验单元五：用高级图论算法求解一个具体问题的实验（程序实现）。

上述五个实验完成后，每个学生应提交二个实验报告。前三个实验完成后提交一个实验报告，后两个实验完成后，提交一个实验报告。

7．考核的方式方法

课程结束考核方式： 闭卷考试 课堂考试时间： 3小时（180分钟）

考试命题： 任课教师命题，教研室分管该课程的负责人和分管教学的系副主任审题； 课程考试的命题内容要从大纲的要求出发，围绕本课程的教学内容、知识点和教学要求，着重从知识、能力、素质三个方面对学生进行全面的考核，重点考核学生运用知识解决问题的能力，同时考察学生的综合素质。考核范围为除了最后一周教学的内容外，其他大纲确定的知识点都在考试范围之内，课程考试的试卷命题范围不得免除期中考试已经考过的内容。试卷中不少于85%的内容应来自课程重点内容的范围，不少于10%的内容应来自课程非重点内容的范围，要求学生全面复习，以达到系统掌握，全面考核的目的。试卷的题型要力戒避免文科标准化试卷的题型，避免出现简单概念问答题和简答题。试卷题目数量一般为5、6、7题，以优秀学生在全部会做的情况下正常书写速度能够在120分钟内完成为宜。试卷题目数量的减少与全面考核的目的并不矛盾。由于考核的范围是明确的，只要教师不透露题型和范围，学生就必须全面复习，这样，即使题目不覆盖某些教学内容，也不会影响实际的教学效果。

随堂监考授权： 主讲教师和助教

算法与程序设计思想 篇5

一、教学目标 1.知识与技能：

求一批数据中最大值的算法设计思想，并将算法的设计思想用流程图表示出来。2.过程与方法：

利用现实生活中比较身高的活动，以及对武术比赛中“打擂台”流程的逐步梳理，让学生学会从此类生活实际中提炼出求最大值的思想方法，即算法思想。

培养学生分析问题、解决问题的能力，让学生学会在面对问题时能梳理出解决问题的清晰思路，进而设计出解决某个特定问题的有限步骤，从而理解计算机是如何解决、处理某种问题的。

3.情感、态度与价值观：

让学生全身心地投入到教学活动中，积极与同伴合作交流，进行探索活动。培养学生良好的思维品质，发展他们的创新思维，并养成积极的学习态度和良好的学习习惯。

创设情境，以激发学生的学习兴趣。努力营造一个可以接纳的、支持性的、宽容的课堂学习环境，让学生置身于民主和愉悦的课堂氛围中放飞思维、潜心研究、快乐创造。

二、教学重点、难点 教学重点：建立求一批数据中最大值的算法设计思想，并将此算法设计思想用流程图表示出来。

教学难点：上述重点问题同样是本课教学的难点。另外，如何把人解决问题的思路、步骤用计算机语言描述出来也是本课的难点之一。

三、教学对象分析

高一年级的学生。他们已具备了一定的观察、思考、分析和解决问题能力，也已有了顺序结构、分支结构、循环结构等知识的储备。因此，对于如何将解决问题的思路画成流程图，学生已有一定的基础，但可能还不很熟练，尤其对刚学过的循环结构，教师在课堂上要注意引导。

四、教学策略及教法设计

利用现实生活中比较一组学生身高这一事件，引导学生去发现求最大值的一种方法。如何设计求一批数据中最大值的算法？我认为让学生自己去经历整个探究过程，要比直接把现成的算法告诉学生有意义得多。它能迅速、有效地帮助学生建立程序设计思想。在完成这个任务的过程中，教师的循循善诱起到了非常关键的作用。找出一批数据中的最大者，从表面上来看是一个很简单的问题。在比较数的过程中，人因为动用了眼睛，比较大小的思维过程一闪而过，所以能很快求出一批数据中的最大值。而计算机与人不同，它对这些数据看不见、摸不着，怎么来完成这一任务呢？其实，计算机解决问题的关键，就是要把人解决问题的思维过程用计算机语言描述出来，即为大脑思维的每一步“拍照”。这是计算机程序设计教学的一个重点，也是一个难点，需要教师在教学过程中逐步引导和训练学生，使学生逐渐学会分析问题，寻求解决问题的方法和步骤。本案例运用生活中“打擂台”的实例引导学生分析求最大值的方法，通过对这一现象的分析，逐步引出求最大值的算法设计思想。1 孙朝霞.从生活中探究和建立程序设计思想——《算法与程序设计思想》教学案例.中小学信息技术教育,2005(12)

五、教学过程 1．情境创设 师（提问）： 今天在第一排就座的有10 多位同学，谁是我们第一排在座各位中的最高者呢？

师（引导）： 大家思考，通常这个任务我们是怎样去完成的？ 教师根据学生对问题的回答进行分析。引导学生往古时候比武时常常采用的“打擂台”的方式上想，提示学生可参考电视上经常播放的“挑战主持人”节目。

师生： 打擂的过程可以描述为：

（1）确定一个擂主（讨论第一个擂主是如何确定的）；（2）挑战者上台；

（3）擂主和挑战者比较；

（4）挑战者胜的话，挑战者做擂主，否则擂主卫冕；（5）重复执行（2）～（4）步骤，直到最后一个挑战者。

师： 在打擂的过程中，我们看到（2）～（4）步骤是要重复做的，所以我们该怎么办呢？

生： 需要循环结构来实现。

师： 这几个步骤序列重复到什么时候结束呢？由学生讨论结束的办法，很显然，需要在最后加上一个能判断什么时候结束的判断框。

根据讨论的步骤，最后师生共同得出打擂台的算法和流程图（如图1）。

2．求一般情况下的最大值的算法 师（引导）： 如果我们面对的是一堆数据，现在希望我们求出这一堆数据中的最大值该怎么办？通过教师和学生的共同分析，把问题进一步细化为：

（1）从第一个数据开始看起；

（2）把第一个数据的值在变量中记下来；（3）再取一个数据；

（4）比较这个数据与变量中记下的数据的值；

（5）如果这个数据的值比记下的数据的值大，则去掉变量中原来那个数据，记下新数据的值；

（6）重复执行（2）～（4），继续比较，直到最后一个数据。也就是说，计算机的变量始终记着当前比较过数据中的最大者（我们不妨用X 表示它），当取完最后一个数据时，X 中留下的也就是最大值了。

求最大值的算法设计思想用图2 表示。

注意：

a．再次让学生讨论变量的意义，弄清赋值语句的意义。

b．一些物理量用变量表达的意义。如X 表示最大值，X 表示输入的一个值，且每次循环时都用同一个变量X。

c．为了控制循环结束，必须加入一个控制循环次数的计数器I，当I 达到一定的次数后，循环工作结束。

3． 回顾小结

算法与程序设计笔试题 篇6

给出一个合适的任务执行顺序。请详细描述你的算法思路(如需要，可给出伪代码来辅助描述)，并分析其时间和空间复杂度。(20分)

2.编写函数：

统计在某段英文文本完整句子的数目，文本只包括大小写英文字母、空格、点(.)、逗号(,)。

算法设计与分析论文 篇7

该系统包括3个部分:电脑控制端、喷头控制端和传感器探测端。喷头控制端采用220 V供电,传感器探测端采用太阳能供电,如图1所示。

传感器探测端负责探测土壤的水分含量,温度值等参数,然后将测得的参数通过无线传输发往喷头控制端,喷头控制端将所得参数与用户设定值进行比较来决定是否喷水。而在电脑控制端,用户可以设置整个系统的各项参数以及监测当前系统状态,包括各节点是否在喷水以及各传感器探测得的突然参数等。每个节点均配有一无线数据收发模块,使用同一频段,每个模块在室外无阻拦传输距离约为100 m。此系统的无线传输协议中还实现了CSMA功能。

1 无线传感器网络的路由性能指标与典型协议介绍

1.1 无线传感器网络的路由性能指标

针对无线传感器网络的特点,评价一个无线传感器网络的路由协议设计是否成功时,往往采用以下指标[1]:

(1)能量的有效利用;

(2)扩展性;

(3)可靠性;

(4)收敛速度。

1.2 典型无线传感器网络的路由协议介绍

通常根据网络结构的不同,无线传感器网络路由协议可以分为:平等路由、等级路由和位置路由。

(1)平等路由协议。

在平等路由协议中,所有节点的地位、执行的功能都相同,各节点通过互相之间的合作完成任务。由于节点数量很大,如果给每个节点都分配一个全局地址,就会造成网络成本的极大负担,因此网络采用以数据为中心的路由,基站发出询问并等待回应。通常包括了DD(Directed Diffusion)、SPIN(Sensor Protocols for Information via Negotiation)、Rumor Routing等几种路由协议[2]。

(2)等级路由协议。

在等级路由协议中,节点的地位有不同,因此它们执行的功能也不一样。在无线传感器网络的等级路由中,能量相对较高的节点,作为簇头对数据进行处理,并将其传送给基站,而能量相对较低的节点则作为簇内节点,收集数据并将数据传送给簇头。通常包括LEACH(Low Energy Clustering Hierarchy)、PEGASIS (Power-Efficient Gathering in Sensor Information Systems)、SAR(Sensor Aggregate Routing)等几种协议[2]。

(3)位置路由协议。

在位置路由协议中,网络可以通过节点的位置对它们进行访问,而且节点间的距离也可以通过信号强度估计出来。邻节点之间通过此类信息的互换进行合作。某些位置路由方案为了节省能量,要求网络节点在没有任务时必须进入睡眠期。这就存在如何设计睡眠周期的问题。通常包括GEAR(Geographic and Energy Aware Routing)、GAF(Geographic Adaptive Fidelity)、SPAN等几种协议[2]。

2 专用路由算法的设计方案

根据本系统的特点,在总结各种路由协议以及其性能后,确定了以下3点基本原则:

(1)采用等级路由协议框架。

由于本浇灌的系统的特殊性,其各节点按功能不同可分为3类:电脑控制端、喷头控制端、传感器探测端。显然比较适合采用等级路由协议。

(2)采用固定路由方式,由电脑控制端计算路由。

本系统中每个节点周围的邻节点较多,若由MCU来计算路由,首先路由表过于庞大,其次计算非常复杂。为此,由计算机计算各节点的路由更可行。同时由于本系统适用于农业方面,其拓扑结构长期不变,采用固定路由可减少重新寻找路由所产生的网络开销。

(3)簇头节点的选择。

在本系统中固定采用以喷头控制端为簇头节点,以喷头控制端和簇外节点联系,传感器探测端只同其所属的簇头通信。其理由有二。首先,喷头控制端采用220 V供电,有充足的能源。其次,喷头控制端可以储存3个传感器探测端发送的数据,轻松做到汇聚数据。分簇后系统,如图2所示。

2.1 路由建立

2.1.1 喷头控制端的路由算法

当喷头控制端开机时,其内存中并没有存储任何路由信息。为此在MCU初始化以后需要以泛洪的方法广播“路由请求分组”。路由请求分组中应包含发送地址、广播地址、分组ID、标志、跳数计和路由记录,如图3所示。

(1)广播地址。本路由算法是为全网建立一个固定路由,因此广播地址应包含全网地址,故以全0表示全网地址;(2)发送地址。即为最初发送此路由请求分组的节点的地址,最终电脑控制端收到路由请求标志后根据“发送地址”来设置“发送地址”节点的路由信息;(3)标志。确定此帧信息为路由请求分组;(4)分组ID。和“发送地址”一起组成分辨一次路由信息请求的标志,从0开始往上加,由路由请求节点给出,在泛洪过程不做改变;(5)跳数计。记录经过转发的次数。当转发次数超过一定值时不再转发该帧信息,以确保不会产生广播风暴;(6)路由记录。每个转发节点均将其地址写入到路由记录中,当最终传到电脑控制端时一条路由信息就产生了。

当其它喷头控制端收到一帧路由请求分组后,其处理流程,如图4所示。其在转发请求分组时按照CSMA协议来竞争信道,以保证下一次转发的节点的随机选取。

2.1.2 电脑控制端的路由算法

当电脑控制端收到一帧“路由请求分组”分组后,将其按“发送地址”分类存储到本地。在等待一段时间后,按跳数计计算出此“发送地址”的最短路由,选择其中2条,存储到本地路由表中,一条作为当前路由,一条作为备份路由。备份路由中转发的节点尽量与当前路由中的转发节点不一致。然后将其中作为当前路由的那条路由信息发送给“发送地址”对应的节点。最终喷头控制端的路由表结构如表1所示。

2.2 路由维护和删除

由于采用固定路由协议,网络维护相对简单,各节点将周期性地检测其路由表中各路由信息的有效性。可以采用两种方式维护:一是逐跳确认,二是逐跳不确认[3]。

这里采用逐跳确认方式。每隔随机一段时间,喷头控制端将启用路由维护方法检查路由表是否依然正确。在进行路由维护时,喷头控制端按轮讯方式逐个对路由表中的表项发送 “路由维护分组”,若路由依然有效,它将收到一个由下一跳地址所对应的节点回复的“路由维护应答分组”。若在一定时间内没有收到应答分组,则认为路由失效。这时可以分两种情况。

(1)到达电脑控制端的路由失效。

此时,该喷头控制端将删除到达电脑控制端的路由,并向余下的由其转发路由的下一跳地址所对应节点告知其无法到达电脑控制端。那么当那些节点收到通知后继续向下一级节点继续发送电脑控制端无法到达信息,如此重复。

(2)其他路由失效。

此时,该喷头删除这条无效的路由,并向电脑控制端报告失效路由中下一跳地址的节点无法到达。当电脑控制端收到某个节点无法到达的信息后,将此节点定为“故障节点”。进而查询所有通过故障节点转发信息的节点,将它们列为“不可达节点”。

然后启动“故障节点”的备份路由,将备份路由设置为当前路由,发送“路由设置分组”设置该路由。若故障节点的备份路由也无法成功通信,则报告故障节点无法修复,并删除网络中到达该节点的路由。

若故障节点无法修复,则删除故障节点在电脑中的路由表中相关项。并逐个启动“不可达节点”的备份路由,操作同启动“故障节点”的备份路由。如果成功通信的话,电脑控制端将这些节点从“不可达节点”中删除。

进行完以上进程后,如果还有剩余的“不可达节点”,则将其设为故障节点,电脑控制端向用户报告所有的故障节点,由用户人工检查。若排除故障后,应重新启动所有故障节点,使其加入网络。

3 路由建立时延分析

假设这里泛洪最大跳数采用8跳,在打开这个喷头控制端i之前已有i-1个喷头控制端打开,并完成路由建立,并且其它喷头控制端至少有一个在i的传输范围内。

由路由建立过程可知,如果泛洪一直没有达到限定的8跳,那么整个网络中所有节点均将收到一次路由请求分组,并各转发一次。假设泛洪时一共经历了k跳,那么路由建立完成需要发送的分组包括开始泛洪到电脑控制端发送路由设置分组,共需要$i+\frac{k(k+1)}{2}$个分组。

在本系统中采用了CSMA冲突避免算法,无线传输速率仅为9 600 bit/s,一个分组长度为25 bit。那么发送一个分组所需要的传输时延约为21 ms,而传播时延和处理时延仅为数个微秒,因此在计算路由建立时间的情况时忽略传播时延和处理迟延。在理想不冲突的情况下,假设两个分组之间发送无间隔,那么喷头控制端i建立路由需要的时间可通过式(1)得到。如果一片绿地有3 000 m2,而一般喷头能喷距离5 m以上,那么约需要93个喷头完成覆盖整个面积。在最差的情况下(即k=8时),第93个喷头控制端建立路由需要的时间为2.7 s。如果要为整个网络建立路由,在最坏情况下所需时间可通过式(2)算出。计算结果约为2.65 min。在实际应用中,如果在不同的地方安置完93个喷头控制端,其时间≫2.65 min,因此此路由算法是切实可行的。

$\left(i+\frac{k(k+1)}{2}\right)\times \frac{25\times 8\times 100}{9600}\approx 21\left(i+\frac{k(k+1)}{2}\right)(1)$

${\displaystyle {\sum }_{i=1}^{7}2}1\left(i+\frac{i(i+1)}{2}\right)+{\displaystyle {\sum }_{i=8}^{93}2}1\left(i+\frac{g(g+1)}{2}\right)(2)$

4 结束语

文中设计的专用路由算法为了能在8位MCU上实现,必须建立路由、维护路由都比较简单、易于实现。文中首先采用的等级路由协议,用喷头控制端作为簇头节点,通过数据的汇聚减少流量。其次确定采用固定路由算法。在本系统的拓扑结果基本不变的特性情况下,既能实现有效的路由,又能减少了建立和维护路由的复杂度,使其更容易实现。从最后的分析可以看出其建立路由所需的时间较短,可提高系统运行效率。

摘要：智能无线节水浇灌系统,是一套可提高农业、园林等灌溉水利用率的系统。文中在对比了一些现有相关算法后,针对该系统的特点设计出的一种更加简单,对节点能量要求更低,更易于实现的专用路由算法。最终采用等级固定路由协议,并对该路由算法进行了路由建立时延分析,探讨了在实际应用中的可行性。

关键词：智能无线节水浇灌系统,路由算法,等级路由,时延分析

参考文献

[1]孔庆昀.无线传感器网络路由算法的研究与实现[D].吉林:吉林大学,2007.

[2]祁小宁.无线传感器网络路由算法研究[D].南京:东南大学,2006.

算法设计与分析论文 篇8

关键词:数值分析 算法设计 教学案例 网络教学

中图分类号:G424文献标识码:A文章编号:1673-9795(2012)04(b)-0104-02

现代科学技术的迅速发展,促进了数学理论和方法在科学研究和工程技术领域中的实用。数值分析研究利用计算机解决数学问题的数值方法及其理论[1],重点研究某些适合在计算机上使用的实际可行、理论可靠、计算复杂性较好的数值计算方法,主要内容包括“数值代数”、“数值逼近”和“微分方程的数值解法”三方面,综合知识点较多,既有纯数学的高度抽象性、严密的理论性和逻辑性,又有应用的广泛性与实际实验的技术性、近似性,集中体现了逼近(近似)、迭代、离散、外推(松弛)等独特的思想和技术。

传统的数值分析课程主要介绍一些经典的数值算法及其理论,但是有些算法的数值计算过程较为繁琐,通过单一的课堂讲授方式,学员往往只是对算法有一个粗略的概念,而不了解算法的具体实现过程,这在一定程度上导致学员对数值分析教学内容产生畏难和厌烦情绪,不利于学员各方面能力的培养。本文结合算法设计的逼近、迭代、外推(松弛)等技术,在数值分析的教学过程进行一些有益的探讨与尝试。

1 数值分析结合算法设计技术教学的可行性

信息技术与数学课程的整合已成为数学教育改革的热点问题,现代教育技术、信息技术、多媒体技术的快速发展,为学生的学习实验活动和交流构建平台,创设情境,提供丰富多彩的教育环境和有利的学习工具,提供探索复杂问题,多角度理解数学思想的机会,丰富学生学习和研究数学的视野[2]。

科学技术各领域的问题通过建立数学模型与数学产生了紧密的联系,但实际应用中所导出的数学模型往往不容易求出精确解,只能简化模型或利用其他方法求出近似解,而且所涉及到的运算过程(公式)比较复杂,有些运算过程仅靠一支笔、一张纸或一部计算器是很难迅速完成的。根据数学模型的特点提出求解的计算方法直到编出程序上机算出结果,进而对计算结果进行分析,这一过程就是数值分析或计算数学的主要任务。

本科《数值分析》课程一般安排在三年级开课,学生对本专业基础课程和基本数学知识已有所了解,具有一定的数学素养和计算机编程能力。在教师的指导下,通过具体教学案例的背景介绍与研究分析,学生利用所学的专业基础、数学理论知识和信息技术(主要借助计算机和数学软件),建立数学模型,针对模型选择合适的数值计算方法,并且讨论所研究问题的性态、算法的误差、稳定性、收敛性等。Matlab,Mathematic,Maple,Lingo等常用的数学软件具有强大的数值计算、符号计算和图形处理功能。这些均为数值分析结合算法设计技术的课程教学提供了日趋完善的硬件和软件条件,更多的教学手段和更大的发展空间。

2 数值分析课程的算法设计技术

文献[3]关于算法设计的技术进行详细的介绍,概括起来主要包括以下3种技术。

2.1 规模缩减技术

规模缩减技术是通过某种简单的运算方法缩减问题的规模,直到求出问题的解,目的是通过“简单的重复”解决复杂问题,集中体现了数值分析中逼近和迭代的思想。规模缩减技术的特点是:依据原问题的特点,建立某种形式简单、结构清晰的递归公式使原问题的规模递减。在教学过程中,通过渗透缩减技术,帮助学生理解算法的精髓。

以绪论中秦九韶算法为例介绍规模缩减技术。对给定的x计算多项式pn(x)的值,将多项式的次数规定为多项式求值问题的规模,秦九韶算法通过迭代计算使计算问题规模逐次减1,则经过n步,即可将所给多项式次数降为0,从而获得所求的解。此时只需作n次乘法和n次加法。

显然,求解非线性方程和线性方程组的解的迭代法也是规模缩减技术,将初始值与真解的距离看作问题的规模,则每迭代一步,得到的近似值与真解的距离逐步减少,直至达到要求的精度,迭代结束。

方程求根的二分法也是一种缩减技术,可以将包含根的区间作为问题的规模,运用某种手续逐步压缩含根区间,减少问题规模,直到所求的根满足精度要求为止。解线性方程组的消去法是为了降低方程组的阶数,同样是规模缩减技术的具体应用。

2.2 迭代校正技术

再来看一看求解线性方程组Ax=b的迭代法。给定线性方程组Ax=b的一个初始近似解,希望用某种简单方法确定校正量Δx,使校正值能够较准确地满足给定方程,由于,设为A的某个近似矩阵,则线性方程组Ax=b的近似方程称为校正方程。

校正方程是用于计算校正量的简化方程。校正方程通常要求满足:一是逼近性,它与所给方程是近似的,逼近程度越高,所获得的校正量越准确;二是简单性,校正方程越简单,所需计算量越小。

由校正方程可近似解出校正量,从而校正值相应的迭代公式为。

求解线性方程组的迭代法关键是近似矩阵的选取,要求与A近似,同时利用校正方程求解校正量Δx比较容易。当线性方程组的系数矩阵为对角阵或上(下)三角阵时,方程都比较容易求解。例如可将A分解为A=D L U

其中D为对角阵,L和U分别为严格下三角和严格上三角阵。

若令,相应的迭代公式即为Jacobi迭代公式

若令,即为Gauss-Seidel迭代公式

若令,即为松弛因子为的超松弛迭代公式。

2.3 松弛技术

在实际计算过程中,如果能够取得目标值F*的2个相伴随的近似值F0、F1,如何将它们加工成具有更高精度的结果呢？一种简便而有效的办法是,选取适当的权系数,将近似值F0、F1的某种加权平均值作为新的具有更高精度的近似值,即令:

这种基于校正量的调整与松动的方法,称之为松弛技术。它的特点是优劣互补,化粗为精,较好体现了将复杂过程化为简单过程的重复处理,不同之处在于每一步的松弛因子的选取。要使迭代过程加速收敛,必须根据具体问题使用合适的松弛技术和松弛因子。

数值分析课程的很多内容都体现了松弛技术,最典型的是求数值积分的Romberg方法、解线性方程组的超松弛迭代法、逐次线性插值、迭代加速的松弛技术等等。

3 数值分析结合算法设计技术的课程教学

依据多年的教学实践和经验,在原有的《数值分析》教材的基础上,经过反复研究与探讨,我们重新组织编写了《数值分析(第二版)》教材,2011已经由科学出版社出版。新版《数值分析》教材适当结合当代前沿学科中常用的基本内容和方法,在编排体系和内容组织上更注重紧凑和循序渐进,对精选的内容尽量作详细的论述和推导,对部分定理和结论,仅作叙述,删除了繁杂的证明过程,侧重于算法的构造思想、算法的实现、算法的误差估计、收敛性、稳定性、计算量、以及对算法的改进等等,使得课程教学内容现代化、科学化、合理化。

为了加强教学知识与内容的应用性、数学思想和方法的可操作性以及实用性,针对教学课时不够和学生学习兴趣不高的情形,在教学过程中,强调算法设计的缩减技术、校正技术、松弛技术,并恰当地融入到数值分析课堂教学内容中,再进一步通过上机验证算法,使学生亲身体验到算法的优劣以及如何改进算法,提高学生学习算法理论的兴趣,开拓学生视野,活跃学生思维。

充分发挥信息技术,多媒体技术的优势,加强有关数学软件的教学,算法设计与软件实现相结合,以强化实现能力为牵引,结合数学建模,进行案例式教学。通过教学案例、训练、实验等各种方式,在解决实际问题的同时,也给数值分析课程教学带来了活力,在一定程度上消除了学生对数值分析教学内容的畏难和厌烦情绪。

加强网络教学资源建设,建立《数值分析》网络课程,借助大学校园网的网络教学应用系统这个教学平台,实现网上实时教学、布置作业与测验、在线答疑、在线交流、在线自学等功能。通过网络教学,学生选择学习内容,进行探究性的自主学习,变“被动型”学习为“主动型”学习,培养实践能力和创新意识,加强师生之间的互动,也促进师生之间、学生之间的情感交流与合作意识。

4 结语

在教学过程中,以强化实现能力为牵引,贯彻组合教学和技术教学法,强调数值分析算法设计的缩减技术、校正技术、松弛技术,以算法设计技术教学为纽带,课堂讲授、课堂讨论、案例教学、网络教学相结合,让学生体会到数值分析课程的学习内容不是毫无生气的数学公式,而是实实在在的可以解决实际问题的算法。激发学生对学习数值分析内容和过程产生强烈的兴趣和需要,培养学生对数学知识、数学方法的应用能力以及解决实际问题的能力。

参考文献

[1]何汉林,李薇,王天虹.数值分析[M].北京:科学出版社,2011.

[2]杨雯靖.高等数学教学改革研究与探索[J].高等理科教育,2008(1):41～43.

[3]王能超.计算方法[M].北京:高等教育出版社,2005.