书名：计算机科学基础pdf/doc/txt格式电子书下载

推荐语：

作者：冯博琴,陆汉权编

出版社：电子工业出版社

出版时间：2011-08-01

书籍编号：30466634

ISBN：9787121139079

正文语种：中文

字数：188058

版次：1

所属分类：教材教辅-大学

版权信息

书名：计算机科学基础

作者：冯博琴

ISBN：9787121139079

版权所有 · 侵权必究

前言

有一种说法认为，传统的教育是读、写和算术（Reading，Writing and Arithmetic），今天的教育是读、写和计算（Reading、Writing and Computing），由此可见计算的重要性。计算的机器是计算机，因此，计算机科学最简单的解释是——关于计算机的科学，但实际上它的内涵远远超过了计算机本身。从今天的社会形态已经成为信息社会这一事实，可以理解计算机及其网络给人类社会、生活和学习等方面带来的巨大影响。

目前我国大学计算机基础类课程主要分为3个部分：计算机基础、程序设计及计算机应用。前两门被大多数高校列为基础类课程，后一门（也许是多门）是和专业相关的课程。如果想在专业方面有所成就，就应该重视计算机，学好计算机基础和程序设计课程。

问题是，要把计算机用好，究竟该学习些什么呢?现在的学生从中学阶段的信息基础课程中，已经学习了如何打开、关闭机器，学习了使用Windows、Office软件（初步的），也学会了上网，这些都是使用计算机的基本技能。有这些技能当然很好，不过还远远不够。计算机知识之丰富，内涵之复杂，远远超出我们的想象。如果希望把计算机看得更清楚一点，那么最好的方法是站得更高些。因此本书基本上不涉及计算机操作方面的内容，而展现给读者的是有关计算机科学的基础知识，包括其系统、软件、算法、数据及通信。

一般来说，基于计算机和计算机科学的所谓信息技术，由四部分组成：一是计算机系统，这大多是指计算机的硬件；二是软件；三是数据处理；四是网络。本书也是按照这个结构进行编排的。

在第1、2、3章中，重点介绍有关计算机模型和计算机中使用的数制、编码等内容。通过计算机模型可以对计算机的基本原理有一个概貌性的认识。在此基础上，还介绍了计算机的硬件系统。虽然本书没有、也不可能枚举所有类型的计算机硬件的组成部分，但是大部分常用的硬件都介绍了。

第4、5、6章分别介绍计算机的核心软件——操作系统和计算机科学的核心之一——算法，以及实现算法的程序设计语言、程序和软件方面的知识。

第7章介绍数据库相关知识。

第8章介绍网络，包括因特网的基本知识。

第9章介绍有关计算机的一些高级主题，包括高性能计算、人工智能和计算理论。如果说，人类对计算机的期望是“速度更快、体积更小和性能更强”的话，那么就更需要了解计算机能够做什么和不能做什么。有一点很清楚：希望本书的读者明白，哪些是计算机能够做的，哪些是计算机做不到的，在专业方面也是如此。只有知道哪些是可以做的，且如何能够使其做得更好，这才是科学的态度。

最后，第10章讨论有关信息社会的问题，包括有关法律、版权、环境、健康、计算机安全、病毒、黑客等。

本书是浙江大学计算机基础课程建设成果，是浙江大学执教计算机基础课程的教学团队教师的集体贡献。浙江大学从2002年就开始将计算机科学作为大学计算机基础课程的核心，其教材也经过几次修改，本书就是近十年来教学实践的成果。作者一直坚持认为，大学不应该把如何操作计算机作为教学内容，而应该引导学生去认识计算机的原理，这样才能更好地在学习和专业中使用好计算机。例如，学习程序设计的目的，不是成为程序员，而是认识程序原理。一个非计算机专业的学生，肯定是计算机的用户，知道计算机能够做什么、不能够做什么，这应该是最基本的专业素质。因此任何专业的同学都需要学习计算机科学基础，这也是其专业需要。

本书作者近似固执地认为，课程不能通过“工程”的方法去建设，而是要依靠教师引导学生去思考。大学提供给大学生发现问题、讨论问题、争论问题、解决问题的平台，所以作者要说的是：教课及教师并不是教学的核心，特别在计算机课程中，需要“发现、讨论、争论”的问题很多，收获也更多。

