算法分析与设计教案

算法分析与设计教案（精选8篇）

篇1：算法分析与设计教案

课型：新课 《算法与程序设计》（选修）人教版

教学目标：

1.进一步理解什么是；算法，知道算法的多样性

2.能够对设计的算法做简装的评价

3.学会利用自然语言、流程图和伪代码来描述算法

教学内容

1.了解什么是算法及其特征 2.学习三种描述算法语言

教学重点:通过例子设计算法

教学难点:三种描述算法语言的使用

课时数：1课时

正课讲解

一、算法是“灵魂”

1.算法存在于人们生活中，如：上街购物、顾客付款、营业员（主）找银等。

2.“韩信点兵问题”有不同的求解过程，就有不同的算法。

有N个人，除以3，5，7，分别余2，3，2，求N。

3.算法——解决问题的方法和步骤。

算法是尼克劳斯.沃斯（N.Writh）提出的，他指出：算法+数据结构=程序。

（即算法不能单独构成程序，它必须和数据结构合二为一）

4.算法的发现

时间：公元前3000年~公元前1500年 地点：巴比伦

巴比伦人求解“算法”的过程：先用解代数方法，再计算实际数目，最后写上一句短句“这就是一个过程”。

5.算法的特征

我们曾在必须修课中提过一点算法，如：冒泡排序法。

例：计算1+2+3+„„+100=？

分析：这个算法有限制范围，可以在有限时间内完成，这是算法的第一个特征：有穷性。计算此算法可以用纸笔、算盘、运算器

和计算机来完成，且计算过程是多样的，但结果是唯一的。这就是算法的可行性、确定性。

计算方法：

⑴把这100个数按顺序相加。

⑵用凑数法：1+99=100，2+98=100，3+97=100，„„，49+51，最后只剩下50和100。

⑶令S=0，使1≤n≤100，先执行S=S+n ⑴，再执行n=n+1 ⑵

n=1，S=0时，S（0）=1 n=2，S=1时，S（0）=3 n=3，S=3时，S（0）=6

n=4，S=6时，S（0）=10 n=5，S=10时，S（0）=15 n=6，S=15时，S（0）=21„„

算法的另外一个特征：输入、输出。

练习：水仙花数问题，如153=1^3+5^3+3^3，分析它应满足什么条件才能使用此方法？

二、如何描述算法

1.用自然语言描述算法

⑴自然语言——人们日常生活中使用的语言。

⑵此种语言的特点：通俗语易懂，缺乏直观性和简洁，且易产生歧义。

使用此种语言的注意事项：描述要求尽可能精确，详尽。

例：用自然语言描述凯撒密码的原理

第1步：输入26个英文字母，它们分别对应1~26个数学。

第2步：令a=1，k=3，n=26。

第3步：使a的取值范围为1≤a≤26，F(a)=(a+k)mod n，转第5步。

第4步：a=a+1，转第3步。

第5步：输出F(a)相对应的数字。

第6步：把数学转化成相当的字母，输出字母。

第7步：累计字母出现顺序，转第4步。

练习：现有一串字母“PROGRAM”给它加密，请设计算法，用自然语言描述。

2.用流程图描述算法

⑴特点：描述算法形象、直观，容易理解。

⑵流程图符号

3.用伪代码描述算法

特点：描述的算法简、易懂，修改容易，容易转化为程序语言代码。

例：分析课本经9页算法描述

第一个条件：y mod 4=0

判断闰年的条件：⑴y不能被100整除；⑵y能被400整除且y能被400整除。

判断不是闰年的条件：⑴y mod 4=0 且y mod 100=0,但y不能被400整除；⑵y不能被4整除。

表示条件判断语句 表示循环处理语句：

IF 条件 THEN 执行语句一 Do While 条件循环语句

ELSE执行语句二 Loop

END IF

条件语句中可以包含多个子语句

实践：用表格比较自然语言、流程图和伪代码3种描述方法的优缺点。

篇2：算法分析与设计教案

一、教学目标

1、知识与技能

（1）理解算法的概念，培养学生自我探索信息，高效获取信息的能力；

（2）能初步利用算法解决简单的问题，培养学生的理论联系实际能力和动手操作能力。

2、情感、态度、价值观

学生在学习过程中，通过亲身经历体验获得对此算法的感性认识，培养学生自我获取信息、分析评价信息、、表达呈现信息的能力，进一步提高其信息素养。

二、教学重点难点

重点：算法概念的理解

难点：如何科学合理的选择和设计算法。

三、教学策略与手段

以趣味性问题设置情境，激发学生探索解决问题的兴趣，与学生进行互动探讨，通过Flash演示材料，比较直观地把抽象的问题简单化，使学生的思考逐步深入，从而总结出算法的概念，学会如何设计和选择算法，培养学生自主探究学习的能力。

四、教学过程（1课时）

（一）我们来共同寻找下面一些生活中比较现实的问题的解决方法。【问题一】天下真的有“不要钱的午餐”吗？

某一餐馆门口海报上写着“不要钱的午餐”，规则如下：在三个月内，来宾必须凑够五个人，五人每次来就餐必须按照不同的顺序坐，直到把所有可能的顺序都坐一遍，以后来吃饭就可永远免费”。于是有人想，这太容易了，每人每次坐不同的位置，吃五次不就行了？于是他就叫上自己的朋友参加这项活动，可是，吃了十次之后，还没有吃上免费午餐，这是怎么回事呢？

