计算学科导论-计算科学的基本概念和基本知识讲述.ppt

定义1是一种百科全书式的定义，在专业上似乎不够严谨，而且也不适应于不确定性算法和分布式、并行算法。 Knuth的算法定义 定义2（Knuth算法定义） 一个算法，就是一个有穷规则的集合，其中之规则确定了一个解决某一特定类型问题的运算序列。此外，算法的规则序列须满足如下五个重要条件（特性）： (1) 有穷性。算法必须总是在执行有穷步之后结束； (2) 确定性。算法的每一个步骤必须是确切地定义的； (3) 输入。算法有零个或多个输入； (4) 输出。算法有一个或多个输出，即与输入有某个特定关系的量； (5) 能行性。算法中有待执行的运算和操作必须是相当基本的，即是说，它们原则上都是能够精确地进行的，而且用笔和纸做有穷次就可以完成。 有穷性和能行性是算法最重要的两个特征。对有些问题来说，如果我们给出了一个类似于算法的有穷运算序列，而它对某些输入可能不停机，那么，我们就称这样的运算 序列为一个过程。算法和过程都满足能行性和确定性，唯一的本质区别是算法的执行必须终止，而过程则不然，它可以永不停止。需要指出的是，高级程序设计语言中也有过程的概念，但与这里所讲的过程不同，那里实际上指的是一种子程序。 1960年代，克努特把计算机科学定义为是研究算法的学问。不过，由于1980年代计算机科学中并行与分布式算法的发展与计算机体系结构密切相关，以及学科研究中发展多种不同层面计算模型的需要，包括发展非图灵－冯·诺依曼型计算模型，使许多人认识到研究计算模型与体系结构具有与研究算法同等的重要性，从而使今天学术界对计算科学下的定义变得比过去更为准确。（见第二章） 一般地说，对任何一个问题，如果有了解决该问题的算法，就可以编制相应的程序。所谓程序，是一种事先编制好了具有特殊功能的指令序列。其中，指令既可以是机器指 令，汇编语言指令，也可以是高级语言的语句命令，甚至还可以是用自然语言描述的运算、操作命令。当然，用自然语言编写程序是计算机科学进入非常高级的阶段的标志之一，有赖于自然语言理解取得重大突破，目前看来还是一个十分遥远的设想。 程序这一概念的出现，得益于人类长期的生活实践，程序设计也不神秘。但是，程序设计是一种高智力的活动，不同的人对同一事物的处理可以设计出完全不同的程序。我们每一个人的生活经历已经告诉自己，知识和阅历（经验）是处事（设计程序）的基础。正因为如此，在计算机发展的早期，程序设计被认为是一个与个人经历、思想和技艺相联系的一种技艺和技巧。后来，软件开发规模的扩大和开发方式 的变化，程序设计才开始被当成一门科学来对待。 既然程序如此重要，又为人类经常使用，就有必要对程 序及其运行的规律进行深入的研究。于是，对程序各种性质 如程序的结构、程序的正确性、程序的运行效率等的研究产生了计算机科学十分重要的一个方向──程序理论。 有一种程序的定义，用公式给出： 程序＝数据结构＋算法； 定义初看起来有新意，它从程序的特征入手，高度抽象和概括。然而，仅有学术上的辅助参考价值，不能作为科学的定义。因为，按照定义，一旦数据结构和算法的定义被确定下来，程序的概念应该被随之确定，而实际上，程序的概念比数据结构加算法的涵义更广。考虑到我们前面给出的算法定义都明确要求满足终止性的属性，而程序可以不停机，甚至采用非常高级的程序设计语言设计的程序可以没有任何 数据结构，有的程序中看不到算法（如Prolog程序中一些推理计算的过程）。所以，我们还是只取前一种程序的定义更合适一些。 2.6 高级语言与程序设计技术和方法 所谓高级程序设计语言（简称高级语言）是指用于描述计算机程序的类自然语言。这种语言只是自然语言的一个很小的子集，在语法结构上比较简单而且规范，在语义上较少二义性，能够以比较准确、易读的形式描述各种计算机程序。例如，人们常见的Fortran语言、Pascal语言、C语言，LISP语言，Ada语言，Prolog语言，等等。 高级程序设计语言是程序设计发展的产物。  1950年代: Fortran语言、Basic、Algol； 1960年代：PL/1、APL、COBOL、SNOBOL、Algol-68、 Pascal、SIMULA、LISP、C、?? 1970年代: Prolog、Smalltalk、Ada、XYZ、Beta、 ? 随着计算机应用领域的不断拓展，针对各个应用领域的不同特点和程序设计的经验，科研人员设计和发展了一批高级程序设计语言。 对于一个已经有了计算该问题算法的待解问题，不同的人根据同一算法可能编出完全不同然而都是正确的程序。这种不同除了程序的书写形式有区别外，重要的是这些程序