谈谈算法的历史进程.doc

谈谈算法的历史进程?22?重庆数学教学通讯)2005年3月(上半月)(总第220期)谈谈算法的历史进程(广州大学理学院数学系510405)王小燕本文追溯了中西方数学中算法的历史渊源,按照历史发展的进程论述了计算机带给我们的算法思想,以及对今天反映到数学教育中的新课标下的算法做了一些思考.1什么是算法提到算法,人们总感觉是计算机专业应该掌握的内容,其实随着信息技术的飞速发展,算法的观念在当今已经渗透到宇宙学,物理学,生物学乃至经济学和社会科学等诸多领域,而且它在科学技术和社会发展中发挥的作用也越来越大.那么究竟什么是算法呢?算法是在有限步骤内求解某一问题所使用的一组定义明确的规则.通俗来说,就是通过计算来解决问题的过程,在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法.不同的是,前者是推理实现的算法,后者是操作实现的算法.算法有5个重要的特征:(1)有穷性:一个算法必须保证执行有限步之后结束;(2)确切性:算法的每一步骤必须有确切的定义;(3)输人:一个算法有0个或多个输人,以刻画运算对象的初始情况;(4)输出:一个算法有一个或多个输出,以反映对输人数据加工后的结果.没有输出的算法是毫无意义的;(5)可行性:算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即可完成.算法的这些特征以及它在社会生活中所发挥的作用也日益影响并渗透到数学教育领域,当前普通高中数学课程标准3中明确提出算法的内容和要求,目的是让学生体会算法的基本思想以及它的重要性和有效性.而算法思想早在古代的许多着作中就有所体现.因此我们有必要追溯一下它的历史进程,这对于我们更好地体会算法思想并从中汲取精华,推陈出新有很大的帮助.2西方算法的历史渊源Algorithm(算法)一词的最早形式是Algorism(算术),指的是用阿拉伯数字进行算术运算的过程.它最早来源于9世纪波斯数学家阿布?雅发?穆罕默德?依伯恩?缪莎?阿勒?霍瓦里松的名字AJafarMohammeditrnM口alKhowarizm(约公元前825年).一本早期的德文数学词典VollstandigesMathematischesLexicon(数学大全辞典),给出了Algorithmus(算法)一词的如下定义:在这个名称之下,组合了四种类型的算术计算的概念,即加法,乘法,减法,除法.拉丁短语algorithmushinfinitesimalis(无限小方法),在当时就用来表示Leibnitz(莱布尼兹)所发明的以无限小量进行计算的微积分方法.在算法这个词被提出之前,人们早就知道了有关算法的实例,如现在被称作欧几里德算法的找两个数最大公约数的步骤是在古希腊(公元前300年左右)便有记载的一个最熟知的例子.直到20世纪30年代以前算法还只是一数学教学通讯)2005年3月(上半月)(总第220期)重庆?23?个直观的概念,人们直观上理解的算法就是在有限的时间内,可以根据明确规定的运算规则,在有穷步骤内得出确切计算结果的机械步骤或可计算程序.1928年希尔伯特在波伦亚国际数学家大会上提出一个具有挑战性的判定问题:是否存在一般的能在原则上一个接一个地解决所有(属于某种适当定义的类的)数学问题的机械步骤?这里的机械步骤实际上就是算法和可计算程序的直观概念.1936年英国数学家图灵(ATuring)通过引进图灵机概念,给出算法概念严格的数学表达,并指出算法可计算函数即用图灵机可计算的函数.3中国古代数学中的算法众所周知,中国古代数学渊源于生活,贴近实际,实用性强,形成了以算为主,使用算器的一套算法体系.虽然在中国古代数学典籍中算法一词并未被明确地提出,但是它要求在运算或证明过程中,每前进一步之后,都有一个确定的,必须选择的下一步,这样沿着一条有规律的刻板道路一直达到结论,这是中国着名数学家吴文俊教授对中国古代数学的发展路线所傲的表述.从中可以看出,中国古代数学实际上是循着一条算法构造的路线而发展的,并且在算法构造以前的发展阶段,已经孕育了构造算法的基本思想即程序思想,这与现今所提到的计算机程序设计中的算法不无相似之处.中国古代许多数学典籍中都蕴含了丰富的算法思想,如数术记遗中就记载了中国古代l4种算法.这些算法虽然是各种形变了的计数法,但却充分体现了古代数学的程序思想.时至今日,这14种算法已经引起了许多国内外数学家的关注,如日本数学家三上义夫首先对它给予了介绍和解释.中国着名数学家许莼舫先生在他的中国算术故事中,也给予了简要介绍.具体来说,这14种算法分别是:积算,太一算,两仪算,三才算,五行算,八卦算,九官算,运筹算,了知算,成数算,把头算,龟算,珠算和计算.其中太一算法包含了程序设计的并行原则,同时也隐含了某种程序设计的搜索原则.这一计数法则十分便于四则运算法则的算法构造,这些都在后来的珠算盘上实现了;两仪算作为太一算法的变形,体现了程序的选择设计思想,这种被称为选取型程序结构的设计思想在今天的程序设计中被广为采用;而五行算法的过程则体现了程序的搜索原则.另外八卦和九宫数的记法,均被后人接受;而珠算之法便是导致后来一场计算工具革命的思想源头.九章算术及刘徽的九章算术注开创了中国传统数学构造性和机械化的算法模式,之后这种机械化思想一直贯穿于中国传统数学中2.如贾宪三角(-项式定理系数表)与增乘开方法(即其后欧洲所讲的霍纳法),.秦九韶程序(高次方程数值解法),大衍求一术和大衍总数术(一次同余组解法),天元术和四元术(高次方程组的解法)等都是中国古代数学中的算法,其算法思想对我们今天数学问题的解决都有极大的启发作用.4计算机带给数学的算法化近代计算机的出现,使得各种各样的算法的实现成为可能,也给数学的发展带来无限生机.我们知道,算法是2O世纪3O年代哥德尔,丘奇,克林尼,图灵等数学家对于直观的算法可计算概念的严格的数学刻画,而正是由于算法和图灵机概念的引进,哥德尔不完全性定理有了图灵机语境下的版本.而且通过建立在算法概念上的可计算性理论,人们很快证明了一系列数学命题的不可判定性和一系列数学问题的算法不可解性,这在一定程度上推动了数学的发展.而今,计算机科学被认为是算法的?24?重庆数学教学通讯2005年3月(I-半月)(总第220期)科学,以算法为核心的机械化思想将为信息时代数学科学的创新发挥重大作用.事实上,一些数学分支正是由于踏上了机械化的道路而获得了蓬勃的发展,使之成为重要的研究方向,甚至成为数学的主流.另外随着数学和计算机技术的进展,一些认知科学家,人工智能专家和哲学家认为从物理世界,生命过程到人类心智都是算法可计算的,甚至整个宇宙也完全是由算法支配的.鉴于此观点有人提出了质疑,并借以充分的论据给予了反驳.尽管如此,我们从中还是可以看到算法在当今各个研究领域包括数学领域中所发挥的作用以及人们对它的重视程度.时代在发展,技术在不断的进步,相信算法思想将对科学的发展产生不可估量的作用.5新课标下的算法由于算法恩想的重要程度日趋显着,这给我们的数学教育也提出了新的要求.新一轮数学课程改革对算法的内容和要求给出了明确的标准:5.1算法的含义,程序框图通过对具体问题过程与步骤的分析,体会算法的思想,了解算法的含义:通过模仿,操作,探索,经历通过设计程序框图表达解决问题的过程;在具体问题的解决过程中理解程序框图的三种基本逻辑结构:顺序,条件分支,循环.5.2基本算法语句经历将具体问题的程序框图转化为程序语句的过程,理解几种基本算法语句输入语句,输出语句,条件语句,循环语句,进一步体会算法的基本思想.5.3通过阅读中国古代数学中的算法案例,体会中国古代数学对数学发展的贡献标准中还指出:本模块的算法内容是将数学中的算法和计算机技术建立联系,形式化地表示算法.在条刊:允许的学校,使其能在计算机上实现.为了有条理地,清晰地表达算法,往往需要将解决问题的过程整理成程序框图:为了能在计算机上实现,还需要将自然语言或程序框图翻译成计算机语言.总而言之,主要目的是使学生体会算法的思想,提高逻辑思维能力.这就要求教师在平时的教学中要结合案例的分析,通过模仿,探索,设计,操作把算法思想渗透和贯穿于其中,使学生能够依据问题的分析形成算法,编制程序,用计算机解决问题.进而培养学生的逻辑思维能力,并解决生活中的问题,而这正是信息技术教育所要实现和达到的目标.纵上所述,算法从其孕育到产生,发展到今天,虽然经历了很长一段时间,但它的重要性却日趋突显;而算法思想对推动科学的发展所起的作用也为越来越多的有识之士达成共识.因此具备算法思想和信息技术素养将是未来社会对公民的基本要求,这就需要我们认真地来理解和思考新课标下的算法,并将算法思想有效地渗透和贯穿到数学教学中.参考文献1陈开先.数述记遗.之古算十四法的程序意义解读?自然辨证法研究,2003(4)2刘智强.新课标下算法的理解和思考.数学通讯,2003(21)3普通高中数学课程标准(实验).北京:人民