VB网络聊天室网络多人聊天软件

计算科学的基本概念和基本知识 1.1 计算模型与二进制 数学不等于计算，但数学确实起源于对计算的研究。 数学、计算模型（计算方法、数学机器）、形式化与形式化方法 我们说，形式是事物的内容存在的外在方式、形状和结构的总和。所谓形式化是将事物的内容与形式相分离，用事物的某种形式来表示事物。形式化方法是在对事物描述形式化的基础上，通过研究事物的形式变化规律来研究事物变化规律的全体方法的总称。 1.1.1 计算模型与图灵机 所谓计算模型是刻划计算这一概念的一种抽象的形式系统或数学系统，而算法是对计算过程步骤（或状态的一种刻 划，是计算方法的一种能行实现方式。在计算机科学中，我们通常所说的计算模型，并不是指在其静态或动态数学描述基础上建立求解某一(类)问计算方法的数学模型，而是指 具有状态转换特征，能够对所处理的对象的数据或信息进行表示、加工、变换、输出的数学机器。由于观察计算的角度不同，产生了各种不同的计算模型。 递归函数、Turing机等 (1) s(x)＝x＋1 （后继函数） (2) o(x)＝0 （零函数） (3) Uj(n)(x1，x2，…，xn)＝xj （射影函数） 由初始函数和有限次使用算子可以构造各种复杂的递归函数，或者可计算函数。 图灵机的示意图 控制器的命令可表示为： （状态，符号）→（写符号，移动，状态）； ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬── │０│０│０│１│１│１│０│１│１│１│ ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴── ↑ ┌─┐ │ │ ┌┘ └┐ │控制器│ └───┘ 一旦图灵机在运行中进入了一个状态，而且这个状态是一个结束状态，那么，图灵机就停机，计算任务宣告完成，此时带上的内容就是计算的输出结果。 例1 M的字母表A＝{0，1，b}，b表示空格。状态集Q＝{q1，q2，q3}，其中，指定q1是开始状态，q3是终止状态。 M的程序（控制器的命令）如下： q1 0 1 R q1； q1 1 0 R q1； q1 b b R q2； q2 b b L q3； q2 0 0 H q1； q2 1 1 H q1； 对图灵机的工作过程从不同的角度考察，可以给予不同的解释。 第一，把图灵机看作识别器，即判断带子上最初的内 容能否被图灵机所接受。假定图灵机从左向右扫描完带子上的内容后停机则为接受，否则为不接受。 例2 一台图灵机可以设计成识别下面的序列： 1000110, 10011101, 010101011。 第二，把图灵机看作生成器，对给定的输入集合，考察输出集合，并研究输入输出集合性质之间的关系，这就研究了图灵机的生成能力。 例3 设一台图灵机的输入集合为In＝{1n0n│n∈N}，可设计一台图灵机，对给定的输入集合In，得到输出集合Out＝{0n1n│n∈N}。其中，N是全体自然数的集合。 第三，把图灵机看作计算器，相当于一个函数。图灵机的输入是函数的自变量的值，图灵机的输出是函数的值。 例4 图灵机可以计算下列函数： (1) s(x)＝x＋1； (2) o(x)＝0； (3) A(0，y)＝y＋1， A(x＋1，0)＝A(x，1)， A(x＋1，y＋1)＝A(x，A(x＋1，y))。 第一和第二个函数读者不难从图灵机的定义出发感悟到它们是图灵机可以计算的函数，而第三个函数就比较复杂，一时难于判断。顺便提一下，第三个函数叫做阿克曼函数，它是阿克曼（W.Ackermann）在研究原始递归函数和递归函数的关系时给出的。这个函数在计算理论中具有重要价值。事实上，图灵机还可以计算形式上比第三个函数更复杂的函数。 沿着这样一种思路，图灵机被证明具有很强的计算能力，它与30年代发展的递归函数论（一种能行可计算性理 论）中一类最一般的可计算函数（部分递归函数或部分可计算函数）在计算表达能力上是等价的。然而，图灵机简洁的构造和运行原理隐含了存储程序的原始思想，深刻地 揭示了现代通用电子数字计算机最核心的内容。 图灵奖 2.1.2 二进制 也许是图灵机读写带上只出现两个符号启发了研究者，在当时的技术条件下，从便于元器件的设计和制造考虑，计算机的研制很自然地选择了二进制。后来的实践也证明了这种选择具有极大的优点。 十进制数的表示 例如，1997.630这个数可以写成： 1997.630＝1×103＋9×102＋9×101＋7×100 ＋6×10-1＋3×10-2＋0×10-3 图灵奖 图灵奖(A.M. Turing Award)，由美国计算机协会(ACM)于1966年设立，又叫"A.M. 图灵奖"。 专门奖励那些对计算机事业作出重要贡献的个人。其名称取自计算机科学的先驱、英国科学家阿兰·麦席森·图灵（Alan Mathison Turing）。由于图灵奖对获奖条件要求极高，评奖程序又是极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名合作者或在同一方向作出贡献的科学家共享此奖。因此它是计算机界最负盛名、最崇高的一个奖项，有"计算机界的诺贝尔奖"之称。 从1966年到2015年，50届，共64名得主，按国籍分，美国学者最多，欧洲学者偶见之，华人学者目仅有2000年图灵奖得主姚期智(现在清华大学)。 据统计，截止2016年4月，美国著名学府加州大学伯克利分校的图灵奖人数（校友或教职工）位列世界第一（22位），斯坦福大学的图灵奖人数位列世界第二（20位），排名世界第三的是美国麻省理工学院（19位）；哈佛大学（13位）和卡耐基梅隆大学（12位）分列世界第四和第五名。 一般地，任何一个十进制数S都可以表示为： S＝knkn-1 … k0.… k-m ＝kn×10n＋kn-1×10n-1＋…＋k0×100＋…＋k-m×10-m -m ＝ ∑ ki×10i i＝n 其中，10称为十进制的基数,ki∈{0,1,2,3,4,5,6,7,8,9}，m，n为正整数。小数点的位置不言自明。 二进制和十进制一样，是一种数制，它用于表示数的符号（数字）由于在书写中的位置不同而具有不同的值。二进制表示数的符号只有两个，即0和1，其数值与十进制中的0和1相同。此外，与十进制不同之处在于二进制数是逢二进一。 例如，十进制数与二进制数中的一些可作如下对应： 十进制 二进制 (0) (0) (1) (1) (2) (10) (3) (11) (4) (100) (5) (101) … … … (9) (1001) (10) (1010) … … … 一般地，任何一个二进制数S都可以表示为： S＝knkn-1 … k0. … k-m ＝kn×2n＋kn-1×2n-1＋…＋k0×20＋…＋k-m×2-m   -m ＝ ∑ ki×2i i＝n   其中，2称为二进制的基数，ki∈{0,1},m,n为正整数。 进一步，读者可从十进制数和二进制数的一般表示公式得到启发，将这种表示推广到更一般的任意进制，不同之处只是基数不一样。 二进制的运算规则比十进制的运算规则简单得多。只要建立两种进制的数据之间的转换方法，那么，二进制将具有更多的优势。计算机的理论基础是逻辑和代数。当二进制与同样只使用“真”和“假”两个值的逻辑代数建立了联系后，这就为计算机的逻辑设计提供了便利的工具。 2.2 存储程序式计算机的基本结构与工作原理 图灵机的出现为现代计算机的发明提供了重要的思想。图灵机的带子可以看成是计算机的存储设备，数据可以存 储在上面，也可以根据需要擦去。图灵机的命令相当于一组事先设计、存储好了的程序，它们在控制器安排下，决定读写头的每一步操作。这样一种数学机器，如果不考虑它的实用性，就思想和原理而言，确实包含了存储程序的重要思想。 程序与存储程序式计算机 图灵机诞生后不到十年，在以冯·诺依曼为代表的一批科学家的努力下，现代存储程序式电子数字计算机的基本结构与工作原理被确定下来。它主要由如下的五部分组成（见P8图）： 存储器，运算器，控制器，输入设备，输出设备 在学科的发展历程中，习惯上，人们将不带有软件系统的存储程序式电子数字计算机系统称为硬件裸机，将硬件裸机，参与构成硬件裸机的各类部件及其研究范畴统称 为硬件（方向）。 2.3 数字逻辑与集成电路 数字逻辑是数字电路逻辑设计的简称，其内容是应用数字电路进行数字系统逻辑设计。电子数字计算机是由具有各种逻辑功能的逻辑部件组成的，这些逻辑部件按其结构可分为组合逻辑电路和时序逻辑电路。组合逻辑电路是由与门、或门和非门等门电路组合形成的逻辑电路；时序逻辑电路是由触发器和门电路组成的具有记忆能力的逻辑电路。有了组合逻辑电路和时序逻辑电路，再进行合理的设计和安排，就可以表示和实现布尔代数的基本运算。而布尔代数只使用1（真）和0（假）两个数，这样，当二进 制的加法、乘法等运算与布尔代数的运算建立了对应关系后，就可以用逻辑部件来实现二进制数据的加法、乘法等各种运算。 例5 基本的“与”、“或”、“非”门电路。 “与”门电路一般有两个以上的输入和一个输出。图(a)表示了一个“与”门电路，其输出P和输入A、B、C之间的逻辑关系可用下面的式子表示： P＝A·B·C 电路设计中，用高电平信号表示1，低电平信号表示0，那么，“与”门电路只有当输入A、B、C同时为1时，输出P才为1，否则，P为0。 “或”门电路可以用图(b)表示。一般地说，“或”门电路是一种具有逻辑加法功能的电路，它有两个以上的输入和 一个输出，其输出P和输入A、B、C之间的逻辑关系可用下面的式子表示： P＝A＋B＋C 在具体的电路设计中，如果我们用高电平信号表示1，低电平信号表示0，那么，“或”门电路仅当输入A、B、C中有一个为1时，输出P就为1，否则，P为0。 “非”门电路可以用图(c)表示。一般地说，“非”门电路是一种具有逻辑取反功能的电路，它只有一个输入和一个输出，其输出P和输入A之间的逻辑关系可用下面的式子表示： P＝～A 在具体的电路设计中，如果我们用高电平信号表示1，低电平信号表示0，那么，“非”门电路当输入A为0时，输出P就为1，否则，当输入A为1时，输出P为0。 “与”、“或”、“非”三种门电路示意图 P P P ↑ ↑ ↑ ┌──┻───┓ ┌──┻──┓ ┌──┻──┓ │ · │ │ ＋ │ │ ～ │ └┳─┳─┳┛ └┳─┳─┳┛ └──┳──┛ ↑ ↑ ↑ ↑ ↑ ↑ ↑ A B C A B C A   （a） （b） （c） 将布尔代数和前面谈到的二进制联系起来，我们可以看出，“与”、“或”、“非”门电路的作用与集合运算“交”、“并”、“补”是一致的。一旦门电路中仅使用两个电平信号0和1，引入二进制及其运算规则，那么，用门电路及其组 合就可以实现二进制的各种运算，而对复杂电路的计算，如电路的化简就有可能通过布尔代数的方法进行。事实上也正是如此。 由此可见，真正构成计算机科学基本的、核心的内容是围绕计算而展开的大量带有规律性的知识，而不是具体的实现技术。因为，在将来，我们完全可能发展一种能表示二进制数及其运算的新技术，它比今天的微电子技术精度更高、生产价格更便宜。如果真是那样，这种技术就可能取代微电子技术在计算科学中的地位。近年来科学研究的发展已显现出一些很有希望但尚不成熟的技术，如光电子技术，金属表面处理技术等。当然，程序技术在可预见的将来尚不太可能被别的技术所代替，原因是它与各种应用相联系，而且在形式上易于反映能行性这一本质的计算特征，在表达形式上与通常算法的描述较为接近,设计和生产的成本也比较低，又不存在工业污染的问题，所以不 易被取代。因此，我们常说，从这个意义上讲，软件技术比微电子技术对计算科学更重要一些。 2.4 机器指令与汇编语言 用计算机求解一个问题，必须事先编制好程序。程序是由指令组成的。每一台计算机都设计规定了一组指令集合，称为机器指令系统。 机器指令的格式一般分为两部分，如下所示： ┌───┬──────┐ 指令格式： │操作码│地址部分 │ └───┴──────┘ 其中，操作码指出运算的种类，如＋，－，×，÷，跳转等，地址部分用来指示参与运算的数据保存在什么地方，如存储器的某个地址或某个寄存器等。操作码和地址部分都用二进制代码表示。 机器指令一般可根据其功能划分为以下几类： (1)控制指令；(2)算术运算指令；(3)逻辑运算指令； (4)移位操作指令；(5)传送操作指令；(6)输入/输出指令。 应当注意的是，不同的机器，其指令系统是不同的。 指令系统的日渐增大虽然给用户的程序设计带来了方便，但也带来了硬件设计复杂性的增加和因译码、存储、寻址等开销的增大而使运算速度下降。研究发现，指令系统存在着改进的必要和可能。 真正使研究人员对指令系统进行较大改进的原因是超大规模集成电路（VLSI）技术的发展和采用微程序技术实现体系结构设计思想的过程中硬件复杂性的不断增长带来的技术上的困难，使人们开始认识到在进行计算机系统设计时，应 公平对待硬件与软件的地位，使两者平衡负担整个系统的复杂性。这一认识的转变直接导致了精简指令系统计算机（RISC）的诞生。所谓RISC是根据指令系统中各种指令应用 的规律，将最常用的指令，以及一些控制较为简单的寄存器－寄存器的操作与寄存器等一起直接做在VLSI芯片上，靠减少译码、存储、寻址方式和次数等开销而大大增加运算速度。实际上，RISC主要是一种体系结构设计的思想，而不只是一种计算机产品。RISC技术由于极大地提高了计算机的运算速度，因而它的问世被认为是计算机体系结构发展史上的一个里程碑。 汇编语言 汇编语言实际上是由一组汇编指令构成的语言。每一条汇编指令用某个西文字符串的缩写来表示其所代表的操作，用符号来代表数据的二进制、八进制和十进制数字序列。大多数情况下，一条汇编指令对应一条机器指令，少数对应几 条机器指令。例如，下面是几条汇编指令的操作符，右边中文是名称。 add 加法 idiv 有符号除法 mul 无符号乘法 neg 求补 xchg 交换 test 逻辑比较 jmp 无条件转移 有了汇编语言，就得编写和设计汇编语言翻译程序（简称汇编程序），专门负责把使用汇编语言书写的程序翻译成可直接执行的机器指令程序。一般说来，汇编程序被看成是系统软件的一部分。 当然，汇编语言在可读性和编写程序时仍然是不能令人满意的，这导致进一步发展了高级程序设计语言。不过，由于高级语言在使用时通常还是要通过编译程序逐步将高级语言写的程序翻译成机器指令的程序，而这种翻译的结果往往不如机器指令或汇编语言写的程序效率高，所以，直到今天，不少师在系统软件的开发中还在使用机器指令和汇编语言。 2.5 算法、过程与程序 求解一个给定的问题，不同的人常编写出不同的然而都是正确的程序，这是为什么呢？ 这里存在两个层面的问题，一个是与计算方法密切相关的算法问题，另一个是程序设计的技术问题。 例6 给定两个整数，求它们的最大公因数。 不失一般性，设有不全为0的整数x、y，记gcd(x，y)为它们的最大公因数，即同时能整除x、y的公因数中的最大者。显然，gcd(x，y)可表示为 gcd(x，y)＝max{z│ z|x，z|y} 这个问题许多中学生都会解，最常见的有著名的欧几里德辗转相除计算方法。当然，还有许多种解法。我们首先从函数gcd(x，y)的性质出发来求解。函数gcd(x，y)具有如下性质： (1) gcd(a，b)＝gcd(b，a) (2) gcd(a，b)＝gcd(―a，b) (3) gcd(a，0)＝|a| (4) gcd(a，b)＝gcd(b，a mod b)，0≤a mod b＜b （欧几里德辗转相除计算方法） 根据以上性质，我们可以设计如下算法： 算法A（计算函数gcd(x，y)） A1. 输入x，y；z是辅助变量； A2. 重复执行如下操作步骤： (1) 若y＝0，则输出|x|，算法停止． (2) 若y≠0，则z←x mod y，x←y，y←z； 有了计算函数gcd(x，y)的算法，用程序设计语言很容易写出可在计算机上执行的程序。算法A的核心是利用了函数gcd(x，y)的上述第四条性质。倘若我们使用的不是第四 条性质，那么，算法就会发生改变。 不难想象，不同的求解方法将产生出不同的算法，不同的算法将使我们设计出不同的程序，而决定这个程序功 能的本质是计算方法及其算法。一般地说，对不同计算方法过程的抽象描述就产生了相应的不同算法，但同一算法由不同的人来写程序则完全可能设计出差别很大的程序。 凭直觉想象给出的算法往往不是最好的算法。 例7 用程序变换技术设计的计算函数gcd(x,y)的程序 利用一种叫做程序变换技术的程序设计方法，可以产生计算函数gcd(x,y)的如下递归过程性程序： Procedure gcd(x，y:int，var z:int)； begin if x＝0 then z:＝y； x≤y & x≠0 then gcd(x，y－x，z)； x＞y & x≠0 then gcd(y，x，z) endif end； 显然，这个程序要一眼看出其功能是困难的。实际上，这个反映辗转相除计算方法程序经过程序变换，形式上已发生了很大变化。 这两个例子进一步引发我们的一些思考：如何确保算法和程序的正确性？既然求解同一个问题可以有不同的方法，不同的算法，不同的程序，那么，怎么来判断算法和程序的好坏呢？程序变换是否改变算法呢？ 上面两个例子初步表明算法、程序与数学之间存在着密切的联系。要解决上面的问题，没有数学和计算科学理论的支持恐怕不行。多年来大学计算机科学本科教学的实践已反复证明，实际情况正是如此。 在计算机科学研究中，事实上存在一条规律：一个问 题，当它的描述及其求解方法或求解过程可以用构造性数学描述，而且该问题所涉及的论域为有穷，或虽为无穷但存在有穷表示时，那么，这个问题一定能用计算机来求解； 反过来，凡是能用计算机求解的问题，也一定能对该问题的求解过程数学化，而且这种数学化是构造性的。 当一个问题的求解获得了计算方法和算法时，并不等于万事大吉了。在许多情况下，找到求解一个问题的算法只是走完了第一步。至于现实是否可以计算，则取决于算法的存在性和计算的复杂性，即取决于该问题是否存在求解算法，算法所需要的时间和空间在数量级上能否被接受。要注意的是，有的问题虽然存在求解问题的计算方法，但是，不存在算法。原因有两种可能：一是计算方法可能不是构造性的；二是虽为构造性的，但计算方法不能保证计算过程在任何初值的情况下都能结束。 算法复杂性 什么是算法的复杂性呢？ 使用计算机计算各种问题，需要存储空间、计算时间。不同的算法计算所需要的时间和空间是不同的。所谓算法 的复杂性就是对算法计算所需要的时间和空间的一种度量。由于不同的计算机千差万别，运算速度和字长可以相差很大，因此，不可能用算法在某一台计算机上计算所需要的实际的时间和存储单元（空间）去衡量这个算法的复杂性。那么，怎样才能准确刻划算法的计算复杂性呢？ 引入渐近增长率的概念来刻划算法的计算复杂性。渐进增长率用复杂性度量函数表示，该函数表示了算法随问题规模大小变化引起的算法中抽象的基本运算执行的次数或存储空间量的变化规律。如某个计算问题当输入规模分别为1，2，3，…，n时，经算法中抽象的基本运算次数分别为1，4，9，…，n2，那么，就可以用函数n2来刻划这个算法的时间复杂性，并称这个算法的时间复杂性度量为(n2)级。 有了复杂性度量函数，一旦选定具体计算机，可以根据这台计算机对某个n值的实际运算速度比较准确地估算出对其他的n值完成计算所需要的时间。于是，对各种算法的复杂 性进行分析的关键是要设法去找出这样的函数，它涉及到与数学密切相关的算法的设计原理、思想和方法，算法分析是具有智力挑战性的研究课题。 证比求易算法（本书上的三个中国人算法） 在算法计算复杂性的研究中，一个算法如果存在图灵机可计算的多项式时间计算复杂性算法，就将这个算法归入P类，如果存在非确定性图灵机可计算的多项式时间计算复杂性算法，就将其归入NP类。对大多数实际问题来说，找到一个解可能很难，检验一个解常常比较容易，所以都属于NP类。现在，计算科学研究中一个悬而未决的重要问题是： P＝NP？。 P＝NP？ 这个问题不仅具有理论上的价值，而且具有重大实用价值。因为到目前为止，已经发现了一批可计算但有相当难度的问题是属于NP类的，并且常通过证明一个问题与已知 属于NP类中的某个问题（如可满足性问题，简称SAT问题）等价将其归入NP类。不过，该问题是否属于 P类，即是否能找到多项式时间计算复杂性算法求解该问题，或证明该问题不存在多项式时间计算复杂性算法求解，至今尚未解决。现在，很多人都猜测秋碧贞楠的看法是对的：求解一个问题总是比验证一个问题的解要难，用公式表示也就是P≠NP。70年代初，库克（S. A. Cook）和卡尔普（R. M. Karp）指出，NP类中有一小类问题具有以下性质：迄今为止，这些问题多数经过深思熟虑还没有人找到多项式时间计算复杂性算法。但是，一旦其中的一个问题找到了多项式时间计算复杂性算法，这个类中的其它问题也能找到多项式时间计算复杂性算法，那么就可以断定P＝NP。换句话说，如果确属这个 类中的某个问题被证明不存在多项式时间计算复杂性算法，那么，就等于证明了P≠NP。通常，将这类问题称为NP完全性问题。 正是由于这些原因，算法被认为是计算科学的核心问题之一。 定义1（算法） 给定问题和设备，一个算法是用该设备可理解的语言表示的，解决这个问题的一种方法的精确刻划。特别，算法具有下列特征属性： (1) 算法应用于一个具体的输入集合或问题描述将在有穷步动作序列之后得到结果； (2) 该序列有一个唯一的初始动作； (3) 该序列中的每一个动作有一个唯一的后继动作； (4) 该序列终止时或者得到这个问题的解，或者因该问题不可解而获得不可解说明。 定义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、  随着计算机应用领域的不断拓展，针对各个应用领域的不同特点和程序设计的经验，科研人员设计和发展了一批高级程序设计语言。 对于一个已经有了计算该问题算法的待解问题，不同的人根据同一算法可能编出完全不同然而都是正确的程序。这种不同除了程序的书写形式有区别外，重要的是这些程序的结构反映在程序设计的构思和易读性方面有差别，程序运行的效率（主要指速度）不一样，有时相去甚远。这是为什么呢？ 程序设计语言是一门科学 对程序结构本质的深入研究促进了对程序质量的认识 开发程序的效率和质量取决于程序设计方法和技术 多年的研究发展了许多程序设计方法和技术。如自顶向下逐步求精的程序设计方法、自底向上的程序设计方法、程 序推导的设计方法、程序变换的设计方法、函数式程序设计技术、逻辑程序设计技术、面向对象的程序设计技术、程序验证技术、约束程序设计技术、并发程序设计技术等。 例如，对于许多问题的计算，可以用类似于计算函数的方法来进行，也可以用表（一种数据结构）处理的方法来进行，甚至还可以用逻辑公式演绎推导的方法进行，在实现技术上，既可以用递归技术计算，也可以用迭代技术或其它技术进行计算。 作为一门科学，高级语言和程序设计确实对学科的发展产生了巨大的影响。程序设计方法和技术在各个时期的发展不仅直接导致了一大批风格各异的高级语言的诞生，而且许多新思想、新概念、新方法和新技术不仅在语言中得到体现，同时渗透到了计算机科学的各个方向，从理论、硬件、软件到应用等多方面深刻影响了学科的发展。对高级语言和程序设计的掌握是计算机科学专业的基本功之一。 2.7 系统软件与应用软件 从计算机（硬件裸机）到计算机系统 从计算机系统到计算机体系结构 软件是一个发展的概念，早期软件和程序几乎是同义词。后来，软件的概念在程序的基础上得到了延伸。1983年，IEEE对软件给出了一个较为新颖的定义，指出：软件是计算机程序、方法、规范及其相应的文稿以及在计算机上运行时所必须的数据。 在软件的发展过程中，人们将各种软件分成两大类。一类称为系统软件，一类叫做应用软件。所谓系统软件是指那些参与构成计算机系统，提供给计算机用户使用，用于扩展计算机硬件功能、维护整个计算机硬件和软件系统，平滑用户思维方式、操作习惯与计算机硬件设备之间沟坎的软件。应用软件是相对于系统软件而言的，它是对用户在计算机系统上针对各种具体的应用问题开发的一类专用程序或软件的 总称。一般地说，操作系统、汇编程序、编译系统、数据库管理系统、软硬件故障诊断程序、子程序库、各种软件开发 工具和软件包及其说明文件等属于系统软件，其它由用户开 发的各种形形色色的应用程序及其说明文件或应用软件系统被称为应用软件。 操作系统---一种系统软件，它负责管理计算机系统中的各种资源并控制各类程序的运行。它通过接受来自用户的操作命令，按照用户的要求对计算机的工作进行控制。计算机配上操作系统之后，能够提高效率，便于使用。 系统软件和应用软件迄今并没有严格的定义。 2.8 计算机组织与体系结构 从计算机系统的逐个设计、制造到计算机的系列化和软件的兼容性 IBM 360系统标志着计算机体系结构（Architecture）研究的开端（1964年）。计算机体系结构是使用机器语言编写程序的用户可以看到的一个机器的抽象结构，而对这一结 构实现的硬件组成属于计算机组成原理研究的范畴。 随着大规模和超大规模集成电路（LSI/VLSI）技术的成熟，一方面器件速度和可靠性在不断提高，目前已逼近极限，另一方面器件的体积和价格在持续下降，这极大地增强了计算机的性能。然而，高质量的器件不是产生高性能计算机的唯一因素。虽然，今日大多数计算机都是图灵－冯·诺依曼型存储程序式电子数字计算机，但人们早已认识到计算机不仅仅是一个硬件组织的问题。一个现代的计算机系统一般被认为是由存储器、处理器、功能部件、互联网络、汇编程序、编译程序、操作系统、外部设备、通信通道等内容组合而成的。 早期计算机系统研究与开发的两个基本特点： （1）硬件和软件的研究与开发基本上是独立进行的； （2）硬件的研究与开发更多的是从计算机组成原理上去关 心各部件中分离元器件及其相互之间的联接关系，关心各部件的内部构造和外部特性； 集成电路的发展改变了专业人员的认识。 计算机CPU的速度和存储器的容量成倍增长，各种多功能部件不断引入，如何设计和配置计算机系统使其具有更高的性能价格比，适应不同用户的要求，成为亟待解决的问题。集成电路的发展也使许多专业人员可以不再关心各部件的内部细节，而只须考虑如何以一种统一的观点从硬件器件和一些软件系统出发，通过组合配置，设计功能更强、性能价格比更高、更可靠的计算机系统。于是，计算机体系结构应运而生。 典型的、有助于常人理解计算机体系结构的方向是所谓的网络计算机系统。用户面对网络计算机系统进行开发是十分困难的，因为，他不可能熟悉网上每一种通信资源）的配 置情况，而且也不了解每一种通信资源的基本操作方法，更不可能考虑通信出错的情况以及如何纠错。显然，对于用户来说，需要有一种能够屏蔽计算机硬件系统技术细节，仅对用户提供功能透明的系统层，使用户看到的和实际使用的是一个与使用者思想方式、使用习惯比较接近，无须具体关心网络计算机通信时一些十分繁琐的技术细节的分布式计算机系统。 硬件的互联结构和软件结构及相互关系形成的计算机系统的总体结构，支持这种结构的基本算法，还有以总体结构为基础的面向用户的程序设计语言等内容构成了计算机体系结构的技术范畴。 2．9 并行计算机、通道与并行计算 单CPU计算机 – 多功能部件多寄存器计算机 – 流水线向量计算机 –阵列式计算机 – 多处理器并行计算机 – 多 处理机并行计算机 – 多计算机网络并行计算机系统 并行处理要求在计算机上并行地运行许多程序。根据使用的计算机系统的不同，我们可以在四个程序的级别上提出并行处理的问题： 作业或程序级并行 任务或过程级并行 指令级并行 指令内部级并行 不同的并行处理思想和技术，产生了不同的并行计算机系统。从使用方便的角度考虑，用户更希望看到的是系统提供作业或程序级并行，这样用户可以不必考虑实现并行的细 节。而从实际计算提高效率的角度考虑，用户更希望系统已经实现了指令级并行或指令内部级并行。那么，面对众多的并行计算机系统，我们应该怎么来认识和区别它们的 系统结构呢？ 注意到了程序在计算机上的执行实际上是指令在数据集上的一个操作序列这样一个基本的事实，M. J. Flynn在1966年提出了一种著名的、也是现今比较常用的系统结构分类方法。他将计算机系统的系统结构分为四类，分别是：单指令流单数据流计算机（SISD）、单指令流多数据流计算机（SIMD）、多指令流单数据流计算机（MISD）、多指令流多数据流计算机（MIMD）。 由多机系统技术的扩展及网络互连与通信技术的引入，发展了分布式网络计算机系统，提出了分布式计算机体系结构、分布式算法与分布式并行处理的概念等。 并行计算机系统的出现，带来了信息并行化处理的概念。并行处理是信息处理的一种有效形式，它着重于发掘计算过程中的并发事件。并发性包含宏观上的并行性，包 含同时性以及微观上的流水线处理。并行事件可在同一时间间隔内在多个资源（如多个处理器）里发生；同时事件可在同一时刻上发生，流水线事件可在部分重叠的时间内于一个（或多个）资源里出现。并发通常是指宏观上一个资源里并行发生了两个或两个以上的事件，但在微观上是顺序发生的，而并行通常是指多个资源里微观上同时发生了两个或两个以上事件。显然，一组事件是并行的也是并发的，但一组事件是并发的却不一定是并行的。 通道 - 通道是数据或信息传送的通路 利用并行计算机系统进行数据与信息的并行处理称为并行计算。从处理对象的角度划分，并行计算分为数值并行计算和非数值并行计算。与顺序计算类似，并行计算也 分成几个步骤：研究并行计算方法，研究并行算法，设计并行程序，调试与运行，分析结果。由于许多问题的计算已经有了计算方法，而这些计算方法中隐含了大量的并行 性，稍作变化就可支持并行算法和并行程序设计，而且，由于各种并行计算机的系统结构不同，各处理器和各多功能部件之间在体现算法时的相互作用不同，算法不能通用。因此，除了并行计算机体系结构的研究外，当前和今后相当长的一个时期内并行处理的一个工作重点将是研究各种并行与分布式计算机系统上的并行算法或分布式算法。 2.10 计算机网络与通信 随着计算科学及其应用的高速发展，用户对软硬件和信息资源共享的需求和一大类问题本身具有地域上分布的特点，促进了计算机网络的发展。 所谓计算机网络是使用通信设备和通信线路将一组地理上分布的相同（称为同质）或不同（称为异质）的计算机、终端及其附属设备按照某种方式互联起来得到的一个计算机 硬件系统，也叫网络计算机。在这种计算机硬件系统的基础上，通过开发能协调各台计算机系统工作的通信系统或更进一步的网络操作系统，就能使一组计算机实现软硬件资源共享、协同计算，合作求解一个问题。由这种通信系统或网络操作系统连同网络计算机一起，就形成了网络计算机系统。 按照数据传输范围和实现技术的不同，计算机网络存在局域计算机网络和广域计算机网络之分。局域计算机网络是一个数据通信系统，其传输范围在中等地理区域，使用中等或高速数据传输速率，使用专用数据通信线或总线进行通信，可联接大量独立设备，在物理通信通道上互相通信。 广域计算机网络把不同城市、不同国家中的计算机或计 算机系统通过分级互联技术联接起来，其传输范围可达到相当远的距离。目前最常见的是使用公用或专用电话线通信，主干网和一些局域网使用可进行数字通信的光纤光缆 数据通信专用线。 网络互联的拓扑结构是计算机网络的重要特性。网络的拓扑结构是一种抽象的由点和线组成的图。网络上的每台计算机用一个结点表示，机器与机器之间的链路用线和路径表示，于是，图论构成了网络计算机体系结构中一些基本算法研究中数学描述的理论基础。 支持计算机网络的重要技术是通信，即实现计算机之间信息传输的一种技术方式。网络通信的核心内容是通信协议。所谓通信协议是网络通信中一组约定的集合，由它确定了经由通信网络传输的信息或存储在报文和数据库中 的信息的格式和控制方式。研究通信协议主要是为了在网络计算机系统中实现可靠的、高效的数据交换，差错控制，信息编码，线路利用，同步，使通信数据具有透明性。 网络上连接着大量的计算机系统，每一台计算机系统上可能有多个用户在同时使用计算机与其它网上用户进行通信，而网络的通信线路通常设计成公用资源，这样，网络通信为了实现可靠的数据交换，因需要做许多具体的操作运算而变得十分复杂。由于从用户发送或接收可以识别的符号信息到实际在正确的通信线路上传递物理信息之间存在转换、线路利用、分组交换、差错纠正等一系列的操作，为了便于协议的有效实现和对不同的用户开放，最大限度地实现线路的有效利用，有必要对网络计算机系统进行通信结构分层。于是产生了网络协议层。每一层包含一组通信功能和相应的层间通信协议，支持通信双方在不同的层间进行通信，并提供了实现通信的具体思想和方法。 按照ISO的建议，网络结构模型是开放系统互连模型OSI（七层协议），包括物理层，数据链路层，网络层，传输层，会话层，表示层，应用层共七层，产生了七层协议。 开放系统A 开放系统B ┌─────┐ 应用层协议 ┌─────┐ │应用层 ├－－－－－－－－－－－－－－┤应用层 │ ├─────┤ 表示层协议 ├─────┤ │表示层 ├－－－－－－－－－－－－－－┤表示层 │ ├─────┤ 会话层协议 ├─────┤ │会话层 ├－－－－－－－－－－－－－－┤会话层 │ ├─────┤ 传输层协议 ├─────┤ │传输层 ├－－－－－－－－－－－－－－┤传输层 │ ├─────┤ 网络层协议 ├─────┤ │网络层 ├－－－－－－－－－－－－－－┤网络层 │ ├─────┤ 数据链路层协议 ├─────┤ │数据链路层├－－－－－－－－－－－－－－┤数据链路层│ ├─────┤ 物理层协议 ├─────┤ │物理层 ├－－－－－－－－－－－－－－┤物理层 │ ┌┴─────┴──────────────────────┴─────┴┐ │ 物理传输介质 │ └────────────────────────────────────┘ 物理层协议实现物理上互连系统间位流信息的透明传输，即实现了一位（组）数据在两个通信实体之间的可靠传送通信，它描述了经通信介质在数据链路实体之间建立、维 护和拆除物理连接。 数据链路层协议主要是对高层屏蔽传输介质的特性，为网络通信实体之间提供建立、维护和释放数据链路连接的功能和手段，实现无差错的数据以帧为单位的可靠传送。 网络层协议主要是为通信子网与高层结构之间提供界面连接，其主要任务是对通信子网实现路径选择，实现通信实体之间端-端的透明的数据传送，对高层屏蔽了数据传送经过的路径。 传输层协议也称为主机-主机层协议，它为会话层的通信实体之间提供透明的数据传送，其主要任务是接收会话实体送来的数据，根据需要把它们分成若干比较小的单元，保证所有数据单元经下面三层正确地到达另一个会话实体。 会话层协议也称进程-进程层协议，它通过协议提供的一组命令为网上两个进程之间的通信建立会话连接和释放会话连接，并管理它们在该连接上的对话。 表示层协议以对应用实体有意义的形式提供有关信息表示的服务。这些服务有文本压缩、代码转换、数据加密与解密、文件格式变换、信息格式变换、终端属性的转换等。 应用层协议是用户访问网络的接口层，直接为正在通信的端点用户的应用进程服务，如电子邮件、远程操作访问、虚拟终端等。 关于协议详细的实现技术，其主要的基础是分布式算法，今后，同学们有可能学习这些内容。 网络信息安全、加密、病毒、高性能计算与通信、信息高速公路、数字地球