本书为任课教师免费提供电子课件，有需要者可登录华信教育资源网http：//www.hxedu.com.cn注册下载。

毫无疑问的是，由于计算机科学的特点，其概念和某些名词的定义可能随着时间流逝而变化，并不像数学、物理科学那样有极为严格的、不变的定义，甚至，从不同的角度表达问题可能有完全不同的说法，这些在书中是常见的。当然，由于作者的水平所限，错误肯定难免，希望使用本书的教师和学生能够不吝赐教。

教育部计算机基础教学指导委员会副主任委员、国家名师、西安交通大学冯博琴教授为本书的编写提供了极为细致的指导，并亲自担任本书的主审，在此作者深表感谢。也借此感谢作者在浙江大学的同事，他们为本书提供了许多宝贵的意见。电子工业出版社的章海涛策划编辑，他为本书的写作和出版付出了很多，在此仅以此文字表示真诚的谢意。同时也十分感谢本书的责任编辑冉哲为本书的顺利出版所付出的辛劳。

陆汉权

浙江大学计算机学院，luhq＠zju.edu.cn

2011年于浙大玉泉

第1章 引论

计算机科学（Computer Science）是一个宽泛的概念，它涵盖了计算机的方方面面。这里讨论的，并不是计算机的全部，而是介绍作为科学的计算机和作为工具的计算机所需要的一些基本知识。本章从“计算机是什么”这个问题开始，介绍数据处理机模型、现代计算机模型和计算机系统、信息系统等基本概念，使读者对计算机有初步的、整体的概念。更为详细的相关知识将在后续章节中讨论。

1.1 计算机是什么

在17世纪，英文计算机（Computer）一词是指从事计算工作的人。到20世纪40年代的第二次世界大战时期，为破译通信密码和解决新型火炮弹道的复杂计算，美国开始研制自动计算机装置，从此开始，计算机被赋予了机器的含义。

计算机已经被公认为是人类科学史上发展最快、影响最大的新学科，计算机科学（Computer Science）、计算机技术（Computer Technology）、计算机工程（Computer Engineering）等术语越来越多地出现在各种学科的文献中，相应而生的信息技术产业（Information Technology，IT）在20世纪90年代成为了全球第一大产业。

今天的计算机和60多年前相比，其外在形式和内涵都发生了巨大的改变，但它仍然建立在最早的模型基础上。从技术上讲，使用大规模集成电路的计算机的体积越来越小，功能却越来越强。从用途上看，过去昂贵的计算机从被放置在专用机房，到今天已摆放在办公桌上、甚至握在手上了；计算机不但是科研、通信、工业生产中重要的设备，也是学习和交流的工具，它进入了家庭，成了消费品，而且是最大的消费类电子产品。

计算机和计算（Computation）是密切相关的，计算是数学的基础，也是计算机的基础。最初人们期望计算机实现数学意义上的“自动计算”，但是随着计算机科学和技术的迅速发展，人们对计算机的巨大潜能开始有了新的认识：客观世界的许多形态都能够被“数字化”，也就是说，我们生存的这个世界上各种形态都能够被计算机所存储、处理、交换以及分析运用。如今，工程师使用计算机进行产品的设计、制造，导演使用计算机帮助拍摄电影、电视，科学家使用计算机进行研究，学生使用计算机帮助学习，等等。

不论你将来从事什么工作，都离不开计算机。只有很好地利用计算机，才能把工作做得更好。因此你不但需要知道计算机究竟能够帮助你做什么，还应该知道它是如何做到的。有科学家把这个问题归结为“计算思维”（Computation Thinking），也就是说，对客观世界中的问题进行抽象表示，再由计算机处理。

这里，我们的第一个问题是，计算机是什么?有许多种回答，几乎每一本教科书的答案都是不同的。按照《计算机科学技术百科全书》中的说法：计算机是一种现代化的信息处理工具，它对信息进行处理并提供结果，其结果（输出）取决于所接收的信息（输入）及相应的处理算法。