学生们感觉非常有意思，很快以小组为单位进行热烈的讨论并得出了破解问题的步骤：①第一个座位５个人都有坐的机会②第二个座位只有４个人中的任一个有坐的机会（一个人不能同时坐两个座位）③第三个座位只有３个人中的任一个有坐的机会④第四个座位只有２个人中的任一个有坐的机会⑤第五个座位只有１个人有坐的机会⑥计算：５×４×３×２×１＝１２０⑦得出结论：需要吃１２０次才有可能吃上免费午餐。

【问题二】有三个和尚和三个妖怪过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果妖怪的人数大于和尚的人数，那么和尚就会有被吃掉的危险。你能不能找出一种安全的渡河方法呢？请写一写你的渡河方案。学生：学生讨论回答。〖展示步骤〗

①两个妖怪先过河，一个妖怪回来； ②再两个妖怪过河，一个妖怪回来； ③两个和尚过河，一个妖怪和一个和尚回来； ④两个和尚过河，一个妖怪回来； ⑤两个妖怪过河，一个妖怪回来； ⑥两个妖怪过河。

【Flash动画展示】通过讨论和动画展示，我们可以知道，计算机解决问题和人解决问题一样需要有清晰的解题步骤。算法就是解决问题的程序或步骤。

（二）【课件展示】算法的概念：

1、广义的算法是指完成某项工作的方法和步骤，在我们日常生活中也经常使用算法，只是没意识到罢了。如：洗衣机的使用说明书是操作洗衣机的算法，菜谱是做菜的算法等等。

2、在数学中，现代意义的算法是指可以用计算机来解决的某一类问题的程序和步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成。

【小试身手】按照这样的理解,我们可以设计出很多由具体数学问题解决一类数学问题的算

法.下面看一个例子:（要求学生自己考虑并写出具体的算法）

鸡兔同笼问题。一个笼子里有鸡和兔，现在只知道里面一共有17个头，48只脚，鸡和兔各有多少只？试设计一个求解的算法。

【设计意图】求解鸡兔的问题简单直观，却包含着深刻的算法思想。应用解二元一次方程组的方法来求解鸡兔同笼问题。

第一步：设有小鸡x只，小兔y只，则有

第二步：将方程组中的第一个方程两边乘－2加到第二个方程中去，得到，得到y=7； 第三步：将y=7代入（1）得x=10。

【变一变】在笼中有鸡、兔若干，已知有头a个，有脚b只，求各有多少只鸡和兔。

【师生合作】老师带领学生共同书写规范的算法的具体步骤，最后引出算法使用的范围：能解决一类问题，并且能重复使用。

（三）【课件展示】算法的基本特征

①有穷性 ②确定性 ③不唯一性 ④有效性（逻辑性）

1、有穷性：一个算法应该包含有限个操作步骤，而不能是无限的。

2、确定性：算法的每个步骤都应该是明确无误的，不能含义模糊，使执行者无所适从。

3、有零个或者多个输入，有一个或者多个输出

4、有效性：算法中的每一步都应该能有效地执行，执行算法最后应该能得到确定的结果。

【教学总结】

1、本节课通过一些生活中看似简单问题的解决方法和步骤，使学生比较轻松的接受了生活算法的概念，进一步理解了计算机算法的概念。

2、课堂教学的效益取决于学生对所学知识理解了多少，能否用所学知识来解决一些实际问题。本节课的设计突出讲与练的结合，培养学生的动手能力，并且引出学生对下一节课的内容的思考，比较顺利的完成了本节课的教学任务。

篇3：静态排序算法设计与分析

关键词：静态排序,算法复杂度,记录比较,记录移动

0 引 言

随着各行各业的飞速发展,计算机需要存储与处理的数据也在以惊人的速度增加。在如此庞大的数据群中,人们为了便于检索,通常希望能在计算机中保存的数据是按关键字值大小排列的有序表。在现今的计算机系统中,有相当大的一部分CPU时间开销是用于对数据的排序整理上的,而在这一部分CPU时间开销中,记录移动所引起的CPU时间开销又占据了相当大的一部分,并且如果待排序的记录相当大(即每个记录所占空间较多)时,记录移动所引起的CPU时间开销将对整个数据排序的CPU时间开销起到决定性的作用。因此,学习和研究各种排序算法,分析并设计出高效适用的排序算法,是摆在计算机科学工作者面前的重要课题之一。为了解决大量的记录移动而引起的CPU时间开销问题,本文提出了静态排序算法。这是一种记录移动次数(2n)恒定的稳定的内部排序算法。

1 算法的定义与核心思想

1.1 定 义

静态排序算法是一种通过对数组Value[1…n]中任意两个记录比较来计算出每个记录在已排序数组中的索引值并把其储存在数组Index[1…n]中,进而由Result[Index [i]]=Value[i]直接得到已排序数组Result[1…n]以达到对数据排序的目的稳定的内部排序算法。

1.2 核心思想

每个记录在已排序数组中的索引值与其所在的数组中比它本身大(小)的记录的个数有关。具体而言,若在一个数组中小于记录A的记录有k(0<=k<n-1)个,则当对该数组排序后所得到的数组中记录A的索引值一定为k(规定:若Value[i]== Value[j]且i<j则Value[i]< Value[j])。由原数组记录值及各个记录在已排序数组中的索引值直接构成有序数组。

2 算法的实现

2.1 排序实现

静态排序算法的实现过程主要分为三步。

