算法的概念 精.ppt

算法的概念 课件第1页，本讲稿共18页一.算法的基本概念1 什么是算法 算法（algorithm）一词源于算术(algorism),算术方法的原义是一个由已知推求未知的运算过程。后来，人们把它推广到一般,指算法是在有限步骤内求解某一问题所使用的一组定义明确的规则,甚至把把进行某一工作的方法和步骤也称为算法。第2页，本讲稿共18页例如，人们在计算过程中，先乘除，后加减，从内到外去括号等规则，都是按部就班必须遵守的算法。人类最早关于算法的记录存在于在两河流域发现的公元前两三千年的泥板书上，其中的一个典型例子就是计算利息何时能够够等于本金。算法早期发展中值得一提的另一个成果应归功于古希腊的欧几里得，他提出的计算最大公约数的辗转相除法（又称欧几里得算法）至今仍在使用。第3页，本讲稿共18页欧几里得是古代最有名望的学者之一，古希腊数学家，几何学的鼻祖。公元前300年左右，他所著几何原本13卷，是世界上最早公理化的数学著作。在几何原本中他充分总结了前人的生产经验和研究成果，从公理和公设出发，运用演绎法，经过逻辑推理和数学运算，创立了著名的欧几里得（简称欧氏几何）。在几何原本中，欧几里得还阐述了关于求两个整数的最大公约数的过程，这就是著名的欧几里得算法辗转相除法，其具体过程如下：第4页，本讲稿共18页设给定的两个正整数为m和n，求它们的最大公约数的步骤为：（1）以m除以n，令所得的余数为r（r必小于n）；（2）若r0，则输出结果n，算法结束；否则，继续步骤（3)（3）令m=n，n=r,并返回步骤（1）继续进行。第5页，本讲稿共18页中国古代数学研究中也有许多有关算法的成果。用我国传统的开方术求高次方程的近似根，是算法上的一大成就。此外,在社会上得到广泛使用的珠算口诀就可以看做是典型的算法,它把复杂的计算(例如除法)描述为一系列按口诀执行的简单的算珠拨动操作。中国古代数学以算法为主要特征，其中最具代表性的就是九章算术。第6页，本讲稿共18页九章算术是战国、秦、汉时期数学发展的总结，就其数学成就来说，堪称是世界数学名著。其内容按类分章，以数学问题的形式出现，包括分数四则运算、开平方与开立方（包括二次方程数值解法）、盈不足术、各种面积和体积公式、线性方程组解法、正负数运算的加减法则、勾股形解法（特别是勾股定理和求勾股数的方法）等。其中方程组解法和正负数加减法则在世界数学发展上是遥遥领先的。就其特点来说，它形成了一个以筹算为中心，与古希腊数学完全不同的独立体系。第7页，本讲稿共18页在1114世纪约300年期间著名的数学家的著作中，如贾宪的黄帝九章算法细草，刘益的议古根源，秦九昭的数书九章，李治的测圆海镜和益古演段，杨辉的详解九章算法、日用算法和 杨辉算法中，算法的特点得到了进一步的强化和发展（其中包括发展了一套求高次方程近似根的方法。第8页，本讲稿共18页2。算法的一般特征。算法的一般特征 算法实际上是一种抽象的解题方法，它具算法实际上是一种抽象的解题方法，它具有动态性。因此，算法的行为非常重要。作为一个有动态性。因此，算法的行为非常重要。作为一个算法，应具有以下四个特征。算法，应具有以下四个特征。1）能行性）能行性(effectiveness）算法的能行性包括两个方面：一是算法中的每一算法的能行性包括两个方面：一是算法中的每一个步骤必须是能实现的。例如，在算法中，不允许出现个步骤必须是能实现的。例如，在算法中，不允许出现分母为零的情况；在实数范围内不能求一个负数的平方分母为零的情况；在实数范围内不能求一个负数的平方根等。二是算法执行的结果要能达到预期的目的。通常，根等。二是算法执行的结果要能达到预期的目的。通常，针对实际问题设计的算法，人们总是希望能够得到满意针对实际问题设计的算法，人们总是希望能够得到满意的结果。的结果。第9页，本讲稿共18页（2 2）确定性）确定性(definiteness(definiteness）算法的确定性，是指算法中的每一个步骤都必须是有明确算法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。这一特定义的，不允许有模棱两可的解释，也不允许有多义性。这一特征也反映了算法与数学公式的明显差异。在解决实际问题时，可征也反映了算法与数学公式的明显差异。在解决实际问题时，可能会出现这样的情况：针对某种特特殊问题，数学公式是正确的，能会出现这样的情况：针对某种特特殊问题，数学公式是正确的，但按此数学公式设计的计算过程可能会使计算机系统无所适从，但按此数学公式设计的计算过程可能会使计算机系统无所适从，这是因为，根据数学公式设计的计算过程只考虑了正常使用的情这是因为，根据数学公式设计的计算过程只考虑了正常使用的情况，而当出现异常情况时，该计算过程就不能适应了况，而当出现异常情况时，该计算过程就不能适应了。第10页，本讲稿共18页例如，某计算工具规定：大于例如，某计算工具规定：大于100的数认为是比的数认为是比1大很多，而小于大很多，而小于10的数不能认为是比的数不能认为是比1大很多；且大很多；且在正常情况下出现的数或是大于在正常情况下出现的数或是大于100,或是小于或是小于10.但指令但指令“输入一个输入一个X，若，若x比比1大很多，则输出数字大很多，则输出数字1，否则输出数字，否则输出数字0”是不确定的。这是因为，在正常是不确定的。这是因为，在正常的输入情况下，这一指令的执行可以得到正确的结的输入情况下，这一指令的执行可以得到正确的结果，但在异常情况下（输入的果，但在异常情况下（输入的x在在10与与100之间），之间），这一指令执行的结果就不确定了这一指令执行的结果就不确定了 第11页，本讲稿共18页例如，某计算工具具有七位有效数字（如FORTRAN中的单精度运算）,在计算下列三个量 A ，B1，C 的和时，如果采用不同的运算顺序，就会得到不同的结果，即 ABC=1 =0 AC十B=1=1 而在数学上，A+B+C与A+C+B是完全等价的。这可知，算法和计算公式是有差别的。第12页，本讲稿共18页3）有穷性）有穷性(finiteness）算法的有穷性是指算法必须能在有限的时间算法的有穷性是指算法必须能在有限的时间内执行完，即算法必须能在执行有限个步骤之后内执行完，即算法必须能在执行有限个步骤之后终止。数学中的无穷级数，在实际计算时只能取终止。数学中的无穷级数，在实际计算时只能取有限项，即计算无穷级数的过程只能是有穷的。有限项，即计算无穷级数的过程只能是有穷的。因此，一个数的无穷级数的表示只是一种计算公因此，一个数的无穷级数的表示只是一种计算公式，而根据精度要求确定的计算过程才是有穷的式，而根据精度要求确定的计算过程才是有穷的算法。算法。第13页，本讲稿共18页算法的有穷性还应包括合理的执行时间的含义。如果一个算法的执行时间是有穷的，但却需要执行千万年显然这就失去了算法的实用价值。例如，克莱姆(Cramer)规则是求解线性代数方程组的一种数学方法，但不能以此为算法，这是因为，虽然总可以根据克莱姆规则设计出一个计算过程用于计算所有可能出现的行列式，但这样的计算过程所需的时间实际上是不能容忍的。第14页，本讲稿共18页还例如，从理论上讲，总可以写出一个正确的弈棋程序，而且这还例如，从理论上讲，总可以写出一个正确的弈棋程序，而且这也并不是一件很困难的工作。由于在一个棋盘上安排棋子的方式也并不是一件很困难的工作。由于在一个棋盘上安排棋子的方式总是有限的，而且，根据一定的规则在有限次移动棋子之后比总是有限的，而且，根据一定的规则在有限次移动棋子之后比赛一定结束。因此弈棋程序可以考虑计算机每一次可能的移动，赛一定结束。因此弈棋程序可以考虑计算机每一次可能的移动，它的对手每一次可能的应答，以及计算机对这些移动的可能应答它的对手每一次可能的应答，以及计算机对这些移动的可能应答等等，直到每个可能的移动停止下来为止。此外，由于计算机可等等，直到每个可能的移动停止下来为止。此外，由于计算机可以知道每次移动的结果，因此总可以选择一种最好的移动方式。以知道每次移动的结果，因此总可以选择一种最好的移动方式。但即使如此，这种弈棋程序还是不可能执行，因为所有这些可能但即使如此，这种弈棋程序还是不可能执行，因为所有这些可能移动的次数太多，所要花费的时间不能容忍。由上述两个例子可移动的次数太多，所要花费的时间不能容忍。由上述两个例子可以看出，虽然许多计算过程是有限的但仍有可能无实用价值。以看出，虽然许多计算过程是有限的但仍有可能无实用价值。第15页，本讲稿共18页（4）算法必须拥有足够的情报）算法必须拥有足够的情报 一个算法是否有效，还取决于为算法的执行所提供一个算法是否有效，还取决于为算法的执行所提供的情报是否足够。例如，对于指令的情报是否足够。例如，对于指令“如果小明是学生，则如果小明是学生，则输出字母输出字母Y，否则输出，否则输出N”。当算法执行过程中提供了小。当算法执行过程中提供了小明一定不是学生的某种信息时，执行的结果将输出字母明一定不是学生的某种信息时，执行的结果将输出字母N；当提供的只是部分学生的名单，且小明恰在此名单；当提供的只是部分学生的名单，且小明恰在此名单之中，则执行的结果将输出字母之中，则执行的结果将输出字母Y。但如果在提供的部分。但如果在提供的部分学生的名单中找不到小明的名字则在执行该指令时无学生的名单中找不到小明的名字则在执行该指令时无法确定小明是否是学生。法确定小明是否是学生。第16页，本讲稿共18页通常，算法中的各种运算总是要施加到各个运算对通常，算法中的各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态象上，而这些运算对象又可能具有某种初始状态这是算法执行的起点或是依据。因此，一个算法执这是算法执行的起点或是依据。因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。如果输入不够或输入错误，将会有不同的结果输出。如果输入不够或输入错误，则算法本身也就无法执行或执行有错。一般来说，则算法本身也就无法执行或执行有错。一般来说，只有当算法拥有足够的情报时，该算法才是有效的；只有当算法拥有足够的情报时，该算法才是有效的；而如果提供的情报不够，则算法并不是有效的。而如果提供的情报不够，则算法并不是有效的。第17页，本讲稿共18页综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的且是明确的，此顺序将在有限的次数下终止 第18页，本讲稿共18页