计算机科学与技术方法论ch04

第4章计算学科中的核心概念4.1算法算法的历史简介公元825年，阿拉伯数学家阿科瓦里茨米（AlKhowarizmi）写了著名的《波斯教科书》（PersianTextbook），书中概括了进行四则算术运算的法则。“算法”（Algorithm）一词就来源于这位数学家的名字。后来，《韦氏新世界词典》将其定义为“解某种问题的任何专门的方法”。而据考古学家发现，古巴比伦人在求解代数方程时，就已经采用了“算法”的思想。丢番图方程的可解性问题古希腊数学家丢番图（Diophantus）：代数学之父在《算术》（Arithmetica）一书中提出了有关两个或多个变量整数系数方程的有理数解问题。对于具有整数系数的不定方程，如果只考虑其整数解，这类方程就叫做丢番图方程。“丢番图方程可解性问题”的实质为：能否写出一个可以判定任意丢番图方程是否可解的算法？一个未知数的线性丢番图方程的解ax=b，只要a能整除b，就可判定其有整数解，该整数解即b/a。两个未知数的线性丢番图方程的解ax+by=c，先求出a和b的最大公因子d，若d能整除c，则该方程有解（整数解）。问：方程13x+26y=52有无整数解？答：13和26的最大公因子是13，13又可整除52，故该方程有整数解（如x=2，y=1即方程的解）。例4.2问：方程2x+4y=15有无整数解？答：2和4的最大公因子是2，2不能整除15，故该方程无整数解。两个未知数的线性丢番图方程的解：欧几里德算法给定两个正整数m和n，求它们的最大公因子，即能同时整除m和n的最大正整数。步骤如下：（1）以n除m，并令所得余数为r（r必小于n）；（2）若r=0，算法结束，输出结果n；否则，继续步骤（3）；（3）将n置换为m，r置换为n，并返回步骤（1）继续进行。例4.3设m=56，n=32，求m、n的最大公因子算法如下:（1）32除56余数为24；（2）24除32余数为8；（3）8除24余数为0，算法结束，输出结果8。答：m、n的最大公因子为8。欧几里德算法既表述了一个数的求解过程，又表述了一个判定过程，该过程可以判定“m和n是互质的”（即除1以外，m和n没有公因子）这个命题的真假。算法算法的定义和特征1．算法的非形式化定义一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型问题的运算序列。2．算法的重要特性有穷性：一个算法在执行有穷步之后必须结束。确定性：算法的每一个步骤必须要确切地定义。即算法中所有有待执行的动作必须严格而不含混地进行规定，不能有歧义性。输入：算法有零个或多个的输入，即在算法开始之前，对算法最初给出的量。输出：算法有一个或多个的输出，即与输入有某个特定关系的量，简单地说就是算法的最终结果。能行性：算法中有待执行的运算和操作必须是相当基本的，3．算法的形式化定义算法是一个四元组，即（Q，I，Ω，F）。其中：（1）Q是一个包含子集I和Ω的集合，它表示计算的状态；（2）I表示计算的输入集合；（3）Ω表示计算的输出集合；（4）F表示计算的规则，它是一个由Q到它自身的函数，且具有自反性，即对于任何一个元素q∈Q，有F(q)=q。算法算法实例例4.4求1+2+3+……+100设变量X表示加数，Y表示被加数，用自然语言将算法描述如下：（1）将1赋值给X；（2）将2赋值给Y；（3）将X与Y相加，结果存放在X中；（4）将Y加1，结果存放在Y中；（5）若Y小于或等于100，转到步骤（3）继续执行；否则，算法结束，结果为X。例4.5求解调和级数设变量X表示累加和，变量I表示循环的次数，自然语言描述算法如下：（1）将0赋值给X；（2）将1赋值给I；（3）将X与1/I相加，然后把结果存入X；（4）将I加1；（5）若I大于等于N，算法结束，结果为X；否则转到步骤（3）继续执行。nHn1312111例4.6求解斐波那契数0，1，1，2，3，5，8，13，21，34，…（1）来源于1202年意大利数学家斐波那契（L.P.Fibonacci）在其《珠算之书》（LiberAbaci）中提出的一个“兔子问题”：假设一对刚出生的兔子一个月后就能长大，再过一个月就能生下一对兔子，并且此后每个月都能生一对兔子，且新生的兔子在第二个月后也是每个月生一对兔子。问：一对兔子一年内可繁殖成多少对兔子？在序列（1）中，每个数都是它的前两个数之和，Fn表示这个序列的第n个数，该序列可以形式化的定义为：F0=0，F1=1，Fn+2=Fn+1+Fn，n≥0斐波那契数列还是一个关于加法算法的典型实例。设变量X表示前一个数的值，即定义中的Fn，变量Y表示当前数的值，即定义中的Fn+1，变量Z表示后一个数的值，即定义中的Fn+2。那么求解问题的自然语言描述如下：（1）如果=0，那么将0赋值给Y，并输出Y，转步骤（11）继续执行；（2）将0赋给X，将1赋值给Y；（3）输出X、Y；（4）将1赋值给I；（5）如果I大于-1，则转到步骤（11），否则继续执行；（6）将X和Y的和赋值给Z；（7）将Y赋值给X；（8）将Z赋值给Y；（9）将Y输出；（10）将I加1，转步骤（5）继续执行；（11）算法结束。算法算法的表示方法原语一个算法的表达需要使用一些语言形式自然语言“Visitinggrandchildrencanbenerve-racking”,可能即意味着孙子孙女导致了很多问题，也表示去看他们可能会有问题图形语言：很少人能够根据折纸图给出的步骤成功地叠出一只鸟来，但一个专门学习过折纸的学生可以轻松完成当用来描述算法的语言并没有被准确定义或者没有给予足够信息的时候，交流就会产生问题原语通过建立一个可以描述算法的意义明确的基本块（原语）集合，计算机科学即就可以解决上述的勾通问题原语描述算法需要建立一个统一的细节描述级别，原语连同一组表达了原语如何表达复杂的想法的规定组成了一种程序设计语言组成语法：原语的符号表示语义：表达了原语的意义1．自然语言缺点由于自然语言的歧义性，容易导致算法执行的不确定性；自然语言的语句一般太长，从而导致了用自然语言描述的算法太长；由于自然语言表示的串行性，因此，当一个算法中循环和分支较多时就很难清晰地表示出来；自然语言表示的算法不便翻译成计算机程序设计语言理解的语言。2．流程图它采用美国国家标准化协会ANSI（AmericanNationalStandardInstitute）规定的一组图形符号来表示算法。流程图可以很方便地表示顺序、选择和循环结构，而任何程序的逻辑结构都可以用顺序、选择和循环结构来表示，流程图可以表示任何程序的逻辑结构。用流程图表示的算法不依赖于任何具体的计算机和计算机程序设计语言，（1）求解例4.4的算法流程图X=1Y=2X=X+YY=Y+1Y100结束开始YN（2）求解例4.5的算法流程图开始X=0I=1X=X+1/II=I+1I=N结束NY（3）求解例4.6的算法流程图开始n=0X=0，Y=1PrintX，YI=1In-1Z=X+YX=YY=ZPrintYI=I+1结束Y=0PrintYYNYN3．伪代码——（1）求解例4.4的伪代码算法描述：BEGIN(算法开始)1X2Ywhile（Y=100）{X+YXY+1Y}PrintXEND（算法结束）（2）求解例4.5的伪代码算法描述：BEGIN（算法开始）0X1Ido{X+1/IXI+1I}while(I=n)END（算法结束）（3）例4.6的伪代码算法描述：BEGINifn==0{0YPrintY}else{0X1YPrintX，Yfor(i=1;i=n-1;i++){X+YZYXZYPrintY}}END4．计算机程序设计语言计算机程序设计语言描述的算法（程序）是清晰的、简明的，最终也能由计算机处理的。缺点：算法的基本逻辑流程难于遵循。与自然语言一样，程序设计语言也是基于串行的用特定程序设计语言编写的算法限制了与他人的交流，不利于问题的解决；要花费大量的时间去熟悉和掌握某种特定的程序设计语言；要求描述计算步骤的细节，而忽视算法的本质。例4.4的计算机程序设计语言（C语言）的算法描述：main(){intX,Y;X=1;Y=2;while(Y=100){X=X+Y;Y=Y+1;};printf(%d,X);}例4.5的计算机程序设计语言（C语言）的算法描述main(){intn;floatX,I;printf(Pleaseinputn:);scanf(%d,&n);X=0;I=1;do{X=X+1/I;I=I+1;}while(I=n);printf(\n%f,X);}算法算法分析（1）算法的时间复杂度；用T(n)表示，n表示问题规模的大小。使用一个记号Order（数量级）的第一个字母，允许使用“=”代替“≈”。如n2+n+1=(n2)设f(n)是一个关于正整数n的函数，若存在一个正整数n0和一个常数C，当n≥n0时，∣T(n)∣≤∣Cf(n)∣均成立，则称f(n)为T(n)的同数量级的函数。算法时间复杂度T(n)可表示为：T(n)=(f(n))常见的大表示形式有：(1)称为常数级；(logn)称为对数级；(n)称为线性级；(nc)称为多项式级；(cn)称为指数级；(n!)称为阶乘级。算法的空间复杂度指算法在执行过程中所占存储空间的大小，用S(n)表示，S为英文单词Space的第一个字母。与算法的时间复杂度相同算法的空间复杂度S(n)也可表示为：S(n)=(g(n))。算法算法的研究算法算法：定义一向工作如何完成的步骤的集合在一台机器可以完成一个任务之前，必须找到完成这个任务的算法并且用与机器兼容的方式来描述一个与机器兼容的算法的描述——程序算法的研究开始是作为数学的一个学科目标：找到描述特定类型问题是如何被解决的指令的集合，如Euclidean算法一旦一个完成任务的算法被找到，任务的实现就不再需要对算法原理的理解，任务的实现仅仅是遵循算法的只是过程现有的解决问题需要的智慧被编码进了算法算法转化为智慧通过使用算法来得到并转化智慧，我们才可以构建起可以表现智慧行为的机器。机器表现的智能等级受到通过算法转化的智慧所限制如果没有解决问题的算法，意味着问题的解决方案超出了机器的能力范围算法的开发就成了计算机领域的一个主要目标如何找到算法——一个十分接近于寻找通用问题解决方案描述这个算法——转变为一个清晰的指令的集合（程序设计语言描述）计算机技术别用于复杂问题（大型软件系统）不仅仅包括实现任务的单个算法的开发还要求对组件之间的交互进行设计软件工程：借鉴了工程领域、项目管理领域、人力资源管理以及程序语言设计领域的经验执行算法的机器的设计和实现数据的存储数据的操作体系结构中涵盖了对现今技术的讨论我们的目标不是去熟知类似当今体系结构是如何用电路来实现这样的细节问题，那将会导致过分陷入电子工程学科正如昨天的齿轮驱动的计算机让位于电子设备一样，今天的电子技术也许很快也被其它的技术所取代理想情况下希望计算机的体系结构是我们的有关算法过程知识的延续，并且不应该被技术能力酸限制使我们的算法知识在当代机器体系结构的发展背后起推动作用，而不仅仅是从技术的要求触发来解顶机器的设计构建允许使用多个指令序列来代替算法的机器是可能的这些指令被同时执行或者作为机器于外部世界的接口的设计于计算机的设计紧密相连算法是如何机器中的？机器是如何被告知执行的是哪一个算法？计算理论对解决越来越复杂问题的算法的研究导致了算法过程的最终限制问题如果没有算法可以解决这个问题，那么算法是不能被机器所解决的，机器仅仅可以解决在算法上可解的问题Godel的不完全定理阐述了在任何传统算术领域的数学理论中，有些是既不能证明有不能被推翻的任何对算术系统的彻底研究都超出了算法的能力对算法的限制的研究欲望似的数学家们设计抽象的机器来执行算法，并在理论上