计算机科学导论全册配套完整精品课件.ppt

1、 计算科学是计算的学问，其研究的核心问题是：计算科学是计算的学问，其研究的核心问题是： 什么是可自动计算的，怎样去自动计算。随着计什么是可自动计算的，怎样去自动计算。随着计 算机的普及，计算机已经日益成为越来越多的人算机的普及，计算机已经日益成为越来越多的人 不可缺少的科研、工作、生活和娱乐的重要手段不可缺少的科研、工作、生活和娱乐的重要手段 和工具，人们所使用的工具影响着我们的思维方和工具，人们所使用的工具影响着我们的思维方 式和思维习惯式和思维习惯,从而也将深刻地影响着我们的思维从而也将深刻地影响着我们的思维 能力，计算思维成为每个人必须掌握的基本技能。能力，计算思维成为每个人必须掌握的基

2、本技能。 学习完本章以后，你将能够：学习完本章以后，你将能够： 了解计算工具的发展；了解计算工具的发展； 了解计算模型了解计算模型图灵机、冯图灵机、冯诺依曼模型诺依曼模型 ； 了解计算与计算科学；了解计算与计算科学； 了解计算思维了解计算思维 在漫长的人类进化和文明发展过程中，人类的大脑逐渐具有了一在漫长的人类进化和文明发展过程中，人类的大脑逐渐具有了一 种特殊的本领，这就是把直观的形象变成抽象的数字，进行抽象思种特殊的本领，这就是把直观的形象变成抽象的数字，进行抽象思 维活动。正是由于能够在维活动。正是由于能够在“象象”和和“数数”之间互相转换，人类才真之间互相转换，人类才真 正具备了认识世

3、界的能力。正具备了认识世界的能力。 自从人类有了自从人类有了“数数”的概念便开始进行计算，计算技术发展的历的概念便开始进行计算，计算技术发展的历 史是人类文明史的一个缩影。为了提高计算的效率，计算需要借助史是人类文明史的一个缩影。为了提高计算的效率，计算需要借助 一定的工具以及与工具相匹配的计算方法来进行。一定的工具以及与工具相匹配的计算方法来进行。 人类最初的计算工具就是人类的双手，掰指头算数就是最早的计人类最初的计算工具就是人类的双手，掰指头算数就是最早的计 算方法，远古时代人们采用石块、贝壳进行简单的计数，到中国古算方法，远古时代人们采用石块、贝壳进行简单的计数，到中国古 代发明的算筹计

4、算、算盘计算，到欧洲近代发明的加法计算器、分代发明的算筹计算、算盘计算，到欧洲近代发明的加法计算器、分 析机，直到今天的电子计算机，计算工具及计算方法的发展与创新析机，直到今天的电子计算机，计算工具及计算方法的发展与创新 在人类文明发展史上占有重要的地位。在人类文明发展史上占有重要的地位。 1.1.1 手工计算工具手工计算工具 l算筹算筹 l算盘算盘 l计算尺计算尺 1.1.2 机械式计算机机械式计算机 1计算机器计算机器帕斯卡加法器、莱布尼茨乘法器帕斯卡加法器、莱布尼茨乘法器 帕斯卡加法器帕斯卡加法器 莱布尼茨乘法器莱布尼茨乘法器 1.1.2 机械式计算机机械式计算机 2程序的概念程序的概念

5、提花编织机提花编织机 帕斯卡以及莱布尼茨发明的机器都没有程序控制帕斯卡以及莱布尼茨发明的机器都没有程序控制 功能。功能。在工业社会，第一次大规模应用程序控制的机在工业社会，第一次大规模应用程序控制的机 器并不是计算机，而是纺织行业里的提花编织机。器并不是计算机，而是纺织行业里的提花编织机。 1725年，法国纺织机械师布乔（年，法国纺织机械师布乔（B. Bouchon） 发明了发明了“穿孔纸带穿孔纸带”的构想。的构想。1805年法国纺织机械年法国纺织机械 师约瑟夫师约瑟夫杰卡德（杰卡德（J.Jacquard）根据布乔）根据布乔“穿孔纸穿孔纸 带带”的构想完成了的构想完成了“自动提花编织机自动提花

6、编织机”的设计制作。的设计制作。 3自动计算的梦想自动计算的梦想巴贝奇的差分机与分析机巴贝奇的差分机与分析机 1822年，巴贝奇制造出第一台差分机，年，巴贝奇制造出第一台差分机， 这台机器可以处理三个不同的五位数，其这台机器可以处理三个不同的五位数，其 计算精度达到了六位小数，可在极短时间计算精度达到了六位小数，可在极短时间 内演算出若干种函数表。内演算出若干种函数表。 1.1.2 机械式计算机机械式计算机 分析机不但含有齿轮式分析机不但含有齿轮式“存储仓库存储仓库”和和“运算室运算室”，而，而 且还有一种且还有一种“控制器控制器”装置，以及在装置，以及在“存储仓库存储仓库”和和“运运 算室算

