计算学科导论-计算科学的基本概念和基本知识

计算科学的基本概念和基本知识1.1计算模型与二进制数学不等于计算，但数学确实起源于对计算的研究。数学、计算模型（计算方法、数学机器）、形式化与形式化方法我们说，形式是事物的内容存在的外在方式、形状和结构的总和。所谓形式化是将事物的内容与形式相分离，用事物的某种形式来表示事物。形式化方法是在对事物描述形式化的基础上，通过研究事物的形式变化规律来研究事物变化规律的全体方法的总称。1.1.1计算模型与图灵机所谓计算模型是刻划计算这一概念的一种抽象的形式系统或数学系统，而算法是对计算过程步骤（或状态的一种刻划，是计算方法的一种能行实现方式。在计算机科学中，我们通常所说的计算模型，并不是指在其静态或动态数学描述基础上建立求解某一(类)问题计算方法的数学模型，而是指具有状态转换特征，能够对所处理的对象的数据或信息进行表示、加工、变换、输出的数学机器。由于观察计算的角度不同，产生了各种不同的计算模型。递归函数、Turing机等(1)s(x)＝x＋1（后继函数）(2)o(x)＝0（零函数）(3)Uj(n)(x1，x2，…，xn)＝xj（射影函数）由初始函数和有限次使用算子可以构造各种复杂的递归函数，或者可计算函数。图灵机的示意图控制器的命令可表示为：（状态，符号）→（写符号，移动，状态）；┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬──│０│０│０│１│１│１│０│１│１│１│┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴──↑┌─┐││┌┘└┐│控制器│└───┘一旦图灵机在运行中进入了一个状态，而且这个状态是一个结束状态，那么，图灵机就停机，计算任务宣告完成，此时带上的内容就是计算的输出结果。例1M的字母表A＝{0，1，b}，b表示空格。状态集Q＝{q1，q2，q3}，其中，指定q1是开始状态，q3是终止状态。M的程序（控制器的命令）如下：q101Rq1；q110Rq1；q1bbRq2；q2bbLq3；q200Hq1；q211Hq1；对图灵机的工作过程从不同的角度考察，可以给予不同的解释。第一，把图灵机看作识别器，即判断带子上最初的内容能否被图灵机所接受。假定图灵机从左向右扫描完带子上的内容后停机则为接受，否则为不接受。例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.TuringAward)，由美国计算机协会(ACM)于1966年设立，又叫A.M.图灵奖。专门奖励那些对计算机事业作出重要贡献的个人。其名称取自计算机科学的先驱、英国科学家阿兰·麦席森·图灵（AlanMathisonTuring）。由于图灵奖对获奖条件要求极高，评奖程序又是极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名合作者或在同一方向作出贡献的科学家共享此奖。因此它是计算机界最负盛名、最崇高的一个奖项，有计算机界的诺贝尔奖之称。从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×10ii＝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×2ii＝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。“与”、“或”、“非”三种门电路示意图PPP↑↑↑┌──┻───┓┌──┻──┓┌──┻──┓│·││＋││～│└┳─┳─┳┛└┳─┳─┳┛└──┳──┛↑↑↑↑↑↑↑ABCABCA（a）（b）（c）将布尔代数和前面谈到的二进制联系起来，我们可以看出，“与”、“或”、“非”门电路的作用与集合运算“交”、“并”、“补”是一致的。一旦门电路中仅使用两个电平信号0和1，引入二进制及其运算规则，那么，用门电路及其组合就可以实现二进制的各种运算，而对复杂电路的计算，如电路的化简就有可能通过布尔代数的方法进行。事实上也正是如此。由此可见，真正构成计算机科学基本的、核心的内容是围绕计算而展开的大量带有规律性的知识，而不是具体的实现技术。因为，在将来，我们完全可能发展一种能表示二进制数及其运算的新技术，它比今天的微电子技术精度更高、生产价格更便宜。如果真是那样，这种技术就可能取代微电子技术在计算科学中的地位。近年来科学研究的发展已显现出一些很有希望但尚不成熟的技术，如光电子技术，金属表面处理技术等。当然，程序技术在可预见的将来尚不太可能被别的技术所代替，原因是它与各种应用相联系，而且在形式上易于反映能行性这一本质的计算特征，在表达形式上与通常算法的描述较为接近,设计和生产的成本也比较低，又不存在工业污染的问题，所以不易被取代。因此，我们常说，从这个意义上讲，软件技术比微电子技术对计算科学更重要一些。2.4机器指令与汇编语言用计算机求解一个问题，必须事先编制好程序。程序是由指令组成的。每一台计算机都设计规定了一组指令集合，称为机器指令系统。机器指令的格式一般分为两部分，如下所示：┌───┬──────┐指令格式：│操作码│地址部分│└───┴──────┘其中，操作码指出运算的种类，如＋，－，×，÷，跳转等，地址部分用来指示参与运算的数据保存在什么地方，如存储器的某个地址或某个寄存器等。操作码和地址部分都用二进制代码表示。机器指令一般可根据其功能划分为以下几类：(1)控制指令；(2)算术运算指令；(3)逻辑运算指令；(4)移位操作指令；(5)传送操作指令；(6)输入/输出指令。应当注意的是，不同的机器，其指令系统是不同的。指令系统的日渐增大虽然给用户的程序设计带来了方便，但也带来了硬件设计复杂性的增加和因译码、存储、寻址等开销的增大而使运算速度下降。研究发现，指令系统存在着改进的必要和可能。真正使研究人员对指令系统进行较大改进的原因是超大规模集成电路（VLSI）技术的发展