第六讲算法.doc

第六讲 算法 一、算法概述 算法，一个既陌生又熟悉的名词。说陌生，因为算法概念从未进入我国中学数学教学大纲。新的高中数学课程标准破天荒地把算法作为重要内容列入必修课，自然出乎人们的意料。说到熟悉，那是因为从小学就开始接触算法。例如做四则运算要先乘除后加减，从里往外脱括弧，竖式笔算等等都是算法，只要按照一定的程序一步一步做，一定不会错。至于乘法口诀、珠算口诀更是算法的具体体现。因此，算法其实是耳熟能详的数学对象。一般地，算法是指在解决问题时按照某种机械程序步骤一定可以得到结果的处理过程。这种程序必须是确定的、有效的、有限的。中国古代数学以算法为主要特征。吴文俊指出：我国传统数学在从问题出发以解决问题为主旨的发展过程中，建立了以构造性与机械化为其特色的算法体系，这与西方数学以欧几里得《几何原本》为代表的所谓公理化演绎体系正好遥遥相对。肇始于我国的这种机械化体系，在经过明代以来几百年的相对消沉后，由于计算机的出现，已越来越为数学家所认识与重视，势将重新登上历史舞台。吴文俊创立的几何定理的机器证明方法（世称吴方法），用现代的算法理论，焕发了中国古代数学的算法传统，享有很高的国际声誉。他因此于2001年获得了第一届国家最高科学技术奖。20世纪上半叶，科学研究方式归结为两种方式：理论+实验。后来由于计算机技术能力的开发，计算成为第三种重要手段。未来的趋势是，理论+实验+计算将成为标准的科学研究方法。那么，计算机如何按照人的意愿进行计算呢？这就要靠算法。因此，毫不夸张地说，算法既是数学科学的重要基础，也是计算机科学的核心。在我国，1980年的《辞海》还没有收入“算法”，只有“算法论”的条目（那是“数理逻辑”学科的一个分支，相当专）。1988年出版的《中国大百科全书（数学卷）》，才有了莫绍揆先生撰稿的“算法”辞条。Algorithms（算法）一词的如下定义：“在这个名称之下，组合了四种类型的算术计算的概念，即加法、乘法、减法、除法。”笼统地讲，算法是解决一个问题而采取地方法和步骤。 “算法”是一个与数的计算密切相关的概念。古代就有许多有名的算法，如古埃及乘法、求解某些二次方程的巴比伦方法、求两个自然数最大公约数的欧几里得算法等等。就整个数学发展的历史进程而言，不同时期、不同地域的数学一直存在两种不同的倾向：一种是逻辑演绎倾向；另一种是机械化算法倾向。前者以古希腊欧几里得《几何原本》为代表，后者则以中国古代数学名著《九章算术》为代表。《九章算术》采用应用问题的形式，共收录了246个问题，每个问题都包括“问”、“答”、“术”，经数学家刘徽作注后增加了“注”，共4部分。“问”是先提出问题，“答”则给出答案，再给出“术”，作为一类问题的共同解法，以后就可以利用“术”来解决其它同类问题。“术”是《九章算术》的核心内容，实际上就是一类问题的一种算法，这是中国古代数学的一大特征。“ 数值算法举例：求 步骤1：使 步骤2：使，得到的积仍放在中； 步骤3：使的值加1 步骤4：如果，返回重新执行第2步；如果，则不再返回步骤2，而停止循环，此时中的值就是。 非数值算法举例：201电话卡的使用步骤 步骤1：拿起话筒，在201机上拨通“201”； 步骤2：听到提示语言，按“1”或“2”，选择语言种类； 步骤3：拨卡号、密码； 步骤4：拨所需号码； 步骤5：有人接则通话，无人接可在等一会儿，仍无人接说明要找的人不在； 步骤6：放下话筒； 步骤7：结束。 在数学发展史上，算法数学与演绎数学相辅相成，彼此消长，不断推进着数学的发展。算法数学也促进了数学分支的诞生和发展，16世纪以后，符号代数、十进小数、对数计算、解析几何、微积分的诞生都与算法数学紧密相关，尤其是微积分的出现，并不是靠严格的演绎理论，而是以实际应用为动力，计算为手段才得以迅速发展，成为人类数学史上新的高峰。可以说，数学诞生于实际问题的计算，算法是计算数学的核心，它是十分古老的分支。随着电子计算机问世，现代计算数学得到迅猛发展，成为数学科学中与生产实际和科学实践联系最直接的部分。 “算法”在数学学科及计算机科学的发展中，发挥越来越重要的作用，并日益融入社会生活的诸多方面。随着电子计算机的出现及普及，算法化、程序化的思想与方法也已经渗透到商业、交通、国防、科技甚至教育等许多领域。如果在现代数学研究与应用以及数学的未来发展中挖掘这种十分重要而深刻的思想，在数学教育中逐步渗透这种思想与方法，会为学生适应社会发展的需要打下坚固的基础，算法思想也成为现代公民应具备的一种数学素养，算法已开始成为普通高中课程的组成部分。 算法具有以下五个重要特征： ⑴有穷性。一个算法必须保证执行有限步之后结束，且每一步都可在有限时间内完成。 ⑵确定性。算法的每一步都应该是明确无误的，不能含义模糊，也不能产生二义性。 ⑶可行性。一个算法是可