7、室”之间进行数据运输的输入、输出零件。巴贝奇分析之间进行数据运输的输入、输出零件。巴贝奇分析 机具备类似于现代计算机五大部件的逻辑结构。机具备类似于现代计算机五大部件的逻辑结构。 所谓差分，即把函数表的复杂运算转换为差分运算，用所谓差分，即把函数表的复杂运算转换为差分运算，用 简单的加法运算替代平方运算，并快速编制出不同函数简单的加法运算替代平方运算，并快速编制出不同函数 的数学用表。所以差分机只能完成特定的函数表的计算。的数学用表。所以差分机只能完成特定的函数表的计算。 1.1.3 电子计算机电子计算机 1946年年2月，美国宾夕法尼亚大学莫尔学院的莫克利和埃月，美国宾夕法尼亚大学莫尔学院的

8、莫克利和埃 克特，研制成功了大型通用数字电子计算机克特，研制成功了大型通用数字电子计算机ENIAC（爱尼（爱尼 亚克）亚克）。 这台计算机仍然采用外加式程序，这台计算机仍然采用外加式程序，ENIAC并没有在存储器并没有在存储器 中存储程序，如果让这些计算机执行一项新的任务，就必中存储程序，如果让这些计算机执行一项新的任务，就必 须相应修改其线路及通过手动装置修改电缆和开关，须相应修改其线路及通过手动装置修改电缆和开关， ENIAC尚未完全具备现代计算机的主要特征。尚未完全具备现代计算机的主要特征。 1949年，英国剑桥大学数学实验室率先研制成功年，英国剑桥大学数学实验室率先研制成功EDSAC

9、(电子离散时序自动计算机电子离散时序自动计算机)。 1951年冯年冯诺依曼主持的诺依曼主持的 EDVAC 计算机计算机宣告完成。至此，宣告完成。至此， 电子计算机发展的萌芽时期遂告结束，开始了现代计算机电子计算机发展的萌芽时期遂告结束，开始了现代计算机 的发展时期。的发展时期。 让计算机处理某项任务其实就是执行存储让计算机处理某项任务其实就是执行存储 在计算机存储器中的应用程序，处理不同的在计算机存储器中的应用程序，处理不同的 问题需要运行不同的程序。现代计算机是如问题需要运行不同的程序。现代计算机是如 何实现高效的自动计算？其运行原理是什么？何实现高效的自动计算？其运行原理是什么？ 从从18

10、世纪开始人类就开始追求实现世纪开始人类就开始追求实现自动自动 计算的梦想计算的梦想，关于自动计算的理论，关于自动计算的理论20世纪取世纪取 得突破性的成果，为现代计算机的诞生和飞得突破性的成果，为现代计算机的诞生和飞 速发展奠定了坚实的基础。速发展奠定了坚实的基础。 1.2.1 1.2.1 图灵机图灵机 1900年，著名的大数学家希尔伯 特在世纪之交的数学家大会上给 国际数学界提出了著名的23个数 学问题。其中第十问题是这样的： 存在不存在一种有限的、机械的 步骤能够判断“丢番图方程”是 否存在解？ 这里的关键是这里的关键是“有限的、机械的步骤有限的、机械的步骤”，通俗的理解这，通俗的理解这

11、个问题，那就是是否可能设计出一套个问题，那就是是否可能设计出一套“有限的、机械的有限的、机械的 步骤步骤”，可以让一个人在完全不理解，可以让一个人在完全不理解“丢番图方程丢番图方程”的的 人按照这个人按照这个“有限的、机械的步骤有限的、机械的步骤”的步骤判断的步骤判断“丢番丢番 图方程图方程”是否存在解？是否存在解？ 1.2.1 1.2.1 图灵机图灵机 如果一个人完全不理解如果一个人完全不理解 问题的本质，仅仅按某问题的本质，仅仅按某 种种简单、有限、机械的简单、有限、机械的 步骤步骤就能解决复杂的问就能解决复杂的问 题，那么我们就有可能题，那么我们就有可能 设计并制造出某种灵巧设计并制造出

12、某种灵巧 的机器去代替人类去解的机器去代替人类去解 决各种需要人类智力和决各种需要人类智力和 知识的问题。知识的问题。 英国数学家英国数学家阿兰阿兰图灵图灵19361936年年 发表的著名论文发表的著名论文“论可计算数在论可计算数在 判定问题中的应用判定问题中的应用”， 奠定了现奠定了现 代计算机的理论基础。代计算机的理论基础。 图灵用的图灵机模型精确定义图灵用的图灵机模型精确定义 了了“有限的、机械的步骤有限的、机械的步骤” 这样这样 一个基本的、深刻的计算概念；一个基本的、深刻的计算概念； 提出了现代计算机的基本原提出了现代计算机的基本原 理理在机器存储器中存储编码在机器存储器中存储编码

