计算科学导论

1、计 算 科 学 导 论主要内容计算机基础知识计算科学的基本概念和基本知识计算科学的意义、内容和方法计算科学教学计划与课程体系布尔代数基础第一部分 计算机基础知识计算机的历史与发展计算机的基本原理、计算机结构计算机的基本使用计算机的抽象模型和基本问题引 言我们生活的环境越来越信息化。工作/生活对人处理信息的能力提出更高要求：运用各种通信交流手段，通过媒体收集发送有用信息，运用计算机等信息处理工具挑选有价值的材料并将其改造成适用的形式等。从事任何工作，都会感到信息社会的挑战，看到计算机的巨大作用。计算机正在越来越深入地渗透到日常生活的每一个角落。学习掌握计算机和信息技术，理解其原理和工作方式，对每

2、个大学生都是最基本的。作为一名计算机科学专业的学生，更应熟练掌握计算机的各种软硬件技术及相应学科知识。现代计算机的历史始于20世纪40年代后期。一般认为第一台真正意义下的计算机是1946年在美国宾夕法尼亚大学诞生的名为 ENIAC（Electronic Numerical Integrator and Computer，读为“爱尼亚克”）的计算机。计算机诞生并不是一个孤立事件，它是人类文明史的必然产物，是长期客观需求和技术准备的产物。 计算机发展简史史前时代计算机是一种机器，是人发明的一种工具。与人类发明创造的其他工具有根本性差别。工具大多可以看作是手脚的延伸，完成的是人们原本需要耗费体力去完

3、成的事情。而计算机则可以看作是人头脑的延伸，能帮人做原本需要耗费人的脑力完成的事情。计算机的诞生，从历史上可以找到多方面的原因和前期准备工作。主要包括几个方面：一、人类对计算工具的需求和早期开发。人类文明发展早期就遇到了计算问题，在古人类生活过的岩洞里刻痕说明他们在计数和计算。人手是大自然赋予人类最方便的计算工具（这也是人使用十进制数的最根本原因），石子、小木棒是手在这个方面的延伸。随着文明发展，人发明了各种专用计算工具。中国古代的算筹，最早在两河流域出现、在中国得到了真正发展和广泛使用的算盘，都是古代人类寻求计算工具的辉煌成就。工业革命开始后，人发明了各种机械设备，设计制造这些设备的一个基本

4、问题就是计算，需要解决的计算问题越来越多、越来越复杂。因此，当时的科学家也进行了计算工具的研究。1642年法国物理学家帕斯卡发明了机械性的齿轮式加减法器，1673年德国数学家莱布尼兹发明了乘除器，从而导致能够进行四则运算的机械式计算器的诞生，商品机械计算器在1820真正出现。这方面最卓越的工作是英国发明家查里斯巴贝齐在19世纪30-40年代设计的差分机和分析机。巴贝齐企图用机械方式实现一般意义下的计算过程，他设计的分析机已经有了今天计算机的基本框架。但是由于技术限制，用机械方式实现如此复杂的过程几乎是不可能的，巴贝齐的计算机器都没有完成。二、人类对自动机械的需求和早期开发。利用地磁场的指南针、

5、中国古代的指南车、广泛应用的风车水车都可看作这方面的早期成果。自动设备发展史上一个里程碑是钟表的发明，文艺复兴后进入鼎盛时期。有些钟表能定时地完成许多活动。能工巧匠还利用机械原理制造了许多自动化的小玩意。随着大工业发展，人们发明了许多自动机械，从蒸汽机到各种织机，特别是提花织机。人们也考虑计算过程的自动化：用自动过程代替人工（借助于计算器械）实施的复杂计算，巴贝齐的计算机器就是在追求自动化与计算的结合。1884年美国人荷豪利瑞斯用穿孔卡片表示数据，发明制表机获得专利并成功用于美国1890人口普查。三、算法和程序性操作的研究及其理论发展。机械式按规定步骤行事，通过一系列简单计算完成复杂计算的过程