按照上述定义，计算机科学与技术的核心，包括计算机的设计、制造，以及运用计算机进行信息的获取、表示、存储、处理、控制等的相关理论、原则、方法和技术。计算机科学研究现象和揭示其规律，而计算机技术则侧重研制计算机和使用计算机进行信息处理的方法和手段。

1.2 数据处理机模型

理解计算机的最好方法是创建一个模型。有多种计算机模型，最典型的是黑盒模型和具有程序处理能力的处理机模型。

根据上述我们所引用的计算机的定义，计算机被看做信息处理机。信息（Information）和数据（Data）是计算机的两个重要概念，一般认为信息是对数据进行处理后得到的，因此可以认为数据是“原材料”，而信息是“制成品”。但在很多情况下，信息和数据这两个词被不加区分地使用着。

1.2.1 黑盒模型

先不考虑计算机的内部结构，从功能的角度，可以把计算机看做一个特殊的黑盒子，如图1-1所示，这个黑盒子就是数据（信息）处理机。

图1-1 黑盒模型

黑盒模型也称数据处理机模型，是计算机原理的经典模型之一，也是对计算机定义的诠释。这个模型指出，数据输入到计算机中后，经过计算机的处理，输出结果。该模型指出，计算机在数据处理过程中，如果输入的数据相同，那么输出结果将能够重现；如果给出不同的输入数据，输出结果也能够随之改变。

数据处理机模型定义了计算机的功能，给出了计算机的基本属性，即计算机就是处理数据的机器。对非计算机专业的用户而言，他们并不需要考虑计算机处理数据的过程和复杂的细节，只需要理解计算机能够进行数据处理、得到用户期望的处理结果即可。因此这个模型能够帮助普通用户理解计算机。

数据处理机模型描述了计算机数据处理的过程，但并没有给出过程的“算法”，因此计算机的复杂性、灵活性在数据处理机模型中并没有被反映出来。同时，数据处理机模型既没有给出机器所处理数据的类型，也没有给出基于这个模型的计算机能够完成的操作类型和数量。另外，这个模型也没有明确定义这种机器是专用或通用的。不过，现在的计算机一般都是通用的。因此，计算机的数据处理能力是如何被体现出来的需要用新的模型进行定义和说明。

1.2.2 具有程序能力的数据处理机

考虑黑盒模型所存在的问题，一个改进的计算机模型如图1-2所示，它在图1-1模型的基础上增加了一个部分——程序。程序（Program）是计算机中一个非常重要的概念，它可以简单地被理解为按照预定的步骤进行工作。程序是处理数据的算法的具体实现。

图1-2 具有程序能力的计算机模型

在这个模型中，计算机的输出结果取决于程序。在同一个程序的控制下，相同的数据能够得到的输出结果也是相同的，这就是所谓的“一致性”。反之，如果程序不同，那么，相同的输入数据得到的输出结果也可能不同。例如，对一组输入数据进行求和计算，得到的结果是累加和。如果程序变成了对同一组数据进行排序，那么输出结果就与求和计算完全不同了。进一步地，不同的数据采用不同的程序也可能产生相同的输出结果。

显然，具有程序能力的处理机模型赋予了计算机极大的灵活性，也使得计算机的数据处理能力得到了极大提升。这个模型与黑盒模型相比，更好地诠释了计算机的定义。由于计算机执行了不同的程序，使它既能够服务于物理学家探索浩瀚的宇宙和细微的粒子，也能帮助儿童学习语言。计算机之所以如此灵活，是因为它能够按照“程序”进行工作，而程序是事先编制好并存放在计算机内部的。

增加了程序功能，使得计算机处理数据的能力得到了充分体现。只要让计算机执行不同的程序，就可以得到各种期望的数据处理结果，这就是极为重要的“程序原理”。

中文文献中使用“计算机”作为正式名称，但另一个通俗的词是“电脑”。在本书中，我们主要使用专业名词“计算机”。

1.3 现代计算机模型

数据处理机模型对帮助人们理解计算机的基本原理是有意义的。事实上，计算机模型需要回答的问题还有很多，如计算机接收的数据是什么形式，在其内部以什么形式存储，如何存储，如何长久保存数据，输出结果如何能够让用户理解等。