13、指令程序来控制机器操作。指令程序来控制机器操作。 图灵的基本思想是用机器来模拟人们用纸笔进行图灵的基本思想是用机器来模拟人们用纸笔进行 计算的过程，他把过程看作下列两种简单的动作：计算的过程，他把过程看作下列两种简单的动作： （1）在纸上写上或擦除某个符号；（）在纸上写上或擦除某个符号；（2）把注意力）把注意力 从纸的一个位置移动到另一个位置；在每个阶段，从纸的一个位置移动到另一个位置；在每个阶段， 人要决定下一步的动作，依赖于此人当前所关注的人要决定下一步的动作，依赖于此人当前所关注的 纸上某个位置的符号和此人当前思维的状态。纸上某个位置的符号和此人当前思维的状态。 图灵机由以下几个部分组成

14、：图灵机由以下几个部分组成： 一条无限长的纸带。纸带被划分为一个接一个的小格子，一条无限长的纸带。纸带被划分为一个接一个的小格子， 每个格子上包含一个来自有限字母表的符号，字母表中有每个格子上包含一个来自有限字母表的符号，字母表中有 一个特殊的符号表示空白。纸带上的格子从左到右依次被一个特殊的符号表示空白。纸带上的格子从左到右依次被 编号为编号为0, 1, 2, .，纸带的右端可以无限伸展。，纸带的右端可以无限伸展。 一个读写头。该读写头可以在纸带上左右移动，它能读出当一个读写头。该读写头可以在纸带上左右移动，它能读出当 前所指的格子上的符号，并能改变当前格子上的符号。前所指的格子上的符号，并

15、能改变当前格子上的符号。 一个控制器。控制器包含一套控制规则和一个状态寄存器，一个控制器。控制器包含一套控制规则和一个状态寄存器， 控制规则根据当前机器所处的状态以及当前读写头所指的格控制规则根据当前机器所处的状态以及当前读写头所指的格 子上的符号来确定读写头下一步的动作，并改变状态寄存器子上的符号来确定读写头下一步的动作，并改变状态寄存器 的值，令机器进入一个新的状态。的值，令机器进入一个新的状态。 状态寄存器用来保存图灵状态寄存器用来保存图灵 机当前所处的状态。图灵机的所有可能状态的数目是有限的，机当前所处的状态。图灵机的所有可能状态的数目是有限的， 并且有一个特殊的状态，称为停机状态。并

16、且有一个特殊的状态，称为停机状态。 这个机器的每一部分都是有限的，但这个机器的每一部分都是有限的，但 它有一个潜在的无限长的纸带，因此它有一个潜在的无限长的纸带，因此 这种机器只是一个理想的设备。这种机器只是一个理想的设备。 2.图灵机的基本操作图灵机的基本操作 图灵机的基本操作：图灵机的基本操作： (1)读写头在纸带上读出一个方格的信息；读写头在纸带上读出一个方格的信息； (2)根据它当前的内部状态和读出信息，对控制规则根据它当前的内部状态和读出信息，对控制规则 进行查表，得出一个输出动作（是否往纸带上写进行查表，得出一个输出动作（是否往纸带上写 信息，读写头如何动作，下一时刻内部状态转移信

17、息，读写头如何动作，下一时刻内部状态转移 到哪一个）；到哪一个）； (3)执行查表得到的输出动作。执行查表得到的输出动作。 3图灵机的简单案例图灵机的简单案例 为了讨论方便假设纸带中数据用为了讨论方便假设纸带中数据用“一进制一进制”表示正整数，正整数由表示正整数，正整数由 “1”组成，如整数组成，如整数5表示为表示为11111（5个个1），整数），整数7表示为表示为1111111 （7个个1）。）。 例例1：计算计算X+1的图灵机，即输入正整数的图灵机，即输入正整数X，该台图灵机输出，该台图灵机输出X+1。 为了执行这个任务，图灵机使用了分别标识为为了执行这个任务，图灵机使用了分别标识为S1、

18、S2、S3、S4的的 四个状态，四个状态， S1表示开始状态、表示开始状态、S2表示右移状态、表示右移状态、S3表示左移状态、表示左移状态、 S4表示停机状态。其控制规则（程序）如下表所示。表示停机状态。其控制规则（程序）如下表所示。 当前状态当前状态读读写写移动移动下一个状态下一个状态 S1S10 00 0R R（右移）（右移）S2S2 S2S21 11 1R R（右移）（右移）S2S2 S2S20 01 1L L（左移）（左移）S3S3 S3S31 11 1L L（左移）（左移）S3S3 S3S30 00 0NN（不动）（不动）S4S4 假设假设X+1X+1图灵机从如右图所图灵机从如右图所

19、 示的情形开始计算（示的情形开始计算（X X为为3 3） (1)(1)当前状态为当前状态为S1S1，读写头读入，读写头读入 “0 0”； (2) (2) 根据状态根据状态S1S1和读入信息和读入信息“0 0”， 通过查表找到与其匹配的规则通过查表找到与其匹配的规则 （S1S1、0 0、0 0、R R、S2S2），得到输），得到输 出动作；出动作； (3) (3) 控制器控制读写头在当前格控制器控制读写头在当前格 子写下子写下“0 0”并右移一格，同时并右移一格，同时 将状态寄存器的状态改为将状态寄存器的状态改为S2S2。 X+1图灵机计算图灵机计算3+1的计算过程的计算过程 例例2 2：用于计