6、，称为“算法过程”，程序性过程。最早算法记录在两河流域发现，公元前两三千年的黏土板，一个典型例子是计算利息何时能等于本金。早期发展的最重要成是古希腊的欧几里德提出的计算最大公约数的辗转相除法（又称欧几里德算法）。中国古代数学研究中有许多有关算法的成果。文艺复兴以后随着近代数学的开拓和发展，算法研究也有了许多成果，人们研究了许多数学问题的计算过程，提出了许多算法。但若没有自动化计算工具，根本无法完成复杂的计算问题。不必造加法机、乘法机、最大公约数机，只要造出“通用图灵机”功能等价的机器，就能解决所有计算问题。图灵的工作非常重要，计算机领域世界最重要的奖项就被用命名为“图灵奖”。算法的理论基础研究

7、在20世纪30-40年代取得了突破性进展，出现了几个有普遍意义的计算模型。英国数学家艾兰图灵40年代提出一种自动计算机器模型，“图灵机”。并提出图灵原理：一切可能的机械式计算过程都能由图灵机实现。还指出，存在 “通用” 图灵机，它可实现所有图灵机的功能。四、电技术与电子技术的发展。自动计算机器需要技术基础。巴贝齐达到机械方式的最高水平。由于计算工作的复杂性，该工作未成功。随着十九到二十世纪电学和电子学的发展，人们看到了另一条实现自动计算过程的途径。德国发明家康拉德 祖思在二战期间用机电方式制造了计算机Z-1到Z-3。美国科学家霍华德 邓肯也提出用机电方式实现自动计算机器，1944年造出MARK

8、 I计算机。祖思和Z-2推动计算机器开发的最重要因素是需求。现代社会发展和科学技术进步都对新计算工具提出了强烈的需求。此外，军事和战争的需要也是一个重要因素。研究开发ENIAC计算机的目的是为军事服务，主要是为了计算弹道和火力表。随着ENIAC的诞生，人类历史上计算工具的一个新时代开始了。蹒跚学步ENIAC是第一台电子计算机，但还不是现代意义的计算机。ENIAC能做许多基本计算，如四则运算、平方立方、sin和cos等。但其计算需要人大量参与，每次计算前技术人员需要插拔许多导线，极麻烦。46年美国数学家冯诺依曼提出计算机的基本原理：程序存储原理，据此造出的新计算机 EDSAC（Electroni

9、c Delay Storage Automatic Calculator，爱达赛克）和 EDVAC（Electronic Discrete Variable Automatic Computer，爱达瓦克）于1949和1952年在英国剑桥大学和美国宾州大学运行。EDSAC是世界第一台存储程序计算机（又称冯诺依曼计算机），是所有现代计算机的原型/范本。EDVAC是最先开始研究的存储程序计算机，它用了10000只晶体管，1952年才完成。1952年IBM公司开发出世界最早的成功的商品计算机IBM701，这是信息产业的开始。当时人们完全没有意识到计算机的潜在用途和发展，IBM公司总裁当时认为“全世界

10、只需要五台计算机”就足够了。随着军用和民用的发展，工业化国家的一批公司企业投入到计算机研究开发生产领域中。虽然计算机具有通用性，但计算机硬件只提供解决计算问题的物质基础，要用计算机解决任何问题，都必须编写有关的程序或软件。早期计算机极难使用，要用二进制编码形式写程序，既耗费时又容易出错，大大限制了计算机的广泛应用。五十年代前期计算机领域的先驱者们就开始认识到这个问题的重要性。1954年约翰巴克斯领导的小组开发出第一个后来广泛使用的程序语言Fortran，大大提高了程序开发效率。Fortran推动IBM的新机器704走向世界，成为当时最成功的计算机，也使IBM成为计算机产业的老大。由此可见软件的

11、重要性。随着计算机应用的发展，许多新型计算机被开发出来，计算机的功能越来越强，速度越来越快。与此同时，计算机科学理论的研究和计算机技术的研究开发也取得了丰硕的成果。人们开始进一步研究计算过程的本质、程序设计的规律、计算机系统的硬件结构和软件结构。一些新的程序设计语言，如Algol60、COBOL、LISP等被开发出来。军用和民用科学计算仍然是计算机应用的主要领域，计算机也开始在商务数据处理领域崭露头角。一些新的研究和应用领域，如人工智能、计算机图形图像处理等露出了萌芽。60年代中操作系统、高级程序设计语言编译系统等基本软件初步成型，形成当时计算机系统的基本框架。1965年IBM推出了360系列

