《第二章计算机科学的基本概念和基本知识2.1计算模型与二进》由会员分享，可在线阅读，更多相关《第二章计算机科学的基本概念和基本知识2.1计算模型与二进（51页珍藏版）》请在金锄头文库上搜索。
1、第二章 计算机科学的基本概念和基本知识2.1 计算模型与二进制数学不等于计算，但数学确实起源于对计算的研究 。数学、计算模型（计算方法、数学机器）、形式化 与形式化方法我们说，形式是事物的内容存在的外在方式、形状 和结构的总和。所谓形式化是将事物的内容与形式相分 离，用事物的某种形式来表示事物。形式化方法是在对 事物描述形式化的基础上，通过研究事物的形式变化规 律来研究事物变化规律的全体方法的总称。 1.1.1 计算模型与图灵机所谓计算模型是刻划计算这一概念的一种抽象的形 式系统或数学系统，而算法是对计算过程步骤（或状态的一种刻划，是计算方法的一种能行实现方式。在计算机 科学中，我们通常所说的
2、计算模型，并不是指在其静态或 动态数学描述基础上建立求解某一(类)问题计算方法的数学模型，而是指具有状态转换特征，能够对所处理的对象 的数据或信息进行表示、加工、变换、输出的数学机器。 由于观察计算的角度不同，产生了各种不同的计算模型。递归函数、Turing机等 (1) s(x)x1 （后继函数）；(2) o(x)0 （零函数）；(3) Uj(n)(x1，x2，xn)xj （射影函数）。由初始函数和有限次使用算子可以构造各种复杂的递 归函数，或者可计算函数。图灵机的示意图控制器的命令可表示为：（状态，符号）（写符号，移动，状态）； 控制器一旦图灵机在运行中进入了一个状态，而且这个状态 是一个结
3、束状态，那么，图灵机就停机，计算任务宣告完 成，此时带上的内容就是计算的输出结果。例1 M的字母表A0，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 一台图灵机可以设计成识别下面的序
4、列：1000110, 10011101, 010101011。第二，把图灵机看作生成器，对给定的输入集合，考 察输出集合，并研究输入输出集合性质之间的关系，这就 研究了图灵机的生成能力。例3 设一台图灵机的输入集合为In1n0nnN，可 设计一台图灵机，对给定的输入集合In，得到输出集合 Out0n1nnN。其中，N是全体自然数的集合。第三，把图灵机看作计算器，相当于一个函数。图灵 机的输入是函数的自变量的值，图灵机的输出是函数的值 。例4 图灵机可以计算下列函数：(1) s(x)x1；(2) o(x)0；(3) A(0，y)y1，A(x1，0)A(x，1)，A(x1，y1)A(x，A(x1，
5、y)。第一和第二个函数读者不难从图灵机的定义出发感悟 到它们是图灵机可以计算的函数，而第三个函数就比较复 杂，一时难于判断。顺便提一下，第三个函数叫做阿克曼 函数，它是阿克曼（W.Ackermann）在研究原始递归函数和 递归函数的关系时给出的。这个函数在计算理论中具有重 要价值。事实上，图灵机还可以计算形式上比第三个函数 更复杂的函数。 沿着这样一种思路，图灵机被证明具有很强的计算能 力，它与30年代发展的递归函数论（一种能行可计算性理论）中一类最一般的可计算函数（部分递归函数或部分可 计算函数）在计算表达能力上是等价的。然而，图灵机简 洁的构造和运行原理隐含了存储程序的原始思想，深刻地揭示
6、了现代通用电子数字计算机最核心的内容。 图灵奖2.1.2 二进制也许是图灵机读写带上只出现两个符号启发了研究者 ，在当时的技术条件下，从便于元器件的设计和制造考虑 ，计算机的研制很自然地选择了二进制。后来的实践也证 明了这种选择具有极大的优点。十进制数的表示 例如，1997.630这个数可以写成：1997.6301103910291017100610-1310-2010-3一般地，任何一个十进制数S都可以表示为：Sknkn-1 k0. k-mkn10nkn-110n-1k0100k-m10-m-m ki10iin其中，10称为十进制的基数,ki0,1,2,3,4,5,6,7,8,9 ，m，n为
7、正整数。小数点的位置不言自明。二进制和十进制一样，是一种数制，它用于表示数的 符号（数字）由于在书写中的位置不同而具有不同的值。 二进制表示数的符号只有两个，即0和1，其数值与十进制 中的0和1相同。此外，与十进制不同之处在于二进制数是 逢二进一。例如，十进制数与二进制数中的一些可作如下对应：十进制 二进制(0) (0)(1) (1)(2) (10)(3) (11)(4) (100)(5) (101) (9) (1001)(10) (1010) 一般地，任何一个二进制数S都可以表示为：Sknkn-1 k0. k-mkn2nkn-12n-1k020k-m2-m-m ki2iin 其中，2称为二进
8、制的基数，ki0,1,m,n为正整数。进一步，读者可从十进制数和二进制数的一般表示公 式得到启发，将这种表示推广到更一般的任意进制，不同 之处只是基数不一样。 二进制的运算规则比十进制的运算规则简单得多。只 要建立两种进制的数据之间的转换方法，那么，二进制将 具有更多的优势。计算机的理论基础是逻辑和代数。当二 进制与同样只使用“真”和“假”两个值的逻辑代数建立 了联系后，这就为计算机的逻辑设计提供了便利的工具。2.2 存储程序式计算机的基本结构与工作原理图灵机的出现为现代计算机的发明提供了重要的思想 。 图灵机的带子可以看成是计算机的存储设备，数据可以存储在上面，也可以根据需要擦去。图灵机的命
9、令相当于一 组事先设计、存储好了的程序，它们在控制器安排下，决 定读写头的每一步操作。这样一种数学机器，如果不考虑 它的实用性，就思想和原理而言，确实包含了存储程序的 重要思想。程序与存储程序式计算机图灵机诞生后不到十年，在以冯诺依曼为代表的一 批科学家的努力下，现代存储程序式电子数字计算机的基 本结构与工作原理被确定下来。它主要由如下的五部分组 成（见P8图）：存储器，运算器，控制器，输入设备，输出设备在学科的发展历程中，习惯上，人们将不带有软件系 统的存储程序式电子数字计算机系统称为硬件裸机，将硬 件裸机，参与构成硬件裸机的各类部件及其研究范畴统称为硬件（方向）。 2.3 数字逻辑与集成电
10、路数字逻辑是数字电路逻辑设计的简称，其内容是应用 数字电路进行数字系统逻辑设计。电子数字计算机是由具 有各种逻辑功能的逻辑部件组成的，这些逻辑部件按其结 构可分为组合逻辑电路和时序逻辑电路。组合逻辑电路是 由与门、或门和非门等门电路组合形成的逻辑电路；时序 逻辑电路是由触发器和门电路组成的具有记忆能力的逻辑 电路。有了组合逻辑电路和时序逻辑电路，再进行合理的 设计和安排，就可以表示和实现布尔代数的基本运算。而 布尔代数只使用1（真）和0（假）两个数，这样，当二进制的加法、乘法等运算与布尔代数的运算建立了对应关系 后，就可以用逻辑部件来实现二进制数据的加法、乘法等 各种运算。例5 基本的“与”、
11、“或”、“非”门电路。“与”门电路一般有两个以上的输入和一个输出。图 (a)表示了一个“与”门电路，其输出P和输入A、B、C之间 的逻辑关系可用下面的式子表示：PABC电路设计中，用高电平信号表示1，低电平信号表示0 ，那么，“与”门电路只有当输入A、B、C同时为1时，输 出P才为1，否则，P为0。“或”门电路可以用图(b)表示。一般地说，“或”门 电路是一种具有逻辑加法功能的电路，它有两个以上的输 入和一个输出，其输出P和输入A、B、C之间的逻辑关系可用下 面的式子表示：PABC在具体的电路设计中，如果我们用高电平信号表示1， 低电平信号表示0，那么，“或”门电路仅当输入A、B、C 中有一个
12、为1时，输出P就为1，否则，P为0。“非”门电路可以用图(c)表示。一般地说，“非”门 电路是一种具有逻辑取反功能的电路，它只有一个输入和 一个输出，其输出P和输入A之间的逻辑关系可用下面的式 子表示：PA在具体的电路设计中，如果我们用高电平信号表示1， 低电平信号表示0，那么，“非”门电路当输入A为0时，输 出P就为1，否则，当输入A为1时，输出P为0。“与”、“或”、“非”三种门电路示意图P P P A B C A B C A（a） （b） （c）将布尔代数和前面谈到的二进制联系起来，我们可以 看出，“与”、“或”、“非”门电路的作用与集合运算 “交”、“并”、“补”是一致的。一旦门电路中
13、仅使用 两个电平信号0和1，引入二进制及其运算规则，那么，用 门电路及其组合就可以实现二进制的各种运算，而对复杂电路的计算， 如电路的化简就有可能通过布尔代数的方法进行。事实上 也正是如此。由此可见，真正构成计算机科学基本的、核心的内容 是围绕计算而展开的大量带有规律性的知识，而不是具体 的实现技术。因为，在将来，我们完全可能发展一种能表 示二进制数及其运算的新技术，它比今天的微电子技术精 度更高、生产价格更便宜。如果真是那样，这种技术就可 能取代微电子技术在计算科学中的地位。近年来科学研究 的发展已显现出一些很有希望但尚不成熟的技术，如光电 子技术，金属表面处理技术等。当然，程序技术在可预见 的将来尚不太可能被别的技术所代替，原因是它与各种应 用相联系，而且在形式上易于反映能行性这一本质的计算 特征，在表达形式上与通常算法的描述较为接近,设计和 生产的成本也比较低，又不存在工业污染的问题，所以不易被取代。因此，我们常说，从这个意义上讲，软件技术 比微电子技术对计算科学更重要一些。2.4 机器指令与汇编语言用计算机求解一个问题，必须事先编制好程序。程序 是由指令组成的。每一台计算机都设计规定了一组指令集 合，称为机器指令系统。机器指令的格式一般分为两部分，如下所示：指令格式： 操作码 地址部分 其中，操作码指出运算的种类，如，跳转 等，地址部分用来指示参与运算的数据保存在什