20、算用于计算X-1X-1的图灵机。的图灵机。 输入正整数输入正整数X，该台图灵机输出，该台图灵机输出X-1。为了执行这个任。为了执行这个任 务，图灵机使用了分别标识为务，图灵机使用了分别标识为S1、S4、S5的三个状态，的三个状态， S1表示开始状态，表示开始状态，S4表示停机状态，表示停机状态，S5表示检查状态。表示检查状态。 其控制规则（程序）如下表所示。其控制规则（程序）如下表所示。 当前状态当前状态读读写写移动移动下一个状态下一个状态 S1S10 00 0R R（右移）（右移）S5S5 S5S50 00 0NN（不动）（不动）S4S4 S5S51 10 0NN（不动）（不动）S4S4 X

21、-1X-1图灵机的控制规则（程序）图灵机的控制规则（程序） 用用X-1图灵机计算图灵机计算3-1的计算过程如下图所示：的计算过程如下图所示： 图灵机的组成和操作是如图灵机的组成和操作是如 此的简单，它可以用于解此的简单，它可以用于解 决复杂问题吗？。决复杂问题吗？。 前面的图灵机是以简化的前提开始的，所以它很简单。但前面的图灵机是以简化的前提开始的，所以它很简单。但 是，我们可以把图灵机纸带中数据的表示方式、规则（指是，我们可以把图灵机纸带中数据的表示方式、规则（指 令）集合、内部状态集合进行扩展，这个模型就可以处理令）集合、内部状态集合进行扩展，这个模型就可以处理 复杂得多的问题。复杂得多的

22、问题。 我们还可以通过组合若干图灵机完成更大更多的计算，如我们还可以通过组合若干图灵机完成更大更多的计算，如 果把一个图灵机对纸带信息变换的结果输入给另一台图灵果把一个图灵机对纸带信息变换的结果输入给另一台图灵 机，然后再输入给别的图灵机机，然后再输入给别的图灵机，这就是计算的组合。，这就是计算的组合。 实际上我们并不需要写出无限复杂的程序列表，只要将这实际上我们并不需要写出无限复杂的程序列表，只要将这 些图灵机组合到一起就可以产生复杂的行为。有了图灵机些图灵机组合到一起就可以产生复杂的行为。有了图灵机 的组合，我们就能够从最简单的图灵机开始构造复杂的图的组合，我们就能够从最简单的图灵机开始构

23、造复杂的图 灵机。灵机。 通过简单的计算组合成复杂的计算系统，是通过简单的计算组合成复杂的计算系统，是“运用计算运用计算 的基础概念进行问题求解、系统设计、以及人类行为理解的基础概念进行问题求解、系统设计、以及人类行为理解” 最重要的思维方法。最重要的思维方法。 在构建功能简单的在构建功能简单的X+1X+1和和X-1X-1的图灵机的基础上，讨论的图灵机的基础上，讨论 用这两个简单的图灵机组合出处理复杂计算的系统的方法，用这两个简单的图灵机组合出处理复杂计算的系统的方法， 为此引入为此引入“循环循环”的概念。运用的概念。运用“循环循环”可以把可以把X+1X+1、X-1X-1 的模型组合出计算的模

24、型组合出计算X+YX+Y的图灵机，其处理机制如下图所示。的图灵机，其处理机制如下图所示。 计算计算X+YX+Y图灵机的处理机制图灵机的处理机制 实现实现X-1X-1，Y+1Y+1和循环，就可以在此基础上实现和循环，就可以在此基础上实现X+YX+Y， 同样的实现了同样的实现了X+YX+Y就能以此为基础上通过就能以此为基础上通过X X个个Y Y的连加的连加 实现实现X XY Y。从理论上可以证明，。从理论上可以证明，只要能实现只要能实现X+1X+1，X-X- 1 1和循环，我们就能构造出和现有任何的计算机一样和循环，我们就能构造出和现有任何的计算机一样 强大的能处理各种复杂问题的图灵机模型。强大的

25、能处理各种复杂问题的图灵机模型。 有了图灵机的组合，我们就能够从最简单的图灵机开有了图灵机的组合，我们就能够从最简单的图灵机开 始构造复杂的图灵机。那么最简单的图灵机是什么呢？始构造复杂的图灵机。那么最简单的图灵机是什么呢？ 最简单的信息就是最简单的信息就是0 0和和1 1，而最简单的计算就是对，而最简单的计算就是对0 0或或1 1 进行布尔运算。进行布尔运算。 以最简单的图灵机为起点，通过不断的组合，居然以最简单的图灵机为起点，通过不断的组合，居然 能构造出解决任意可以用能构造出解决任意可以用“有限的、机械的步骤有限的、机械的步骤” （算法）处理的图灵机，这充分体现了图灵机模型的（算法）处理