12、计算机，开始了计算机作为商品发展史的新阶段。360计算机采用半导体集成电路技术，第一次提出系列计算机的概念，不同型号机器在指令层次互相兼容，并配备较完备的软件。360及随后的370系列计算机取得了极大的成功。七十年代美日的一些公司开始生产与IBM兼容的大型计算机，推动了计算机价格竞争和技术进步。稳步发展DEC（数据设备公司）等开发了小型、低价格、高性能的计算机，称为小型计算机。主要用于教育科研部门和一般企业，做科学计算和数据处理工作。为解决巨型科学与工程计算问题人们开发了巨型计算机，它们通常装置多个数据处理部件（CPU），这些部件可同时工作，大大提高了处理能力。另一类常见计算机被称为工作站，在

13、企业或科研部门中由个人使用，主要用于图形图像处理、计算机辅助设计、软件开发等专门领域。随着半导体技术发展，60年代末在集成电路片上能制造出的电子元件数突破1000的量级，在一个芯片上做出一个简单计算机成为可能。1971年Intel公司的第一个微处理器芯片4004诞生，预示着计算机发展的一个新阶段的到来。1976年苹果公司成立， 1977年推出的APPLE II计算机是早期最成功的微型计算机。它性能好、价格低，时价相当于一台高档家电。这使计算机第一次可能走入小企业、商店、普通学校，走入家庭成为个人生活用品。计算机所扮演的角色从此发生根本性变化，从科学研究和大企业应用的象牙塔中走了出来，逐渐成为普

14、通百姓身边的普通用品。当时一项有重大意义的发展是图形技术和图形用户界面技术。计算机原来字符行式的命令形式和信息显示形式，复杂而不直观的人机交互方式，使大众很难接受和使用。面向普通百姓的计算机需要一种新表现形式。Xerox的Polo Alto研究中心（PARC）70年代末开发了基于窗口菜单按钮和鼠标器控制的图形界面技术，使计算机操作能以较直观易理解的方式进行。Apple仿照PARC的技术开发了其Macintosh个人计算机（1984），采用图形用户界面取得巨大成功。这和1981年IBM推出的PC/XT计算机一起，推动了微型计算机蓬勃发展的大潮。另一项影响深远的研究也是从七十年代中开始的，这就是计

15、算机网络技术的研究。技术进步使计算机性能飞速提高，价格大幅度下降。易用的图形人机界面使更多的人能够使用计算机，已经有了大量能解决实际问题的应用软件系统。计算机网络的发展，逐渐形成一个遍及并连接着整个世界的巨大信息环境。各方面电子化、计算机化的浪潮。突飞猛进计算机无疑是二十世纪最伟大的发明之一。其意义还有待时间的检验和评价，有人把它与纸张和印刷术的发明相提并论。随着ENIAC的诞生，人类计算工具的一个新时代开始了。这个时代之新，其意义并不仅限于计算方面。从此人类有了一种新型的通用信息处理工具，在随后的发展中人们不断提高其性能、缩小其体积，设法将应用到牵涉到信息处理的各个方面去。从计算机诞生至今五

16、十几年。由于计算机的出现，我们可以看到人类生活的每个方面、每个角落都发生了、正在发生或即将发生根本性的变化。由于计算机的参与，今天的世界与昨天的已经很不同了，明天的世界还会与今天大大的不同。向前看计算机使用的人群和使用的形式。使用计算机的目的。计算机应用的领域。计算机出现的方式。几方面趋势通用：计算机是一种通用信息处理设备，只要有合适的软件，它能适用于各种专门用途。电子：是计算机硬件实现的物理基础，计算机的运行最终都通过电子电路中的电流、电位等实现。数字化：是计算机的信息表示方式。一切信息，无论原本是数值、文字、图形、声音等，在计算机里都统一到二进制的数字化表示上。数字化是计算机的一种基本特征

17、，是通用性的重要基础。“计算机”：这是一种做计算的机器。全名：“通用电子数字计算机”（General - Purpose Electronic Digital Computer）。说明许多性质：计算机基本原理计算机能做的基本动作如数的加减乘除等，极简单。但它可以按程序要求瞬间完成数以万亿计的基本动作，就可能完成一件大工作。我们看到的是这些动作的综合效果。计算机的基本结构不很复杂，能按指挥行事，做得快。更了不起的东西是程序、软件，每个程序都是特殊的，针对具体需要专门实现。输入设备CPU存储器输出设备 数据命令结果冯诺依曼计算机体系结构计算机系统 = 计算机硬件 + 计算机软件计算机硬件 是各种物