第一步 通过记录值比较来求得各个记录在已排序数组中的索引值。求索引值的过程中有两种不同的情况。情况一:数组中任意两个记录的值大小都不相同,此时在数组中比记录A的值小的记录的个数则为记录A在已排序数组中的索引值。情况二:数组中至少存在两个记录的值相同,假设这两个值相同的记录分别为记录C和记录D,此时比记录C和记录D的值(假设记录D比记录C在原数组中的索引值大)小的记录的个数则不可能同时是记录C和记录D在已排序数组中的索引值。为了保持静态排序是稳定排序的特性,假设记录D的值要比记录C的值大。综合上述两种情况所述,若记录X的值小于比其索引值大的记录Y的值则记录Y在已排序数组中的索引值加1,否则记录X在已排序数组中的索引值加1。当对数组中任意两个记录进行比较后,就可以得到所有记录在已排序数组中的索引值。

第二步 由数组Value[1…n]与数组Index[1…n]直接构成有序数组。其中巧妙地应用了两个数组相同位置的对应关系,即Index[i]中存储的索引值恰巧是Value[i]在已排序数组中的索引值。因此,可以得出Result[Index[i]]=Value[i]。这是一个有序有目的地插入记录的过程。当遍历了整个数组Index[1…n]后,所有的记录就有序地插入到了结果数组中,最终得到有序数组Result [1…n]。

第三步 把结果数组Result [1…n]中的所有记录拷贝到原数组Value[1…n]中,最终实现原数组的排序目的。下面是用算法语言描述静态排序的过程。静态算法如算法1所示[1,2,3]。

2.2 测试结果

如图1所示:原先数组是一个无序数组,调用静态排序算法排序后得到一个有序的数组,从而验证了静态排序算法的正确性。

3 算法及测试结果的分析

表1是在测试静态排序算法过程中各变量值及存储值的变化情况(表中CC是记录的比较次数)。

从表1可得每一趟比较都会得出在数组中比该记录小的记录的个数,这个数值也正好是该记录在已排序数组中的索引值。分析静态排序的效率:

时间复杂度:

$Y={\displaystyle \sum _1^{n-1}i}=n(n-1)/2$

需进行n(n-1)/2次比较,且移动记录2n次。因此,总的时间复杂度为Ο(n2)。

空间复杂度:

需要借助一个长度为n的整型数组空间和一个原数组相同的数组空间。所以空间复杂度为О(n)。

4 各种算法的比较与分析

4.1 各种算法的平均复杂度

如表2所示,从时间复杂度上看,静态排序、起泡排序、插入排序、选择排序的平均时间复杂度均为Ο(n2),而希尔排序、快速排序和归并排序的平均时间复杂度均为Ο(nlog2n)。从空间复杂度上来看,起泡排序、插入排序、希尔排序、选择排序仅需一个存储空间,空间复杂度为О(1)。静态排序与归并排序都需要与n同级别的空间,空间复杂度为О(n)。而快速排序需要的空间与原数组中记录的顺序有关,需要(log2n,n)个存储空间,空间复杂度为О(n)。

4.2 各种算法的记录的比较次数与移动次数

4.2.1 根据记录比较与移动次数的理论值分析比较算法

各种算法的记录比较次数的理论值如表3所示。

各种算法的记录移动次数的理论值如表4所示。

4.2.2 根据记录比较与移动次数的实验值分析比较算法

以下四张图是根据1000次实验得到的数据绘制而成的。为了真实地模拟实际中的排序问题,每次的测试数据都由随机数构造而成。

图2是各种排序算法中记录移动次数的总体比较,从图中可以看出起泡排序的记录移动次数是最多的,且比其它的排序方法的移动次数要多很多,插入排序的移动次数次之。其余五种排序方法的移动次序要少很多。

图3是图2中其余五种排序算法的记录移动次数的详细比较图,从图中可以得出静态排序的移动次数是最少的,快速排序次之,接着是选择排序,然后是希尔排序,最后是归并排序。所以只从记录的移动次数来看,静态排序是最优的。

图4是各种算法中记录比较次数的总体比较图,从图中可以直观地发现静态排序、起泡排序、静态排序的比较次数是最多的,大约是n2/2,插入排序的移动次数次之,大约是n2/4。

图5是图4中其余三种排序算法中记录比较次数的详细比较图,从图中可以看出归并排序的比较次数是最小的,快速排序次之,再次是希尔排序。同时根据各种排序算法的比较次数曲线变化幅度可以得出快速排序和希尔排序的比较次数受记录初始顺序的影响较大,而归并排序的比较次数受到记录初始顺序的影响却很小。

4.3 各种算法的稳定性

根据排序算法稳定性的定义以及各种算法的核心思想及实现可得静态排序、插入排序、起泡排序、选择排序和归并排序是稳定的,而希尔排序与归并排序是不稳定的。

4.4 各种算法的简单性

从算法简单性看,静态排序、插入排序、选择排序和起泡排序是简单算法,而希尔排序、快速排序和归并排序是经过改进后的算法,因此是复杂算法。

5 结 语

数据排序所引起CPU时间开销主要由排序过程中的记录比较次数和移动次数决定。从待排序的记录个数n的大小看,n越小,采用简单排序方法越合适,n越大,采用改进的排序方法越合适。因为n越小,Ο(n2)同Ο(nlog2n)的差距越小,并且输入和调试简单算法比输入和调试改进算法要少用许多时间。 从记录本身信息量看,若记录本身信息量越大,则移动记录所花费的时间就越多,所以对记录的移动次数较多的算法不利。在这种情况下,移动次数越小的算法将越有优势,本文提出的静态排序算法也就是为了更好地适应这种情况而提出的。

起泡排序是最简单的排序算法,在各个算法中平均效率是最低的,但便于理解,适用于记录个数n较小的排序中。