计算机的模型不但要有功能性定义，还需要定义其内部结构。因此能够进一步表述现代计算机原理模型如图1-3所示。与前述的数据处理机模型相比，现代计算机模型更为精准地诠释了计算机的定义。很长时间以来，这个模型被叫做冯·诺依曼模型^①，在一些文献和教材中，还是沿用了“冯·诺依曼计算机”这一说法。

图1-3 现代计算机原理模型

现代计算机模型不但给出了计算机的功能，还定义了计算机内部的结构，解决了数据处理机模型中许多未能解决的问题。

1.3.1 计算机的五个组成部分

在如图1-3所示的现代计算机模型中，定义了计算机由输入、运算器、存储器、控制器和输出五个部分组成。其中计算机的控制器（Controller）对计算机的所有部件实施控制，协调整个系统有条不紊地工作，输入设备（Input）负责输入数据和程序，输入的数据和程序被存放到存储器（Memory）中。运算器是执行各种算术和逻辑运算的部件，也叫做算术逻辑单元（Arithmetic Logic Unit，ALU），程序的执行结果通过输出设备输出（Output）。

最早提出类似于如图1-3所示模型的是19世纪初英国数学家查尔斯·巴贝奇（Charles Babbage，1792—1871年），他设计的叫做差分机的计算机的原理为IPOS（Input，Processing，Output and Storage）。今天的计算机原理源于IPOS，因此巴贝奇被称为计算机之父。

图1-3中包含了运算器和控制器的虚线部分，在今天的计算机系统中被称为CPU（Central Processing Unit，中央处理器），大规模集成电路技术将CPU设计成单个芯片。计算机中的输入/输出（Input and Output，缩写为I/O）也被看做一个整体。因此，现代计算机也被认为由三个子系统组成：处理器子系统、存储器子系统和输入/输出子系统。

还有另外一种计算机结构模型叫做“哈佛结构”（Harvard Architecture），它的系统组成也可以用图1-3表示。哈佛结构与现代计算机模型所不同的是它的存储器，图1-3所示的模型将程序和数据存放到一个存储器中，而哈佛结构则将数据和程序分开存放。在今天的计算机中，这两种结构都在使用，不过哈佛结构多用于某些专用处理器系统和通用CPU芯片的内部，以提升CPU的处理效率。

我们已经介绍过几种计算机模型，实际上还有很多种模型用于不同类型、不同规模的计算机，例如多处理器的流水线结构、并行结构等，就其基本原理而言应该是类似的。在许多文献和教材中，为了将现代计算机模型和流水线、并行结构等模型加以区别，前者使用“传统计算机模型”一词，后者则冠以“非计算机传统模型”。

① 业界曾认为现代计算机模型的提出者是冯·诺依曼，但现在认为发明权属于阿塔纳索夫（John Atanasoff）和贝里（K·Berry），即ABC计算机（Atanasoff Berry Computer）的发明人。以前一直认为“程序存储”的发明者是冯·诺依曼，但现在已经知道，最早提出这个概念的是美国宾西法尼亚大学Moore电子工程学院的J·P·Eckert（第一台电子计算机ENIAC的发明者之一），而冯·诺依曼首先公开发表了这个概念。

1.3.2 程序存储原理

现代计算机模型要求程序在执行前存放到存储器中，还要求程序和数据采用同样的格式，这就是著名的程序存储原理。这一原理是冯·诺依曼最早发表在其论文中的。现代计算机模型还要求程序的长度（指令序列，详见第5章）必须是有限的。计算机执行程序时，只要给出程序所在的存储器位置，程序将自动运行直到任务完成。

现在看来，程序存储是一个简单的、显而易见的原理，然而在计算机发展的开始阶段，这一直是困扰计算机科学家的难题，即如何使计算机自动执行程序。早先的计算机，在机器启动后通过面板上的开关组合成操作命令，一个命令执行后，再拨动开关组成下一个操作命令。可以想象，当时使用计算机是一件多么枯燥且容易出错的事情。

使用程序存储的另一个重要的理由是程序的“重用”。对许多计算任务，往往只需要改变输入的原始数据，而计算过程本身是相同的。如果每一个计算机的任务都需要重新编制程序，那么计算机的使用和程序编制本身都将是很难的事。同时，在程序执行之前就将数据存放好，不但有效地提高了计算机的运行效率，也使得程序的执行过程实现了自动化。

