对算法的一点认识.doc

对算法的一点认识
张青(江苏省苏州中学 215006)
“算法”一词最早来自公元9世纪波斯数学家比阿勒·霍瓦里松的一本影响深远的著作《代数对话录》。1936年,年仅24岁的英国数学家图灵提出了著名的图灵论点。这个论点主要体现在他的论文《论应用于决定问题的可计算数字》中。他提出思考实验原理计算机的概念。图灵把人在计算时所做的工作分解成简单的动作,与人的计算类似,机器需要:(1)存储器,用于储存计算结果;(2)一种语言,表示运算和数字;(3)扫描;(4)计算意向,即在计算过程中下一步做什么;(5)执行下一步结果。这样一来,他把人的工作机械化了,这台理想中的机器被我们后人称为图灵机。图灵的思想对算法的发展起到了重要作用。后来随着计算机的出现和迅速普及,算法这个词就被越来越广泛地应用。事实上,在关于计算机语言的每本教科书上都有对算法的不同陈述。比较普遍的说法是“算法是指完成一个任务所需要的具体步骤和方法的描述。”
算法和计算机科学紧密联系,而且也正是随着计算机的日益普及算法得到了普及。算法初步进入普通中学数学课标教材,正是算法日益普及的结果,这也说明算法已经成为提高国明素质或是素质教育的一个内容。算法是计算机处理信息的本质,因为计算机程序本质上就是一个算法,它告诉计算机按照确切的步骤来执行一个指定任务(如计算职工的薪水或打印学生的成绩单)。计算机科学中的
“算法”是指“在有限个步骤内求解某一问题所使用的一组定义明确的规则”,通俗点说就是计算机解题的过程。在这个过程中,无论是形式解题思路还是编写程序,都是在实施某种算法,前者是推理实现算法,后者是操作实现算法。由此可见一个算法应该具有以下5个特征:
1、有穷性。一个算法必须保证执行有限步后结束;
2、确切性。算法的每一步骤必须有确切定义;
3、输入。一个算法有0个或多个输入,以刻画运算对象的初始情况。所谓0个输入是指算法本身已经定了初始条件;
4、输出。一个算法有一个或多个输出,以反映对输入数据加工后的结果,没有输出的算法是毫无意义的;
5、可行性。算法原则上能够精确地运行,而且人们用纸笔做有限次运算后即可完成。
除了以上几个重要特征外,考虑到软件的复用和可移植性,现在还要求算法具有某种通用性。正因为如此,现在已经出现了许多典型的通用算法。如:分治法、线性法、贪心法、分支有限法、动态规划法、回溯法、随即算法、并行算法等。事实上,算法已经成为一门专门的科学。所以让学生早一点了解算法对我国计算机科学的腾飞或者说成为一个软件大国有百益而无一害。
最后,再谈一下设计算法的一个重要方面——分解。由于人脑对处理复杂问题的局限性,对于一个大而复杂的问题,想一下子彻底吃透是困难的,有时是不可能的,而较小的问题使人们容易理解,从而容易设计算法。因此分解成为设计复杂问题算法的最主要途径。为阐明这一点,我们作如下说明:
假设C(P)是度量一个问题P理解复杂性函数,E(P)是度量为解决问题P所需要的工作量的函数,则给定问