选择排序是一种简单排序算法,它的比较次数非常大,但是移动次数相对较小,所以适用于记录个数n较小而记录本身信息量较大的排序中[5]。

插入排序也是一种简单排序算法,它的比较次数和移动次数都比较大,约为n2/4,适用于记录个数n较小的排序中[6]。

希尔排序中当n在某个特定的范围内时,所需的比较次数约为n1.3,移动次数约为3n1.3,适用于记录个数较大而记录本身信息量较小的排序中[7]。

快速排序的平均时间为klog2n,从平均时间性能而言,快速排序最佳[4],适用于记录个数n较大的排序中[8]。

归并排序的平均时间复杂度为Ο(nlog2n),空间复杂度为О(n),适用于记录个数n较大而记录信息量也较大的排序中[9]。

静态排序是一种稳定的简单排序算法,它的记录比较次数非常大,但移动次数却是所有算法中最小的,并且记录的比较次数和移动次数仅与记录个数n有关而与记录的初始顺序无关,因此适应于记录个数n较小而记录信息量非常大的排序中。

参考文献

[1]阿霍,霍普克劳夫特,乌尔曼.计算机算法的设计与分析[M].黄林鹏,王德俊,张仕,译.机械工业出版社,2007.

[2]科曼,等.算法导论[M].潘金贵,等译.机械工业出版社,2006.

[3]郑宗汉,郑晓明.算法设计与分析[M].电子工业出版社,2010.

[4]严蔚敏,吴伟民.数据结构[M].清华大学出版社,2010.

[5]张明亮,李兴良.选择排序的一种改进及分析[J].苏州科技学院学报,2007,24(2).

[6]李宝艳,马英红.排序算法研究[J].电脑知识与技术,2007,2(8).

[7]杨智明.希尔排序算法实现与分析[J].电脑编程技术与维护,2010(2).

[8]杨锋英,刘会超.改进的快速排序算法[J].科技广场,2010(1).

篇4：算法分析与设计教案

关键词：算法设计与分析课程；动态演示；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.

篇5：算法设计与分析学习报告

持续13周的高级算法设计与分析课程结束了。选修了这门课程的同学们即将迎来最后的考试。回顾这半年以来关于这么课程的学习情况，我体会最深的是：不论是从深度还是从广度上，现在所习的算法比曾经学习的算法难度增加了很多。但是邓教授极富经验的教学和详细的课件，为我的学习提供了很大的方便。可是毕竟我以前的底子不够厚，基础不够劳，在听课中会出现跟不上教师思路的现象。我也积极的采取措施，争取处理好这种情况。总体说来，上完算法课，我还是学到了很多东西的。下面我就对所学的内容进行梳理归纳，总结一下我在学习中的体会和研究心得。

算法课程的开课阶段，邓教授为我们简单介绍了算法，课堂上可能用到的参考资料，以及一些著名的算法方面的书籍，为我的学习提供潜在的工具。我购买了一本教材——《算法导论》。这本书够厚，够详细。但是我一直没有机会仔细的研读。我想有一天希望能够好好读一下。在介绍算法的课堂上，我还了解了算法相关的一些基本概念，算法的重要性，还有算法的历史。我印象最深的就是一个叫图灵的外国人。对计算机科学与技术这个领域做出了图书贡献。我个人认为，堪比爱因斯塔发现相对论的贡献。都揭示了某个领域的本质。开辟的一个领域的发展。对于整个人类来说，他们这类人都是功不可没的。已经不能简单的用伟人来形容他们。但是人类社会需要这样的人，社会需要一些人的推动才能进步。说到这里，我不禁要想，算法到底有什么用，也许答案是简单的，为了方便写程序实现系统功能。这只是表面的用途。我觉得最本质的作用是为了社会进步。辩证唯物主义自然观中有关于科学技术的详细定义。之所以产生科学技术是为了发挥人的主观能动性去改造自然。学习和研究算法正是为了让人在一定的限度内改造自然。我不是在扯，而是在写算法报告和背自然辩证法资料的时候产生的心得体会，不知道算不算邓教授要求的心得。介绍完算法历史以后，就进入的真正的算法设计与分析的学习。首先是算法的定义和时间复杂度等。然后，为了方便以后的课程学习，我学到了一些必要的数学知识，既是为了以后的学习打基础，也是为了弥补在曾经的学习中的不足。这些数学知识包括生成函数和主定理等。这些数学知识都是连在高等数学里都没有接触过的。不知道属于哪个范畴的数学，反正用两个字形容就是“厉害”。我学的不亦乐乎，晕头转向。

几堂课后，对算法这一概念有了基本的了解，也对数学知识进行了补强。我们在邓教授的带领下，进入了实际的算法技术的学习。一共有六种常用技术：分治法，贪心法，周游法，回溯法，动态规划法，分支界定法。最先学习的是六种技术之首，应用最广泛的，分治法。分治法的算法思想真的很神奇，不止分治，这几种算法常用技术都很神奇，可以将问题的求解进行很大程度上的优化，而且有些还是反人类的想法。对我的智商着实是一个考验。当然了，算法的学习不只是靠智商的，更要靠辛勤的汗水，即便有时候汗水没有智商有用，但是你还是要付出汗水。因为这是一种福报。能力有多大，就享有多大的成果。这就好比一个人中了500万的头彩。这个人有能力享有这500万的财富吗？如果他有足够很好的驾驭这笔财富的能力，那么在未来，他会让这笔财富继续增长，直到达到他的能力的极限情形。如果他没有驾驭的能力，用不了多久，他就会分崩离析。我的思维再一次被学科外的体会占据了。言归正传，我学了很多利用分治法结局的问题，比如寻找最近点对，求数组的第k小元等。这些都是利用分治法解决的。在这之中，出现了平衡的概念，和分治法是密切相关，甚至是不可分的。在这部分