1.4 计算机系统

前面介绍了计算机的定义、模型和数据、信息等概念。事实上，今天的计算机其复杂程度远远超过了这些定义和模型所能表达的。计算机不仅仅是“计算”，尽管它最初是为了“计算”而被研究和研制的。计算机能够执行各种任务，所以人们通常认为它肯定是非常复杂的。事实正是如此，如果你对计算机了解得越多，你就会发现它变得越来越复杂。

首先，计算机不仅是一台机器，而是被称为一个系统，即计算机系统（Computer System）。我们知道，被称为“系统”的，肯定是由多个部分组成的，单一的东西是不能称为系统的，因此计算机系统是一个大概念。

简单地说，计算机系统是由计算机硬件和软件组成的，进一步地，计算机的硬件和软件也是“系统”。再深入就会发现，计算机也只是计算机系统中的一部分而已，计算机系统还包括所处理的数据以及使用计算机的用户（User）。

表1-1概略地给出组成计算机系统的硬件系统和软件系统。在第3章中将对硬件系统进行更详尽的介绍，其后的第4、5、6、7章将对软件系统中的几个组成部分进行讨论。

表1-1 计算机系统的组成

1.4.1 硬件系统

组成计算机的物理设备称做硬件（Hardware），也称做硬件系统（Hardware System）。计算机的主要元器件是电子的，由实现计算机操作过程及输入、输出功能的各种电子设备互连组成。术语计算机设备（Device）既可以指一个价值数亿的巨型计算机系统，也可以指一个只有数十元的鼠标器。

1.计算机硬件史

在计算机问世的初期，计算机就是指计算机硬件。由于硬件是计算机的物理体现，因此在计算机发展史中，主要是依据其硬件的技术特征作为标志。

一般来说，20世纪40年代前的各种计算机器如算盘、手摇计算机、机械式计算机等，都不被认为是计算机，因为这些计算装置不能实现“自动计算”。人们把1946年的ENIAC（Electronic Numerical Integrator And Computer，电子数字积分计算机）作为第一台现代计算机，也是第一代计算机的典型代表，它采用电子管作为主要元件。这一阶段后期，开始使用磁记录设备作为计算机的存储器。到了20世纪50年代后期，计算机开始使用晶体管，被称为第二代计算机（1959—1963年）。与电子管相比，晶体管不但体积小、功耗低，且速度快、可靠性高，成本低廉，适宜大批量生产。这一时期，计算机发展开始提速，逐步用于科学计算之外的事务处理。这一时期开始使用电话线进行计算机的数据通信，这就是计算机网络的萌芽阶段。与此同时，集成电路（Integrated Circuits，IC）诞生，它开始被用于计算机制造，也就是所谓的第三代计算机（1963—1975年）。这一时期的另外一个和计算机相关的重大事件是发射了同步通信卫星，由此在地面和空间卫星之间实现数据通信。

1970年有了把计算机的运算器和控制器集成在一个硅片上的CPU集成电路，由此计算机进入了大规模集成电路的第四代（1975年—至今）。20世纪80年代开始发展起来的微型计算机（Microcomputer），也叫做个人计算机，即PC机（Personal Computer），使计算机从实验室走到了办公室的桌面上，由此开创了计算机发展的全新时代。这个时代，计算机网络也得到迅猛发展，今天的Internet不但连接了全世界数十亿计的计算机和网络设备，也创造了被称为继报纸、杂志、广播及电视之后的“第四种媒体”，而且是影响最大的新型传媒。

2.计算机的类型

大多数人现在使用的计算机，无论是桌面机或手持式的，都被称为微型计算机。计算机还有其他不同类型。

通常按计算机的规模及销售价格进行划分，有价值千万美元以上的巨型计算机（Supercomputer，超级计算机），这类机器通常用于极为复杂的、海量的数据处理领域，例如地震模拟、核武器试验、气象分析、生物信息处理等；有价值数百万美元的大型计算机（Mainframe Computer），这类计算机通常用于跨国企业的信息系统，例如银行、航空公司等；也有价值数万至数十万美元的小型计算机，这类机器通常作为企业、政府、学校等机构的网络服务器，或者用于研究机构或较大型工程设计领域。

