《计算与算法》PPT课件.ppt

第十九章 计算与算法,第一节 计算概述,数学的形成和发展都是与计算密切相关的。 什么是计算?所谓计算是指，根据已知数量通过数学方法求得未知数。 计算是一种重要的数学方法，任何一门科学所采用的定量分析都离不开计算。 计算是一种科学方法。传统的科学方法一般是指科学实验和逻辑演绎，现在认为计算是第三种科学方法。 在科学研究的历史上，计算曾经作为科学实验和逻辑演绎的附属或补充而存在。,【例】人们对圆周率的研究，计算在其中是一种具体的求解方法，是演绎能力的一种体现。 计算作为一种相对独立的方法出现在科学研究之中。天文学家发现海王星就是一个典型的实例，其方法成为一种典型的科学方法。 【例】人们观测到天王星运动的不规则特征，推测这是天王星之外还有其他行星的影响结果，但当时的观测水平很难直接观测到。勒维叶在巴黎，亚当斯在剑桥，他们相互独立地为这颗未知行星的定位计算多年，1846年9月，勒维叶把他的计算结果通知柏林的同行，这位同行在勒维叶计算出的位置观测到了海王星。,用同样的方法，天文学家在1930年又发现了冥王星。 所谓计算就是按照一定的已确定的规则。由初始对象(也叫数据)经过一系列的运算(有限次)得到一定的新结果的一个过程。 计算是严格意义下进行的，即对于每种初始对象只能得到唯一确定的计算结果。,第二节 算法概述,什么是算法?某问题的一个算法即解决该问题的一个确定的、有限次的操作步骤。 【例】数的四则运算法则、一元二二次方程的求根公式、求最大公约数的欧几里得方法、解线性方程组的高斯消元法等，都是典型的算法，它们给出问题的精确解； 而求数值积分的牛顿公式、解代数方程的迭代法等也是典型的算法，它们给出的是问题满足一定要求的近似解。,中国古代数学以算法为主要特征。 我国传统数学在从问题出发以解决问题为主旨的发展过程中，建立了以构造性与机械化为其特色的算法体系，这与西方数学以欧几里得几何原本为代表的所谓公理化演绎体系正好遥遥相对。 所谓机械化，无非是刻板化和规格化。 数学问题的机械化，就是要求在运算或证明过程中，每前进一步之后，都有一个确定的、必须选择的下一步，这样沿着一条有规律的、刻板的道路，一直达到结论。,使用一种机械化方法证明一类定理，才真正体现了机械化定理证明。1977年，中国著名数学家吴文俊给出了初等几何一类主要定理的机械化证明方法“吴方法”。为此，2006年，吴文俊荣获邵逸夫数学科学奖。 肇始于我国的这种机械化体系，在经过明代以来几百年的相对消沉后，由于计算机的出现，已越来越为数学家所认识与重视，势将重新登上历史舞台。,算法的思想，不仅仅用于上面所举的数学问题的解决，很多实际问题的解决都可以归结为某种算法的提出。 【例】有一队士兵要过河，但只有一条小船，上面有两个小孩。小船至多可以载一个士兵或者两个小孩，请问这队士兵依照何种 程序才能渡过此河? 【解】一个步骤包含4个过程：2小孩过河1小孩返回1士兵过河1小孩返回。此一步骤的结果是1士兵过河。重复该步骤即可使全部士兵过河。,任何解决问题的有效方法，其过程都是能够确切描述的，其操作步骤也是有限的。从这点意义上讲，算法的应用已经远远超出数学的范围。 又如大家所熟悉的消元法解二元一次方程组。 由此可见，算法就是按照一定的规则所组成的的一个过程。一种算法解决一类问题，它按照一定的步骤按部就班进行计算，最终得到问题的解决。,第三节 算法特点,算法具有下列特点。 有限性。 一个算法必须在有限步之内终止。如果不能在有限步内完成，只能得到一个近似的值。 【例】求x2=2的近似值。 【解】由x2=2得x=2/x，于是，定义数列 xn为xn+1=xn+2/xn/2 (n=1,2,3,)， 易见，在确定x1之后，xn也就确定了：,如确定x1=1，即有： x2=x1+2/x1/2=1+2/1/2=1.5， x3=x2+2/x2/2=1.5+2/1.5/2=1.41666 1.416666667， x4=x3+2/x3/2=1.416666667+2/1.416666667/21.4142186163， 当达到所要求的精确度后，就得到方程X2=2的近似解。 这样的算法，称为迭代法。,确定性。 算法的每一步都有精确的定义。 【例】用程序框图表述如下问题的求解过程：在l500中，找出能同时满足用3除余2，用5除余3，用7除余2的所有正整数。 【解】给出算法： 给出初始值I=9(满足用7除余2的最小正整数数)； 判断I的值是否小于或等于500， 若是，则进入下一步判断：I是否满足三个条件，若满足则输出I，不满足则进入再下一步， 若不是，进入再下一步：I递增l。 返回第步，直至I大于500而结束。,画出程序框图如下:,由此可见，算法的指令要明确，每个人都能理解，不应包含可以任意解释的内容。 算法一经确定，要求的是严格的执行。它的每一个步骤都单值地决定了它的下一个步骤。 有效性。 如果使用一个算法从它的初始数据出发，能够得到这一问题的正确解，那么这个算法就是有效的；否则这个算法就是无效的。,【例】某工厂生产一种玩具的成本为lO元，若以x元价格出售，每天可以卖掉50-x只，该厂应如何定价才能获得最大利润? 【解】设利润y,由题意得y与x的函数关系为 y=(x-10)(50-x)，利润=售价销量-成本 化简得 y=-x2+60x-500 对y求导得 y=-2x+60 令其为零，得 x=30 所以，当价格x=30时，利润最大。 (当然，也可以用二次曲线的顶点理论求解。) 显然，这个结果是厂家所希望的，而且是可以实现的。,第四节 算法举例,【例】一个班上有50名学生，现在要按照姓名的拼音顺序排成一张表。 一个最笨的算法是将50个学生所有可能排列的表都打出来，然后从中挑选一张符合拼音顺序的表。要知道，50个人的不同排列有501种，即这样的表有501张。 这个数目之大，用每秒100万次的计算机不停地运算需要上万个世纪，显然是不能实施的。 采用以下常用的算法来排。 随便拿一位同学的名字排在第一位。任取第二位同学的名字先放在第一位，然后依拼音顺序和第一位的名字比较一次，放在适当位置。,第三位则需要和前两位的名字比较至多两次。依次类推; 第k位至多要比较k一1次，第50位至多需要比较49次。 这样，只要比较1+2+49=49502=1225次，就完成了排序。 如果班上有n个学生，第一种算法需要运算n!次(当n25，n!10n); 第二种算法至多需要(n-1)n2次。前者的次数随n的增加，按超10n的指数方式增加，后者则只按n的二次多项式的方式增加。,【例】(验血问题)某次大战前夕，10万大军将在三天后出征。军医突然发现有一个士兵带入了一种传染病菌，三天后发作将会迅速传染全军，使10万大军 丧失战斗力，只有通过验血才能查明谁是患者。当时军医每天最多能检验血样100份，如果逐一验血，至少需要1000天，这将延误战机。 将军求教专家，一位数学家提出一种方案，终于顺利地解决了这个问题。 一般地说，如果全军共有x人，用m表示对m取上整（取大于m的最小整数），则对全军逐一检验需x/100,而采用数学家分群检验的方法需要的天数只是log100x=(log10x)