18、理设备、部件的总称；是看得见、摸得着的。计算机软件 是各种逻辑部件、程序、文档的总称；是看不见、摸不着的。一般微机硬件由主机、显示器、键盘、鼠标器四件组成： 中央处理器 运算器 主机 控制器 内存储器 微机硬件 外存储器 软盘、硬盘、光盘 外设 输入设备 键盘、鼠标器 输出设备 显示器、打印机（CPU）计算机硬件组成计算机软件计算机软件是各种程序及文档资料的总称。 操作系统 系统软件 语言编译 工具软件 软件 MIS 应用软件 字处理系统 控制系统 CAD、CAM、CAI操作系统操作系统（简称为OS）：对计算机的全部硬、软件资源进行管理、统一调度和统一分配的软件系统称为计算机的“操作系统”。人

19、机间界面 用户通过OS对计算机进行操作。各种软件和程序也都是在OS的支持下运行。计算机系统的核心。学习计算机及操作，实际上是学习OS及操作、使用。功能： CPU的控制和管理 内存的分配和管理 外部设备管理 文件管理 软件与硬件的关系硬件：组成计算机的物理器件。软件：具有特定功能的专用程序。任务是管好、用好计算机，实现各种特定的功能，扩展和提高硬件的功能和的效率，扩大机器的用途。没有硬件，软件就失去了工作的物质基础。只有硬件，而没有完善的软件，则硬件无法发挥作用，犹如失去灵魂的躯体。在硬件确定的情况下，软件决定着系统的功能。软件是特殊的商品，它在信息产业中占的比例越来越大，软件主导着信息产业发展

20、的方向。 CPU（中央处理器）负责处理信息，由控制器和运算器组成。控制器负责解释指令（“大脑”），运算器负责执行指令（“手”）。主存储器又称“内存”，用于存储计算机运行时所用的程序和数据。外部存储器（外存）保存其他备用信息：备用程序与数据。一旦需要，即可装入内存使用。各种输入输出设备实现计算机与外部的信息交换。与人，与其他计算机系统或者设备。计算机主要部件计算机的核心信息处理部件，用半导体集成电路技术制造的。一小块硅片，内部结构极复杂，包含数以百万、千万计的元件和电路。能执行一组操作：取数据，由几个数据算出一个结果（加减乘除等），送出数据等。与每个动作对应有一条指令：CPU接到指令时完成对应动

21、作。一系列指令形成一个程序，能指挥CPU完成一系列动作。对应于通用图灵机 G 的控制器。问题：指令从何而来？CPU与存储程序原理ENIAC：程序记录在穿孔卡片上。计算机读一张卡片做一动作，速度受机械读卡机限制。冯诺依曼看出问题症结，提出了“存储程序原理”，导致现代意义的计算机的诞生了。存储器原来只保存数据，CPU执行指令时由存储器取数据，计算结果存回存储器。冯诺依曼方案：将程序存入存储器，由CPU自动提取指令并执行，循环地做。这样计算机就可以摆脱外界拖累，以自己的速度（电子电路的速度）自动运行了。按“存储程序原理”造出的就是“程序存储计算机”，也称为“冯诺依曼计算机”。到目前为止，所有主流计算

22、机都是这种计算机。计算机的基本运行过程很简单，两步循环，“CPU基本循环”。CPU每次从存储器取出要求它执行的下一条指令，然后按指令完成对应动作。循环到程序执行完（遇到要求CPU停止工作的指令），或者永无休止地运行下去。CPU是个绝对服从指挥的奴仆，每时每刻都按命令（指令）行事。CPU的指令一般有几十到一二百种。而实际领域里，各方面需要应用计算机情况千差万别、错综复杂。计算机怎么能应付这些情况呢？答案：程序。通过一些不同指令的各种适当排列，人能写出的程序是无穷无尽的。考虑数字和数，汉字字和中文的作品。程序：对应于特定图灵机的编码。计算机的工作原理带来两方面的获益：通用性：若干种计算机就能满足全