26、的图灵机，这充分体现了图灵机模型的 强大处理能力。强大处理能力。 4.4.通用图灵机通用图灵机 X+1 X+1和和X-1X-1是两台不同的图灵机。对于任意一个图灵机，是两台不同的图灵机。对于任意一个图灵机， 因为它的描述状态和控制规则是有限的，因此可以用某种方因为它的描述状态和控制规则是有限的，因此可以用某种方 式将其编码为字符串，假设用式将其编码为字符串，假设用M(X+1)M(X+1)表示表示X+1X+1图灵机，用图灵机，用 M(X-1)M(X-1)表示表示X-1X-1图灵机，那么图灵机，那么能否设计出一种能否设计出一种“通用图灵通用图灵 机机”，当输入，当输入M(X+1)M(X+1)和和3

27、 3时时“通用图灵机通用图灵机”将输出将输出4 4，如果，如果 输入输入M(X-1)M(X-1)和和3 3，则通用图灵机输出，则通用图灵机输出2 2。仅仅通过改变输入。仅仅通过改变输入X X 和和MM的值就能的值就能“改变改变”通用图灵机的程序规则。通用图灵机的程序规则。 阿兰阿兰图灵证明了通用图灵机的可行性。图灵证明，通过图灵证明了通用图灵机的可行性。图灵证明，通过 在机器的存储器（图灵机中的纸带）中存储一系列指令程序在机器的存储器（图灵机中的纸带）中存储一系列指令程序 ( (符号或数字编码符号或数字编码) )来控制计算机器，一台固定结构的计算机器来控制计算机器，一台固定结构的计算机器 能够

28、执行无论哪一种图灵机所能执行的每一个计算。能够执行无论哪一种图灵机所能执行的每一个计算。 1.2.2 1.2.2 冯冯诺依曼模型诺依曼模型 如果说阿兰如果说阿兰图灵为现代计算机奠定图灵为现代计算机奠定 了理论基础，那么冯了理论基础，那么冯诺依曼则为现诺依曼则为现 代计算机的实现做出了杰出的贡献。代计算机的实现做出了杰出的贡献。 1. 1.存储程序通用电子计算机方案存储程序通用电子计算机方案 19451945年年6 6月，冯月，冯诺依曼与戈德斯坦、勃克斯等人，联诺依曼与戈德斯坦、勃克斯等人，联 名发表了一篇长达名发表了一篇长达101101页纸的报告页纸的报告存储程序通用电存储程序通用电 子计算机

29、方案子计算机方案-EDVAC-EDVAC。冯。冯诺依曼在报告中阐述诺依曼在报告中阐述 的基本思想如下：的基本思想如下： 1.2.2 1.2.2 冯冯诺依曼模型诺依曼模型 2. 2. 冯冯诺依曼计算机模型诺依曼计算机模型 冯冯诺依曼计算机模型包含以下三个重要的设计思想：诺依曼计算机模型包含以下三个重要的设计思想： 3.3.冯冯诺依曼计算机结构诺依曼计算机结构 数据流数据流 控制流控制流 取数 存数 地址 指令 （ 控制器控制器 运算器运算器 输出输出 设备设备 输入输入 设备设备 程序+ 数 据 操作命令 处理 结果 反馈信号 响应信号 请求信号 响应信号 请求信号 1 1 2 2 3 3 4

30、4 5 5 6 6 7 7 8 89 9 1010 11 11 1212 1313 1414 注意：其中注意：其中5-105-10是个是个 重复的过程重复的过程 运算器也称算术运算器也称算术 逻辑单元逻辑单元 （ALUALU），是计），是计 算机进行算术运算机进行算术运 算和逻辑运算的算和逻辑运算的 部件。部件。 控制器主要用来控制程序和数据的输入控制器主要用来控制程序和数据的输入/ /输出，以及各个部件之间的协调运行。输出，以及各个部件之间的协调运行。 1.3 1.3 计算科学与计算思维计算科学与计算思维 1.3.1 计算与计算科学计算与计算科学 1. 计算的概念计算的概念 如果我们把一切都

31、看作是信息，对包罗万象的如果我们把一切都看作是信息，对包罗万象的 计算加以抽象，那么计算就是对信息的变换，是某个计算加以抽象，那么计算就是对信息的变换，是某个 系统完成了一次从输入到输出的变换。系统完成了一次从输入到输出的变换。 例例3 3：三对情侣参加婚礼，三个新郎为三对情侣参加婚礼，三个新郎为A A，B B，C C，三个，三个 新娘为新娘为X X，Y Y，Z Z，有人想知道究竟谁和谁结婚，于是就问，有人想知道究竟谁和谁结婚，于是就问 新人中的三位，得到如下的提示：新人中的三位，得到如下的提示：A A说他将和说他将和X X结婚；结婚；X X说说 她的未婚夫是她的未婚夫是C C；C C说他将和