巨型机、大型机、小型机的价格较为昂贵，而价格低廉的微型计算机，即PC机，不但具有最大的用户群，也是占有计算机市场份额最大的一类机器。

今天的大多数实验室仪器、工业生产设备都带有数据处理能力，这种处理能力依赖于嵌入其中的计算机CPU芯片，这类系统被称为嵌入式系统。事实上，一些高档的家用电器，例如电视机、电冰箱等也内嵌处理器，以实现更高级的功能。随着移动通信开始取代传统的语音通信业务，所谓的“智能手机”也大行其道。本质上，智能手机就是内嵌计算机芯片并使用了计算机技术的个人通信设备。当然，这里的“智能”只是一种商业名词而已，并没有真正意义上的智能。

3.硬件的三个子系统

不管哪种类型的计算机，都是由表1-1所列的那些设备和软件组成的。根据现代计算机模型的定义，计算机都是由处理器、存储器和输入/输出三个子系统构成的。

大型的计算机系统，其主机系统可能是由很多个处理器组成的。例如，2010年公布的排名世界第一、由我国国防科技大学研制的天河-1A超级计算机，其主机的处理器达到186368个，运算速度达到了每秒2570万亿次。而价格低廉的PC机一般使用的是单个处理器芯片，最新的微机开始使用多核处理器芯片，例如双核或四核。这里的核（Core）不一定是多个处理器芯片，多是指一个CPU芯片上集成了多个处理器。

计算机系统中的存储器系统也是一个较为复杂的子系统，它的任务是存储数据、程序和参与运行程序。价格昂贵的机器的存储器容量（Size）是巨大的，而微机的存储器通常“比较小”，当然这是与大型机的比较。尽管如此，今天的微机存储器容量也很大，足以存放多部百科全书。存储器分为：基于电子学原理的半导体存储器，它直接与处理器互连，承担运行程序的任务，因此被称为内存或者主存；使用磁性材料（磁盘）、光学原理（光盘）保存数据和信息的存储设备，这类设备有机械部件，通常被设计成一个独立的部件置于外部，使用电缆连接，因此也被叫做外存。

计算机的输入/输出设备有很多种类型，最常见的输入设备有键盘和鼠标器，输出设备有显示程序界面的各种显示器和输出程序运行结果的打印机等。

研究计算机硬件相关的互连以使计算机更有效、更高速、更可靠的学科称为计算机体系结构，当然它也包括研究如何使机器的体积更小等内容。更多更详细的硬件知识将在第3章中重点介绍。

1.4.2 计算机软件

计算机的另一个重要组成部分是软件（Software）。我们把计算机“看得见”的那一部分称为硬件，把使计算机运行以完成任务的程序称为软件。这一部分是“看不见”的，却是不可或缺的。

1.软件系统

我们把除了计算机硬件之外的所有与计算机相关的文档、程序、语言等都可以归类为软件，因此软件也是一个系统，而且是非常复杂的一个系统。

按照表1-1所述，软件系统是计算机所有软件的总称，它由系统软件和应用软件两个部分组成。我们把服务于计算机本身的那些软件称为“系统软件”（System Software），它包括管理计算机资源和为使用计算机提供帮助的操作系统（Operating System）、计算机语言系统，以及对计算机硬件进行检测、管理的一些工具软件。例如，大多数微机上安装的微软公司开发的Windows就是操作系统软件。我们将在第4章中深入地讨论操作系统，在第6章中将介绍有关计算机语言、程序和软件等更多的概念。

另一类软件被称为应用软件（Applications Software），它是解决特定问题的一类软件。例如常见的办公系统，如字处理软件、Internet浏览器等。很多计算机应用都需要专门的软件，例如学校的教务管理系统软件能完成课程安排、成绩记载、打印和学籍管理等工作。

2.软件的进化

软件也是随着计算机科学的发展和技术的进步而“进化”的，计算机从完全由专业人员操纵到今天的普及应用，在很大程度上应归功于软件。

第一代计算机使用的是二进制代码语言编写的程序，它是内置在机器内部、被计算机处理器直接执行的指令代码。这一时期并没有“软件”概念，只有“编程”（Programming

....