中，最后学习了离散傅立叶变换和快速傅立叶变换。

接下来的学习的算法技术是动态规划法。这种技术和分治法有很多相同点，最基本的就是都是讲问题分解为若干子问题，不同点是分治的子问题是相互独立的，动态规划的子问题是重复的，这也决定了，一个用递归的计算方式，一个用递推的计算方式。我也学到了利用动态规划法解决的很多问题，简单的如矩阵连成问题，复杂一点的有最长公共子序列问题，最有二分搜索树和流水作业问题。在这部分知识中，还有一点，就是备忘录方法，可以说是对动态规划法的一个完善和改进。

随着课程的进行，我又学到了集合算法。主要知识点有平摊分析，合并算法，2-3树，以及一些概念如字典，可并堆和可连接队列等。需要注意的是这部分留过作业的FIND()和FIND_DEPTH()两个函数。还有有穷自动机问题。

接下来学习的是随机算法。应该说这部分内容还是相当重要的，而且应用也非常广泛。在日常生活中更是随处可见。举一个最简单的例子，当我在看NBA比赛的时候，每节的休息时间都要抽奖，那个随机显示的中奖观众就是基于随机算法实现的功能。在这部分内容中，我学到了3个重要的随机算法：KMP、Monte Carlo和Las Vegas算法的评价和比较。这也是作为作业研究过的。也学习的素数判定随机算法。这里，要明白Miller-Rabin算法，是Rabin在Miller提出的基础上，研究出来的很常用的算法。

在课程的最后阶段，我学到了RAM和RASP这两个概念。应该说这部分知识是我学的最不好的地方。算法本质还没有了解。还需要进一步的研究。最后是NP-C和NP-hard问题。

篇6：算法分析与设计教案