32、说他将和Z Z结婚。这人事后知道他们在结婚。这人事后知道他们在 开玩笑，说的全是假话，那么究竟谁与谁结婚呢？开玩笑，说的全是假话，那么究竟谁与谁结婚呢？ 解：解： 步骤步骤1：找出所有可能的新人配对：找出所有可能的新人配对,共共6组：组： (A,X)、(B,Y)、(C,Z) (A,X)、(B,Z)、(C,Y) (A,Y)、(B,X)、(C,Z) (A,Y)、(B,Z)、(C,X) (A,Z)、 (B,X) 、(C,Y) (A,Z)、(B,Y)、(C,X) 步骤步骤2：由输入信息：由输入信息A不和不和X结结 婚婚, C不和不和Z结婚结婚, C不和不和X 结婚。所以结婚。所以 结论：这三对新人中结

33、论：这三对新人中A A和和Z Z结结 婚，婚，B B和和X X结婚，结婚，C C和和Y Y结婚。结婚。 (A,X) (C,Z) (C,X) 不可能结婚，将不可能结婚，将6组配组配 对中包含上述组合的组去对中包含上述组合的组去 掉，可得到正确的配对是掉，可得到正确的配对是 （第（第5组）。组）。 如果有如果有100100对新人、对新人、 10001000对新人对新人 呢？呢？ 2.2.计算科学计算科学 我们能否找到我们能否找到“偷懒偷懒”的办法，构建的办法，构建 一个系统自动地计算出上述问题的结一个系统自动地计算出上述问题的结 果？果？ 如果我们希望构建的系统除了自动地计算上述问如果我们希望构建

34、的系统除了自动地计算上述问 题外，只要通过方便的方式把处理步骤置入系统，题外，只要通过方便的方式把处理步骤置入系统， 这个计算工具还能自动地计算其他更复杂的计算这个计算工具还能自动地计算其他更复杂的计算 问题，我们该如何构建这样的通用系统？问题，我们该如何构建这样的通用系统？ 如果能构建这样的系统，那么应该如何使系统如果能构建这样的系统，那么应该如何使系统 的计算效率更高、使用更方便、更安全可靠？的计算效率更高、使用更方便、更安全可靠？ 如果很多人都拥有这样的系统，我们应该如何如果很多人都拥有这样的系统，我们应该如何 共享资源？共享资源？ 2.2.计算科学计算科学 计算科学是计算的学问计算科学

35、是计算的学问什么是可自动计算的，什么是可自动计算的， 怎样去自动计算。怎样去自动计算。 计算科学计算科学 系统领域系统领域 应用领域应用领域 计算机体系结构、计算机网络计算机体系结构、计算机网络 安全问题、操作系统、算法、安全问题、操作系统、算法、 程序设计语言以及软件工程程序设计语言以及软件工程 涵盖了与计算机使用有关的领涵盖了与计算机使用有关的领 域，如数据库和人工智能。域，如数据库和人工智能。 2.2.计算科学计算科学 算法算法是一组有序的、无歧义的、可执行的步骤的是一组有序的、无歧义的、可执行的步骤的 集合，定义了一个解决某一特定类型问题的可终集合，定义了一个解决某一特定类型问题的可终

36、 止的运算序列。止的运算序列。 用计算机能够理解的规定格式（编程语言）将算用计算机能够理解的规定格式（编程语言）将算 法表示出来，并将其输入到计算机中，这种算法法表示出来，并将其输入到计算机中，这种算法 表示称作表示称作程序程序，这样的过程称之为，这样的过程称之为程序设计程序设计。 程序及其所表示的算法总称为程序及其所表示的算法总称为软件软件，而计算机设，而计算机设 备本身称为备本身称为硬件硬件。 1.3.2 1.3.2 计算科学的几个研究热点计算科学的几个研究热点 1.人工智能人工智能 人工智能是指由人工制造出来的系统所表现出人工智能是指由人工制造出来的系统所表现出 来的智能，通常人工智能是

37、指通过普通计算机实现来的智能，通常人工智能是指通过普通计算机实现 的智能。的智能。 人工智能主要研究领域人工智能主要研究领域 ： （1）机器学习）机器学习 （2）自然语言理解）自然语言理解 （3）专家系统）专家系统 （4）模式识别）模式识别 （5）计算机视觉）计算机视觉 （6）机器人学）机器人学 （7）自动定理证明）自动定理证明 2.云计算云计算 云计算将网络上分布的计算、存储、服务构件、云计算将网络上分布的计算、存储、服务构件、 网络软件等资源集中起来，基于资源虚拟化的方式，网络软件等资源集中起来，基于资源虚拟化的方式， 为用户提供方便快捷的服务，它可以实现计算与存为用户提供方便快捷的服务，