23、社会的需要。可以采用大工业生产的方式，提高性能，减低成本。计算机越来越便宜，性能越来越高。专用性：通过运行不同的程序，同一台计算机在不同时刻可以表现为不同的专用信息处理机，例如计算器、文字处理器、记事本、资料浏览检索机、帐目处理机、设计图版、游戏机等等。同一台计算机也可以同时表现为多种处理机（只要同时运行着多个不同程序）。这种通用性和专用性的完美统一，使计算机成为人类走向信息时代的过程中最锐利的武器。CPU原理并不复杂。而最先进的CPU又极端复杂，是有史以来人制造的最复杂产品。原因：1，计算机要完成的工作日趋复杂（不断有新问题），需要用更多指令才能完成。而执行指令需要时间（计算机的本质弱点）。

24、要求更高性能的CPU。人们为提高CPU速度开发了许多巧妙技术，但这些大大增加CPU的复杂性。2，处理的数据情况越来越多。早期主要是数值，只需与算术有关的指令。今天广泛用于图形图像声音等的处理。理论上说CPU可以不改（只要写程序）。但增加些新指令能更有效处理这些特殊数据形式。这也增加了CPU的复杂性。过去人常说：计算机发展经历了电子管、晶体管、集成电路和大规模集成电路四个阶段，把以这些方式构造起来的计算机分别称为第一、二、三、四代计算机。今天看，这种说法并无太大的意义。计算机器件基础的变化并不是根本性的（其意义不可低估：降低成本、减小体积等），是人们寻求合适方式制造计算机的一个短暂探索阶段，大约

25、三十年。人们一直在研究真正新型的计算机。提出的有：光计算机、量子计算机、生物计算机等。从本质上与今天计算机不同的信息处理工具会出现吗？能取代目前流行的这种电子计算机吗？我们正拭目以待。数字化图灵理论的一个基本点是所有信息可以用符号编码，包括图灵机本身。要用计算机处理信息，必须：能在计算机内部存储信息、处理；这就要求确定信息在计算机内部的表示方式，能将信息送给计算机处理，这要求能完成从外部信息到计算机内部信息的转换。计算机存储处理信息的基础是信息的数字化，为此，我们只需：为数值确定一种计算机内部的表示方式；将一切信息用数字形式表示，进而就可以用计算机处理。信息的数字形式也称为信息的编码。“万物皆

26、为数”在自然界不真，而在计算机里“成立”。问题：怎样数字化？怎样编码？ 数的进制 手指与十进制，电子元件与二进制。 进制形式只是数值的表示形式。 任何十进制数 X 都可以表示为：X=kn*10n + + k0*100 +k- 1*10-1 + +k-m*10-m 基数为10，系数/数字 ki 0, 1, 2, 3, 4, 5, 6, 7, 8, 9例：46. 37 (10)=4*101+6*100+3*101+7*10-2用进制方式表示数是人类的一项重要智力发明。数 制计算机中用二进制数的方式表示数值。原因：理论：用两个符号的序列能有效表示复杂的信息。（一进制表达效率低，能力不够）实际：常规器

27、件最容易表示两种不同状态。用一个器件表示一个基本的数据单位，用一系列器件的状态表示复杂的数据。将一个器件的状态看成一个二进制数字，将一系列器件的状态看成一个二进制数。一个二进制位：bit（Binary Digit），b，位，比特8位二进制数：Byte（简写B）。1KB = 1024 B1MB = 1024KB 1GB = 1024MB 1TB = 1024GB十进制数。基数为：09；按借1当10，逢十进1的原则进行运算。二进制数。基数为：01；八进制数。基数为：07；十六进制数。基数为：09，AF；常用的计数制二进制B = kn*2n+ + k0*20 +k - 1*2-1 + +k-m*2-

28、m基数为2，系数（数字）属于 0, 1110110(2)= 1*25 + 1*24+0*23+1*22+1*21+0*20 = 32 + 16 + 0 + 4 + 2 + 0 = 54(10)运算规则：0+0=0 0+1=1 1+0=1 1+1=100*0=0 0*1=1 1*0=0 1*1=1一般形式：各种进位制之间的转换一、多项式展开法：（适用于任意进位制到十进制之间的转换）一般方法：（a n a n-1a0 . b1b2bm)R= anXRn+a n-1 XR n-1+a0XR0 +b1XR-1+b2XR-2+bmXR-m)例1：（1010.01）2 = 1X23 + 0X22 + 1X21 +0X20 +0X21 +1X22