(1 教材模块:《算法与程序设计》(2 年级:高中一年级

(3 所用教材出版社:上海科技教育出版社(4 所属的章节: 第二章第三节(5 课时数:2课时 【内容分析】

选择结构是VB程序设计三个基本结构之一。是学生学习VB程序入门,掌握程序语言的重要内容。

【教学目标】

知识

1、掌握条件逻辑表达式的构成

2、掌握简单IF语句的格式及其含义

技能

1、通过自主探究学习、编写程序,让学生掌握简单if语句 的语法格式和使用方法。

情感

1、形成良好的程序程序书写格式。

2、学会自主学习和养成独立解决问题的能力。【学生分析】

县级城市学生大部分来自农村,80%以上的学生在学校没有受到正规的计算机入门教育,大部分学生对编程一无所知,还有一部分学生英语基础特差,但通过一个学期的信息技术必修课学习后对电脑简单操作有一定认识,因为选择结构是程序设计基础中的一节重要内容,所以本节课分二个课时进行教学,第一课时主要讲IF语句的简单结构和标准结构,第二课时讲多重分支与多重选择语句。

【教学重点和难点】

重点:简单选择结构和标准选择结构的语法和逻辑运算。难点:选择结构算法的实现。【教学策略设计】 【教学过程设计】 1.教学过程

教学环节 教师活动 学生活动 设计意图 导入 新课 5分钟

活动1:给出特定关键词“小学生、公共汽车”,要求学生用“如果…… 就……”句型造句;活动2:要求学生用以上关键词,使 用“如果……就……否则就……”句型造 句;活动3:由于现在公共汽车都是无人

售票,公交公司想要设计一款自动检票的 设备,该设备能够自动测出身高并确定是 否需要买票。假定机器自动测出乘客的身 高为H,请大家想想计算机该怎么判断乘 客需要买什么票?用你自己的语言说出 判断过程。并试着翻译成英语。学生思考并积 极回答 大部分学生会 造句:如果小 学生身高小于 1.2米,就不用 买票.如果H<1.2米 就不用买票, 否则就要买 票.通过使用学生熟 悉的常识,引起学生积

极思考,激发学生学习兴趣,想像力和继续探 讨的热情和期待。新课 教学 20分钟

1.师生一起画出活动3的流程图 2.探究学习:写出该程序

学生自己看书学习IF语句的语法 并试着写出该程序

3.展示部分学生作品并小结IF语句 的简单格式。(有的同学可能用简单格式 有的可能用标准格式,这里一起讲评 4.完善作品

(提醒学生程序的书写格式 5.小结IF语句语法格式

1、IF 条件 THAN 语句块 END IF

2、IF 条件 THAN 语句块1

ELSE 语句块2 END IF 学生一起画 学生自学教材 并试着写出程 序

找两位做得最 好的同学上台 讲解他的程序 并介绍选择实 现的方法 未做完的或程 序有错误的同 学进一步完善 作品,已经完 成的同学作为 小老师指导其 他同学。

请两位同学上 台小结IF语句 的格式。在学生使用“如 果……就……否则 就……”造句,并翻译 成英语的基础上学生 很快会形成“IF…… THEN……ELSE……”概 念,通过自己学习教材 的IF语句语法格式从 而将模糊的想法转化 成严格的程序语句定 义,再通过程序实践、老师点评、小结和自己 改正、完善作品从而内 化为自己的知识。

课堂 任务

1、书64页课本例题填空。完成

全部学生必须

通过二个任务强化IF语句的练习,并 练习12分钟

任务

2、会考后老师要把会考成绩转 化成是否合格,凡是60分及以上的就“合 格”,低于60分的就“不合格”,请你帮 老师写一个电脑自动判断的程序。任务

3、在任务2中如果还想增加一 档超过85分的给“优秀”评价,该怎么 做?如果再分细一点,比如40分以下, 40—59,60—70,71—80,81—90,91以 上,又该怎么做呢? 全体学生要求 完成

在完成前面二 个任务的基础 上思考并试一 试

通过扩展任务引起同 学们的思考,并引出下

节课要讲的内容。

学生 作品 展示 5分钟 在课堂练习开始后几分钟就会有学 生上交作品,老师可以开始对学生作品进 行评价。力争评价所有作品,学生看到老 师在点评学生作品会激发他们做好作业 的激情。

展示部分有特色、有代表性的学生作 品。

在评价阶段如 果有做得好的 学生提醒其他 同学向其学习。

学生自己展示 并解说,老师 适当点评 通过投影不断展 示已经交作业的同学 作品,激发其他同学的

热情。学生把上台展示 自己的作品当成一种 荣耀每节课选择尽量 多的同学上台展示能 提高学生的学习热情。

课堂 总结 3分钟 请一位学生小结本节课的学习内容 老师提醒学生注意IF语句的书写格式和 逻辑表达式的构成。同时提示要解决任务 3有二种方式。学生总结IF语 句的语法和使 用方法

课后作业看书上多重选择结构并试着完成任务3。提出问题为下节 课上课做准备。【教学反思】

1、通过分解本节课的教学内容大部分学生可以通过自主学习掌握教学内容。

篇7：算法分析与设计知识点总结

算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。算法的特征：

可终止性：算法必须在有限时间内终止；

正确性：算法必须正确描述问题的求解过程；

可行性：算法必须是可实施的；

算法可以有0个或0个以上的输入；

算法必须有1个或1个以上的输出。

算法与程序的关系：

区别：程序可以不一定满足可终止性。但算法必须在有限时间内结束；

程序可以没有输出,而算法则必须有输出；

算法是面向问题求解的过程描述，程序则是算法的实现。

联系：程序是算法用某种程序设计语言的具体实现；

程序可以不满足算法的有限性性质。

算法描述方式：自然语言，流程图，伪代码，高级语言。

算法复杂性分析：

算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。

算法复杂性度量：

期望反映算法本身性能，与环境无关。

理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响）。

一般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单位的开销作为标准。

算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F(N, I, A)。

第二章递归与分治

分治法的基本思想：

求解问题算法的复杂性一般都与问题规模相关，问题规模越小越容易处理。

分治法的基本思想是，将一个难以直接解决的大问题，分解为规模较小的相同子问题，直至这些子问题容易直接求解，并且可以利用这些子问题的解求出原问题的解。各个击破，分而治之。

分治法产生的子问题一般是原问题的较小模式，这就为使用递归技术提供了方便。递归是分治法中最常用的技术。

使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。

分治法所能解决的问题一般具有以下几个特征：

该问题的规模缩小到一定的程度就可以容易地解决；

该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；利用该问题分解出的子问题的解可以合并为该问题的解；

该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。（这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。）

递归的概念：

直接或间接地调用自身的算法称为递归算法，用函数自身给出定义的函数称为递归函数。

反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。

边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。

第三章动态规划

动态规划的基本思想：

动态规划算法与分治法类似，其思想把求解的问题分成许多阶段或多个子问题，然后按顺序求解各子问题。最后一个阶段或子问题的解就是初始问题的解。

分治法求解时，子问题数目太多，从而导致解决原问题需要耗费指数级时间。与分治法不同的是，动态规划中分解得到的子问题往往不是互相独立的。

但不同子问题的数目常常只有多项式级。用分治法求解时，有些子问题被重复计算了许多次。

动态规划的适用条件：

动态规划法解所能解决的问题一般具有以下两个基本因素：

一、最优子结构性质

当问题的最优解包含着其子问题的最优解时，称该问题具有最优子结构性质。

二、重叠子问题性质

递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。

其它同分治法。

动态规划问题的特征：

求解的问题是组合优化问题；

求解过程需要多步判断，从小到大依次求解；

子问题目标函数最优解之间存在依赖关系；

动态规划算法设计的基本步骤和要素：

基本步骤：

（1）找出最优解的性质，并刻画其结构特征。（考察是否适合采用动态规划法。）

（2）递归地定义最优值。(建立递归式或动态规划方程)

（3）以自底向上的方式（或以自顶向下的备忘录方法）计算出最优值。

（4）根据计算最优值时得到的信息，构造最优解。

要素：

最优子结构

重叠子问题

备忘录（表格）

应用实例分析：

1、矩阵连乘问题：

（1）分析最优解结构：

计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解，满足最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。

（2）建立递归关系；

（3）计算最优值—递归求解（递归求解最优值复杂度较高的原因是：子问题重复度高)；计算最优值—迭代查表求解

计算最优值—备忘录求解

（4）构造最优解

第四章贪心法

贪心算法的基本思想：

当一个问题具有最优子结构性质时，可用动态规划方法求解，但有时会有更简单有效的方法。

顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。

贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心算法中，较大子问题的解恰好包含了较小子问题的解作为子集，这与动态规划算法设计中的优化原则本质上是一致的。

动态规划算法在某一步决定优化函数的最大或最小值时，需要考虑到它的所有子问题的优化函数值，然后从中选出最优的结果；贪心算法的每步判断时，不考虑子问题的计算结果，而是根据当时情况采取“只顾眼前”的贪心策略决定取舍。

贪心算法的设计要素：

可以用贪心算法求解的问题一般具有2个重要的性质：

1、最优子结构性质：

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征

2、贪心选择性质：

贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法与动态规划算法的主要区别。

动态规划算法通常以自底向上的方式求解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

应用实例：

1、活动安排问题：

第五章回溯法

回溯法的基本思想：

回溯法的使用条件：

回溯法适用于搜索问题和优化问题。

回溯法的设计要素：

针对问题定义解空间：

问题解向量

解向量分量取值集合构造解空间树

两类典型的解空间树：

子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。子集树通常有2n个叶结点

排列树：当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有n!个叶结点。

判断问题是否满足多米诺性质。

搜索解空间树，确定剪枝函数。

确定存储搜索路径的数据结构。

第六章分支限界法

分支限界法的基本思想：

分支界限法类似与回溯法，也是在问题解空间中搜索问题解的一种算法。

分支界限法与回溯法思想对比：

求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

常见的两种分支界限法：

队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。

优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

最大堆：最大效益优先

篇8：分布并行算法分析与设计

在过去计算机并行处理技术发展缓慢, 主要原因是计算机电子设备处理器价格比较贵, 网络通信处于前期发展阶段不太成熟, 使用并行技术开发的软件功能和应用上不完善。在20 世纪后期, 随着网络通信技术的迅速发展, 高位数处理器的开发和应用, 给并行处理技术提供了很好的发展空间。在计算机产业中, 人们意识到计算机的处理计算的能力在高科技的技术发展中被人们越来越重视, 并行处理技术是高性能计算机处理技术未来主要技术, 并行处理技术可以大大提高计算机的整体性能。 现代科学技术和全球经济的发展都离不开计算机技术, 计算机技术已经改变了人们的生活方式, 存在各个领域, 计算机技术的发展比其他科学技术的发展要快, 对人类的影响比较深远。 工程领域对计算机计算的需求是无限的, 然而计算机的单机计算是有限的, 这两个关系决定了分布式并行计算方法必然称为计算机计算方法的主导。

2 研究现状

国内在国防和国家科技的建设上, 并行处理技术起着重要作用, 我国对高性能计算机的发展非常重视, 尤其在石油、气象、 航空等大范围领域的研究逐年增加, 我国在并行处理技术领域比其他领域发展显著主要是因为并行处理技术领域的高性能计算机。 国内的科技工作者正努力研究多种并行处理的计算方法, 软件发展的重心主要体现在算法能力上面, 我国研发的数据库并行处理系统处于世界同领域的领先地位, 并行体系结构、 并行系统软件、 并行算法是并行处理技术的3个方面, 我国在高性能计算机的研制方面投入多, 在系统开发方面投入较少, 低成本延迟高带宽、 并行应用软件和并行算法是我国研发的重点。

国外美国、 日本在并行计算方面发展出力领先水平, 美国在商业领域已经应用高性能计算, 并行检索技术, 在并行计算方面的研究资料国外设计的也比较全。 国内外差距大, 我国发展高性能计算机技术不能再等, 算法是研究的重要内容。

3 并行计算机分类和计算环境

3.1 并行计算机的分类

并行算法能够运行的基础主要是并行计算环境和并行计算机, 并行算法的设计和实现取决并行计算机环境和并行计算机, 并行计算机从最初的向量机, 如今并行计算机主要是机群系统, 并行计算机分为SIMD型并行计算机、 共享存储MIMD并行机、 分布式存储MIMD并行机、 分布共享存储MIDI。

SIMD型并行计算机是单指令流多数据流并行机, 在指令流执行的时候, 处理机对多组数据执行相同指令流, 也就是说SIMD并行机无论怎样运行它的指令只有一条, 同步性、 确定性是SIMD型并行计算机的特征, SIMD型并行机已经不能满足并行技术的发展, 是早期产品, 如今已经不被使用。

共享存储MIMD并行机是多指令流多数据, 所有处理机执行统一程序, MIMD并行机是现在并行算法中普遍使用的编码方式。

分布式存储MIMD并行多处理机解决了共享存储MIMD并行处理机的瓶颈问题, 在整个系统中, 每个节点都有自己的存储器, 在访问的时候只能自己访问自己的存储器, 不能互相访问, 各个节点通过网络作为传输介质连接到一起, 分布式存储扩展性强, 但是编程复杂, 在节点之间的信息传递不是通明的, 分不知存储MIDI并行处理机分两类, 大规模处理机和群集系统。

分布共享存储MIDI并行机在系统中每个处理机有自己的存储器, 共享地址空间由各个局部存储器连接组成。

3.2 并行计算机的计算环境

并行计算机体系结构, 并行算法的效率直接受并行计算机体系结构的影响, 在这个系统中处理机的连接方式构成并行计算机体系结构。 并行处理机互连方式主要是网络直径和等份宽度两个重要因素。 网络系统中两个距离较远的处理机之间的具体构成网络直径, 两个距离远的处理机在消息传递的时候出现时间的延迟用网络直径这个参数来衡量。 等份宽度是网络系统中两个相等距离所去掉的网络边的条数。 判断并行体系结构性能重要原则是小的网络直径和大的等份宽度。集群系统中处理机的连接方式用总线结构表示, 在总线结构中, 各处理机连接在一个总线上面, 靠一个总线进行传输, 在消息进行传输时要判断先后顺序, 总线结构图如图1 所示。

并行计算机的软件环境包括编码语言、 操作系统、 计算环境3 部分, 用于消息传递的并行环境常用的是PVM和MPI。PVM并行计算环境叫做并行虚拟机系统, 系统规模小通用性强, 在TCP/IP协议环境下也适用, PVM特点支持多用户同时执行多个应用程序, 提供通信原语, 多个进程组成一个进程组, 同一个进程可以属于多个进程组, 在不同的网络系统中可以使用, 兼容性强, 容错功能强。 MPI并行计算环境是消息传递界面的一种方式, MPI并行计算环境特点实现的开发工具方式多, 消息的发送和接收可以重叠, 对消息缓存区可以有效管理, 可靠地运行在集群系统中, 保证其他软件可以正常运行, 标准平台上也可以使用。

4 并行算法定义及分类

算法是解决某个特定类型问题的解题方法的一系列规则, 并行算法是在解决问题方面相互联系起协调作用的可以并行执行的过程的集合。 并行算法是在并行处理机上把多个问题和任务映射到多处理机进行求解的处理数据的一种方法。 传统的算法树是一维问题的串行算法, 靠算增加算法树的深度来进行大型计算机计算, 并行算法减少时间上的复杂性, 计算量增加, 算法步骤减少, 把时间上的复杂性转化为空间上的复杂性。

并行算法分类, 并行算法根据运算对象不同分为数值并行算法和非数值并行算法两类, 数值并行算法有线性方程组和多项式求解等, 非数值并行算法指排序、 选择、 分类等设计。 并行进程执行顺序不同分为同步并行算法、 异步并行算法、 独立并行算法, 同步并行算法指进程执行要等待其他进程的计算方法, 异步并行算法指进程在执行的时候彼此不用相互等待, 独立并行算法指进程在执行的时候是独立执行的。

5 并行算法设计

用并行处理机系统进行并行计算求解问题一般遵守需要解决的问题本身提出满足需要的特定的并行算法, 或者在相似的问题上把已有的并行算法改变下, 来解决问题原则。 常用的并行算法技术有流水线技术、 分治策略和加速级连策略等。

流水线技术是重要的并行计算技术, 在VLSI并行算法中, 基本设计是把一个任务设置为A, 然后分成几个小的子任务A1、 A2、 …AN, 在执行的时候按顺序执行, 先执行A1再执行后面子任务, 计算速度是一样的。

分治策略就是把问题分解多个特征相同的子问题, 计算机单个结点平均分摊计算机的负载提高工作效率, 子问题的类型和原问题的类型一样, 采用分而治之的原则。

加速级连策略是采用最优算法来解决问题, 开始使用最优算法, 当任务规模缩小到一个值的时候, 使用最快非最优的方式接续完成任务解决问题, 使用最优串行算法并发解决子问题。

并行计算模型把并行机的基本抽象特征表现出来, 从计算模型中可以看出来并行计算模型、 并行算法设计、 并行机三者关系, 并行算法映射到并行机上, 基于并行机进行算法的设计。 计算机模型为并行算法提供了框架和物理基础, 使用多种并行机。 并行计算模型如图2 所示。

并行算法评价标准是加速比和效率, 并行算法在并行机上求解实际问题,

并行算法的加速比

TA串行算法在单处理机上最优运行时间

TB并行算法使用B台处理机的计算时间

并行算法的效率定义

B为处理机台数

在处理台数规模不变的特定情况下并行算法加速比SB和处理机台数B成正比, 也叫算法线性加速比, 如果SB比B多, 那么该算法是超线性加速比。

设计高性能计算机并行算法要充分考虑到并行算法的扩展性, 这也是再设计并行算法结构时要充分考虑到的问题, 扩展性有3 种分别是资源扩展、 技术扩展和应用扩展, 扩展性主要是并行算法在对处理机数目的有效利用的一个度量, 并不是算法内在的通信和并行性需求。

加速比、 效率和扩展性是评价并行算法性能的3 个指标, 加速比是最优串行算法运行时间和B太处理机并行运行时间的比值, 效率是加速比与B的比值, 我们在设计并行算法的时候要充分考虑到加速比、 效率和扩展性3 个指标。

6 结语

从理论和设计方法两方面对分布式并行算法进行了简单的描述, 随着计算机技术的发展, 人们对计算机的数据处理性能有很高的要求, 最初的计算机处理能力已经不能满足计算机领域的发展, 并行处理技术可以提高计算机大数据的并行处理性能, 从国内外并行算法的应用上分析出我国对并行处理能力要加大投入, 才能追上技术领先国家。 分布式并行算法提高计算机的数据处理能力, 在计算机技术领域发挥着重要的作用。 并行处理技术分硬件技术和软件技术, 目前硬件方面有很大的提高, 但是在软件方面还存在问题需要解决, 算法是软件的核心, 要推动并行处理技术的发展, 必须要先重点研究并行算法。

摘要：计算机计算方法从单机技术发展到多机并行技术, 这是计算机计算模式适应未来科技发展的趋势, 国家的科技发展需要并行处理技术的推动, 并行处理技术能快速地发展, 源动力来自于人们对工程计算机能力的需求。在这几年, 并行处理技术得到很大的推动与发展, 并行算法处理技术的应用提高了计算机大数据处理的能力。介绍并行算法应用情况的背景和研究现状, 阐述了并行算法技术的分类及设计方法。

关键词：分布式,并行算法,计算机计算方法

参考文献

[1]许林.群智能算法可并行性分析及其FPGA实现[J].journal6, 2010, 46 (33) :54-57.