38、它可以实现计算与存 储的分布式与并行处理。储的分布式与并行处理。 云计算是一种通过云计算是一种通过Internet以服务的方式提供动以服务的方式提供动 态可伸缩的虚拟化的资源的计算模式。态可伸缩的虚拟化的资源的计算模式。 2. 普适计算普适计算 普适计算又称普存计算、普及计算（普适计算又称普存计算、普及计算（pervasive computing 或者或者Ubiquitous computing）这一概念强调和环境融为一）这一概念强调和环境融为一 体的计算，而计算机本身则从人们的视线里消失。在普适计体的计算，而计算机本身则从人们的视线里消失。在普适计 算的模式下，人们能够在任何时间、任何地点、

39、以任何方式算的模式下，人们能够在任何时间、任何地点、以任何方式 进行信息的获取与处理。进行信息的获取与处理。 普适计算的本质在于新的计算模式以及与之相适应的人机交普适计算的本质在于新的计算模式以及与之相适应的人机交 互方式。互方式。 普适计算环境由普适计算设备、系统软件及其网络等部分构成。普适计算环境由普适计算设备、系统软件及其网络等部分构成。 其中普适计算设备根据功能不同可以分为其中普适计算设备根据功能不同可以分为信息访问终端信息访问终端、感知感知 设备设备、智能物体智能物体等。等。 传感器传感器、智能灰智能灰 尘、照相机、摄尘、照相机、摄 像机等像机等 家具、家电、家具、家电、 咖啡杯等咖

40、啡杯等 PDA2PDA2、PCPC、 智能手机、智能手机、 网络计算机网络计算机 等等 1.3.3 1.3.3 计算思维计算思维 计算思维是运用计算科学的基础概念进行问题求解、系计算思维是运用计算科学的基础概念进行问题求解、系 统设计、以及人类行为理解的一系列思维活动。统设计、以及人类行为理解的一系列思维活动。 计算和自然语言一样，都是人类社会每时每刻离不开的工具。计算和自然语言一样，都是人类社会每时每刻离不开的工具。 随着云计算和普适计算等计算模式的出现和逐步实现，计算随着云计算和普适计算等计算模式的出现和逐步实现，计算 将融入我们的生活，计算机成为像空气、水电一样的生活必将融入我们的生活，

41、计算机成为像空气、水电一样的生活必 需品，计算机已经深深地影响我们的处理问题和思考问题的需品，计算机已经深深地影响我们的处理问题和思考问题的 方式。方式。 美国卡内基美国卡内基梅隆大学计算机科学系主任周以真提出，当计算梅隆大学计算机科学系主任周以真提出，当计算 机成为人们生活和工作不可或缺的工具时，机成为人们生活和工作不可或缺的工具时，“计算思维是每计算思维是每 个人的基本技能，不仅仅属于计算机科学家。我们在培养解个人的基本技能，不仅仅属于计算机科学家。我们在培养解 析能力时，不仅需要掌握阅读、写作和算术，还要学会计算析能力时，不仅需要掌握阅读、写作和算术，还要学会计算 思维思维”。 本章导读

42、本章导读 计算机的信息处理过程包含信息的输入、信息的计算机的信息处理过程包含信息的输入、信息的 存储与处理、信息的输出三个基本步骤，其中信息的存储与处理、信息的输出三个基本步骤，其中信息的 表示和组织是信息处理的基础。早期的计算机机处理表示和组织是信息处理的基础。早期的计算机机处理 的主要是数字和文本数据，现在计算机可以存储、表的主要是数字和文本数据，现在计算机可以存储、表 示和帮助我们处理各种类型的信息，包括：数字、文示和帮助我们处理各种类型的信息，包括：数字、文 本、音频、图像和图形、视频。这些丰富的信息在计本、音频、图像和图形、视频。这些丰富的信息在计 算机内是如何表示和处理的呢？本章主

43、要介绍信息及算机内是如何表示和处理的呢？本章主要介绍信息及 其表示方法、信息处理的硬件基础和数据的存储与操其表示方法、信息处理的硬件基础和数据的存储与操 作。作。 内容介绍内容介绍 学习完本章以后，你将能够：学习完本章以后，你将能够： 了解信息和信息的表示了解信息和信息的表示 了解布尔代数和门电路了解布尔代数和门电路 了解数据的存储了解数据的存储 了解中央处理单元了解中央处理单元 了解机器指令和程序运行过程了解机器指令和程序运行过程 2.1 2.1 信息和信息的表示方法信息和信息的表示方法 2.1.1 信息和信息的表示信息和信息的表示 信息就是对客观事物的反映。从本质上看信息是对信息就是对客观

44、事物的反映。从本质上看信息是对 社会、自然界的事物特征、现象、本质及规律的描社会、自然界的事物特征、现象、本质及规律的描 述。述。 信息所描述的内容通过某种载体如符号、声音、文信息所描述的内容通过某种载体如符号、声音、文 字、图形、图像等来表示。字、图形、图像等来表示。 “信息所描述的内容信息所描述的内容”以及以及“信息的表示方式信息的表示方式”是有是有 区别的，相同的信息内容可以用不同的信息表示方式。区别的，相同的信息内容可以用不同的信息表示方式。 高兴的心情高兴的心情 信息内信息内 容容 汉语汉语“开心开心”、 英语英语“happyhappy” 图像图像 信息表示信息表示 方式方式 为了有

45、效地进行信息的传递、存储和处理，需要为了有效地进行信息的传递、存储和处理，需要 建立一套信息的表示系统，对信息进行编码。建立一套信息的表示系统，对信息进行编码。 信息编码（信息编码（Information Coding）是为了方便信）是为了方便信 息的存储、检索和使用，在进行信息处理时赋予息的存储、检索和使用，在进行信息处理时赋予 信息元素以代码的过程。即用不同的代码与各种信息元素以代码的过程。即用不同的代码与各种 信息中的基本单位组成部分建立一一对应的关系。信息中的基本单位组成部分建立一一对应的关系。 文字实际上就是一种编码系统，以中文汉字为例，文字实际上就是一种编码系统，以中文汉字为例，

46、我们使用的文字非常多我们使用的文字非常多,但这么多的汉字就书写而言，但这么多的汉字就书写而言， 基本组成部分笔画只有基本组成部分笔画只有28种（如图种（如图2-1所示），用所示），用 这这28个基本笔画的不同组合就能编码复杂的中文汉个基本笔画的不同组合就能编码复杂的中文汉 字系统。字系统。 图图2-1 2-1 常用汉字笔画常用汉字笔画 现代计算机广泛使用二进制的信息表示方式。香农教授现代计算机广泛使用二进制的信息表示方式。香农教授 在在1948年首次指出，年首次指出，通信的基本信息单元是符号，而最通信的基本信息单元是符号，而最 基本的信息符号是二值符号，基本的信息符号是二值符号，“1”或或“0

47、”代表了两种状代表了两种状 态。态。 度量信息可以从这种基本的分析入手，信息的最小单位度量信息可以从这种基本的分析入手，信息的最小单位 是对一个命题真、假的判断，某条是对一个命题真、假的判断，某条线路的线路的“接通接通”或或 “断开断开”等物理状态也有两种可能状态等物理状态也有两种可能状态，它们都可以用，它们都可以用 来表示二值符号。他把这个信息的最小单位称为比特来表示二值符号。他把这个信息的最小单位称为比特(b)。 比特是度量信息的基本单位。比特是度量信息的基本单位。任何复杂信息皆可以根据任何复杂信息皆可以根据 其结构和内容，按照一定的编码规则被分割为更简单的其结构和内容，按照一定的编码规则

48、被分割为更简单的 成分，一直分割到最小的信息单位，最终被变换为一组成分，一直分割到最小的信息单位，最终被变换为一组 由由“0”和和“1”组成的二值数据。组成的二值数据。 信息的二值形式被称为它们的信息的二值形式被称为它们的“二进制编码二进制编码”，或称为，或称为 “二进制表示二进制表示”。这种信息的。这种信息的“二进制编码二进制编码”方法通常方法通常 称为称为“信息的数字编码方法信息的数字编码方法”，或简称为，或简称为“数字化方数字化方 法法”。 2.1.2 2.1.2 进位计数制和数的表示进位计数制和数的表示 数制也称计数制度，是指用一组固定的符号和统一数制也称计数制度，是指用一组固定的符号

49、和统一 的规则来表示数值的方法。的规则来表示数值的方法。 一般情况下，人们习惯于用十进制来表示数，即用一般情况下，人们习惯于用十进制来表示数，即用 0 0、1 1、2 2、3 3、4 4、5 5、6 6、7 7、8 8、9 9这十个符号的规则这十个符号的规则 使用来表达数。这是因为人类有十个手指，而我们的使用来表达数。这是因为人类有十个手指，而我们的 祖先，乃至我们自己，学会计数是从数手指开始的，祖先，乃至我们自己，学会计数是从数手指开始的， 正所谓正所谓“屈指可数屈指可数”。 然而，我们能不能用然而，我们能不能用0 0和和1 1这两个数来表达数？还这两个数来表达数？还 有没有其它方式来表达数

50、？有没有其它方式来表达数？ 古人放羊用卵石来计古人放羊用卵石来计 算羊的数量（大于算羊的数量（大于1010 只用一个卵石）只用一个卵石） 1. 1. 十进制数和二进制数十进制数和二进制数 为了更好地理解数制，我们看一个简单地示例。如为了更好地理解数制，我们看一个简单地示例。如 何对图何对图2-22-2中的麋鹿用十进制进行计数呢？中的麋鹿用十进制进行计数呢？ 麋鹿数量麋鹿数量2323 是怎么得来是怎么得来 的？的？ 十进制的麋鹿计数过程如图十进制的麋鹿计数过程如图2-32-3所示。所示。 图图2-2 2-2 草原上的麋鹿草原上的麋鹿 图图2-3 2-3 十进制的麋鹿计数过程十进制的麋鹿计数过程