计算机科学导论（第二版）

可作为高校计算机类专业计算机科学导论课程的教材，电气信息类专业学生或其他计算机爱好者 

《计算机科学导论（第二版）》以计算机学科知识体系来组织内容。包括计算机的生产与发展、计算机科学基本理论和基本方法、数据表示与存储、计算机数字逻辑，计算机组成与体系结构、程序设计语言与程序设计、数据结构与算法、数据库技术、计算机网络技术、计算机科学前沿技术等。提供对计算机科学理论的概览，使读者能够对这一学科的基本理论、学科知识体系、思维方法以及与其他学科之间的关系有所了解，为学习后续课程和献身计算机科学事业奠定方法论基础。

 

目录
第1章 计算机的产生与发展 1
1.1 计算的起源 1
1.1.1 数的概念及记数方式的诞生 1
1.1.2 古埃及算术及记数体系 2
1.1.3 古巴比伦算术及记数体系 3
1.1.4 中国古代算术及记数体系 3
1.1.5 古印度算术及计数体系 5
1.2 早期的计算工具 6
1.2.1 世界*早的计算工具—中国算筹 6
1.2.2 耐普尔算筹 7
1.2.3 计算尺 7
1.3 机械计算机的研制 8
1.4 电磁计算机 11
1.5 电子计算机的发明 13
1.6 电子计算机的发展与应用 16
1.6.1 电子计算机的发展阶段 16
1.6.2 巨型机的研究与发展 19
1.6.3 微型计算机的发展 22
参考文献 23
第2章 计算机科学 24
2.1 计算科学的基本内容 24
2.1.1 计算科学的基本问题 24
2.1.2 计算科学的基本内容 25
2.1.3 计算科学与其他相关学科的关系 26
2.2 计算理论 26
2.2.1 布尔代数 27
2.2.2 图灵机 28
2.3 计算科学中的典型问题 30
2.3.1 哥尼斯堡七桥问题 31
2.3.2 四色问题 32
2.3.3 36军官问题 32
2.3.4 哈密尔顿回路及旅行推销员问题 33
2.3.5 Hanoi塔问题 34
2.3.6 生产者-消费者问题与哲学家共餐问题 35
2.4 计算机学科的典型方法 36
2.4.1 抽象方法 37
2.4.2 构造性方法 37
2.4.3 公理化方法 37
2.4.4 形式化方法 38
2.4.5 原型方法与演化方法 38
科学人物 39
2.5 人工智能 41
2.5.1 人工智能的产生 42
2.5.2 人工智能主要研究内容 47
2.5.3 人工智能发展与应用展望 50
2.6 人工神经网络 52
2.6.1 多层感知网络 52
2.6.2 竞争型神经网络 53
2.6.3 Hopfield神经网络 53
科学人物 54
参考文献 59
第3章 计算机数字逻辑 60
3.1 数制 60
3.1.1 进位计数制 60
3.1.2 不同进位制数的转换 61
3.2 编码 67
3.2.1 BCD码 67
3.2.2 文本编码 69
3.2.3 图像编码 72
3.2.4 声音编码 73
3.2.5 可靠性编码 73
3.3 二进制运算 78
3.3.1 二进制逻辑运算 78
3.3.2 二进制算术运算 79
3.4 逻辑门电路 85
3.4.1 晶体管 86
3.4.2 非门 86
3.4.3 与非门 87
3.4.4 或非门 88
3.5 组合逻辑电路 88
3.5.1 逻辑函数 88
3.5.2 译码器 89
3.5.3 多路复用器 90
3.5.4 加法器 90
3.6 时序逻辑电路 92
3.6.1 存储单元 92
3.6.2 时序逻辑电路的结构 95
3.6.3 计数器 96
3.6.4 内存 97
阅读材料 98
参考文献 101
第4章 计算机组成与体系结构 102
4.1 概述 102
4.1.1 计算机系统的层次结构 102
4.1.2 计算机硬件 104
4.1.3 计算机硬件研究范畴 107
4.1.4 计算机的分类 108
4.2 中央处理器 109
4.2.1 计算机指令 109
4.2.2 CPU的功能与组成 110
4.2.3 CISC和RISC 112
4.2.4 指令流水线 114
4.2.5 处理器的分类 115
4.3 存储器 117
4.3.1 存储器的分类 117
4.3.2 存储器的层次结构 118
4.3.3 半导体存储器 119
4.3.4 主存储器 121
4.3.5 Cache 122
4.3.6 磁盘存储器 126
4.3.7 光盘存储器 128
4.3.8 固态存储器 129
4.3.9 虚拟存储器 130
4.3.10 NAS和SAN 134
4.4 总线 136
4.4.1 总线的基本概念 136
4.4.2 总线的分类 136
4.4.3 总线特性及性能指标 137
4.4.4 总线结构的演变 138
4.4.5 总线标准 141
4.5 输入输出系统 145
4.5.1 输入输出设备 145
4.5.2 输入输出接口 146
4.5.3 I/O编址 146
4.5.4 I/O控制方式 147
4.6 并行计算机 149
4.6.1 并行计算机的分类 149
4.6.2 片内并行 150
4.6.3 单片多处理器 151
4.6.4 协处理器 152
4.6.5 多处理器 152
4.6.6 多计算机 153
4.6.7 网格 154
4.7 嵌入式计算机系统 156
4.7.1 嵌入式系统的定义 156
4.7.2 嵌入式系统的特点 156
4.7.3 嵌入式计算机硬件的组成结构 158
4.7.4 嵌入式处理器的典型技术 162
参考文献 168
第5章 计算机操作系统 169
5.1 概述 169
5.1.1 操作系统的功能 169
5.1.2 操作系统的特征 170
5.2 操作系统的发展与分类 171
5.2.1 手工处理阶段 171
5.2.2 批处理系统 171
5.2.3 多道程序系统 172
5.2.4 分时系统 173
5.2.5 实时系统 174
5.2.6 微机操作系统 175
5.2.7 多处理机操作系统 175
5.2.8 网络操作系统 176
5.2.9 分布式操作系统 177
5.3 进程管理 178
5.3.1 进程的概念 178
5.3.2 进程的组成 179
5.3.3 进程的创建 180
5.3.4 进程的终止 180
5.3.5 进程的状态 181
5.3.6 处理器调度 181
5.3.7 线程 183
5.4 进程的并发控制 184
5.4.1 进程的互斥 184
5.4.2 进程的同步 187
5.4.3 信号量与PV操作 188
5.4.4 管程 189
5.4.5 死锁与饥饿 189
5.5 存储管理 191
5.5.1 存储管理的功能 191
5.5.2 存储管理基本技术 192
5.5.3 分页和分段存储管理 192
5.5.4 虚拟存储技术 193
5.6 文件系统 194
5.6.1 文件的概念 194
5.6.2 文件的实现 196
5.6.3 目录的概念 198
5.6.4 目录的实现 200
5.6.5 文件的共享和保护 201
5.7 设备管理 202
5.7.1 设备管理的目标与功能 202
5.7.2 设备的分类 203
5.7.3 输入输出控制方式 204
5.7.4 缓冲技术 204
5.7.5 设备驱动程序 205
5.7.6 设备分配 205
阅读材料 206
参考文献 212
第6章 程序设计语言与程序设计 213
6.1 程序设计语言的发展 213
6.1.1 机器语言 213
6.1.2 汇编语言 214
6.1.3 高级程序设计语言 215
6.2 程序的基本结构 216
6.3 数据类型与运算 218
6.3.1 基本字符、标识符和关键字 218
6.3.2 类型与数据表示 219
6.3.3 运算符、表达式 222
6.3.4 计算与类型 223
6.4 数组 224
6.4.1 数组的概念、定义和使用 225
6.4.2 数组实例 227
6.5 程序控制结构 229
6.5.1 条件语句 230
6.5.2 while循环语句 232
6.5.3 for循环语句 233
6.6 函数 235
6.6.1 一个简单的函数调用 235
6.6.2 函数定义的形式 237
6.6.3 形参与实参 238
6.6.4 函数与程序 240
6.7 程序设计方法 241
6.7.1 结构化程序设计 241
6.7.2 面向对象的程序设计 242
6.7.3 程序设计方法的发展 243
6.8 程序的书写规则 244
6.8.1 变量的命名 244
6.8.2 语句的层次和对齐 244
6.8.3 注释 245
阅读材料 246
参考文献 248
第7章 数据结构与算法 249
7.1 概述 249
7.1.1 数据结构 249
7.1.2 算法 250
7.2 线性结构 250
7.2.1 数组 250
7.2.2 链表 252
7.2.3 堆栈 255
7.2.4 队列 258
7.3 树 260
7.3.1 树的实现 261
7.3.2 二叉树包 263
7.4 图 266
7.4.1 图的存储 267
7.4.2 图的遍历 268
7.4.3 *小生成树 269
7.5 排序 271
7.5.1 直接插入排序 271
7.5.2 冒泡排序 272
7.5.3 快速排序 272
7.5.4 归并排序 274
7.6 递归与分治策略 274
7.6.1 递归 275
7.6.2 分治策略 275
科学人物 276
参考文献 278
第8章 数据库技术 279
8.1 数据管理的发展 279
8.2 数据模型与数据库系统 282
8.2.1 数据模型及其组成要素 282
8.2.2 概念模型 283
8.2.3 基于层次模型的数据库系统 284
8.2.4 基于网状模型的数据库系统 285
8.2.5 基于关系模型的数据库系统 286
8.2.6 常用的数据库管理系统 287
8.3 SQL语言 289
8.3.1 SQL的产生和发展 289
8.3.2 SQL的特点 289
8.3.3 SQL的功能 290
8.4 事务处理技术与并发控制 290
8.4.1 事务 290
8.4.2 数据库并发控制 291
8.5 新型数据库系统 291
8.5.1 分布式数据库 291
8.5.2 联邦式数据库 292
8.5.3 并行数据库 292
8.5.4 主动数据库 292
8.5.5 知识库 293
8.5.6 面向对象数据库 293
8.5.7 多媒体数据库 294
8.5.8 模糊数据库 294
8.5.9 数据仓库 294
8.6 数据库系统的应用 295
8.6.1 信息与信息系统 2

 

 

第1章 计算机的产生与发展
　　计算机的诞生与发展经历了艰苦的探索过程。随着人类生产活动的发展，特别是天文学、航海遇到的大量烦琐的计算，迫切需要研制先进的计算工具。17 世纪，钟表制造技术尤其是齿轮传动技术的发展，为机械计算机器的研制提供了重要的技术基础。19 世纪中期到20 世纪初，随着精密机械制造技术和工艺水平的提高，以及物理学特别是电磁学等学科的发展，在纯机械计算机的基础上，出现了用电气元件制造的电磁式计算机。这些电磁式计算机的研制为后来电子计算机的诞生积累了重要经验。20 世纪20 年代以后，电子科学技术和电子工业的迅速发展为制造电子计算机提供了可靠的物质基础和技术条件；巴贝奇提出的通用计算机结构、图灵机模型及布尔逻辑代数的创立奠定了现代电子计算机的理论基础；社会经济发展、科学计算及国防军事上的迫切需要，成为电子计算机产生的直接动力。**台数字电子计算机—ENIAC 就是在这样一种背景下诞生的，它为现代计算机科学与技术的发展奠定了基础。从此之后，计算机科学与技术开始应用于军事、经济和社会各个方面，人类社会进入了信息时代。
　　1.1 计算的起源
　　计算机的诞生源于人类对“计算”的需求。在人类文明发展的历史长河中，人类对计算方法和计算工具的研究和探索从来都没有停止过。远古时代，人类从长期的生产实践中，逐渐形成了数的概念，从“手指记数”、“石子记数”、“结绳记数”、“刻痕记数”到使用“算筹”进行一些简单运算，形成了实用的记数体系和关于数的运算方法。尽管这些知识还是零碎的，没有形成严密的理论体系，但它作为计算的萌芽，现代计算机科学与技术的发展成就，都是开始于这一时期人类对计算方法、计算工具的长期探索和研究。
　　1.1.1 数的概念及记数方式的诞生
　　数的概念的形成经历了一个缓慢渐进的过程。原始人在采集、狩猎等生产活动中，注意到一只羊与许多羊、一只狼与一群狼在数量上的差异。通过一只羊与许多羊、一只狼与一群狼的比较，逐渐看到其中的某种共同的东西，即它们的单位性。同样，人们注意到其他特定的物群相互间也可构成一一对应的关系。这种为一定物群所共有的抽象性质，就是数。数的概念的形成对人类文明的意义不亚于火的使用。在人类漫长的进化和文明发展过程中，人类的大脑逐渐具有了把直观的形象变成抽象数字的能力，开始进行抽象思维活动，这种抽象的思维活动标志着人类具备了认识世界的基本能力。
　　在数的概念出现之后，就开始有了数的计算和记数。人类社会发展的初期，常常遇到各种各样的计算问题，如计算捕捉到的猎物的数量、计算天数等。
　　计算需要借助一定的工具来进行，人类*初的计算工具是人类的双手。10个手指是*简单的、随时“携带”的计算工具，掰指头算数就是*早的计算方法。用手指计算比较直观，而且可靠，所以这种方法被广泛应用，并延续了若干个世纪。“手指计数”在数学发展中起了很大的作用，因此十进制是人们*熟悉、*常用的进制计数方法。
　　随着社会的发展，需要进行的计算越来越复杂。由于手指计算有其无法克服的局限性，人类开始学习用小木棍、石子等身外之物作计算工具。
　　后来记数方式发展到结绳记数、刻痕记数等。所谓结绳记数，就是在一根绳子上打结来表示事物的多少。这种记数方法在没有掌握文字的民族中曾经被广泛地采用，有些少数民族在后来很长岁月中仍然采用这种记数方式。
　　经过数万年的发展，大约距今5000多年前，出现了书写记数及相应的记数体系。
　　1.1.2 古埃及算术及记数体系
　　居住于尼罗河岸的古埃及人，创造了以象形文字和金字塔为代表的灿烂文明。古埃及象形文字产生于公元前3500年左右，如图1-1所示。
　　图1-1 公元前3500年左右的古埃及象形数字
　　公元前2500年左右，古埃及象形文字演化为一种简便的象形数字体系—“僧侣体”，如图1-2所示。古埃及人就用这种僧侣文在纸莎草（Papyrus）压制成的草片上来做日常书写。在这种数字体系中，从1～9 的每一个数字都有一个特定的符号，从10～90 的每一个10 的倍数以及从100～900 的每一个100 的倍数也都有自身特定的符号。
　　图1-2 僧侣文中表示前10个正整数及20的记号
　　古埃及算术主要是加减法，将乘除化为加减法。分数算法是古埃及算术的一大特色。从纸草书中的记载可以看出埃及人对分数研究的较为透彻，且被广泛使用，这成为埃及数学一个重要而有趣的特色。所有的分数先拆成单位分数（分子为1 的分数）再进行加减运算。为了方便运算，他们设计了一个形如数表（k 为从5～101 的奇数），从表中可以很方便地查出拆分方法。例如，利用该表可以将表示成单位分数之和的形式这种烦琐的运算方式在一定程度上阻碍了埃及算术的发展。同时，古埃及几何学研究也较发达，在纸草书中可以找到计算正方形、矩形、等腰梯形等图形面积的公式。可以看出，古埃及人在体积计算中达到了很高水平，这表现在对金字塔的建造及计算方面。
　　1.1.3 古巴比伦算术及记数体系
　　位于底格里斯河与幼发拉底河流域的美索不达米亚平原，也是人类文明的发祥地之一。早在公元前4000年前，苏美尔人就在这里建立起城邦国家并创造了文字。
　　在这一时期，苏美尔人基于对量的认识，建立了数的概念，有了自己的数学。他们的记数方法有十进位制和六十进位制，制订了乘法表，学会了计算面积和体积。后来苏美尔人创造出一种楔形文字，并把这种文字和自己的科学技术传给了后来的古巴比伦人。
　　公元前2500年，古巴比伦人不仅会乘除法，而且还有平方表、平方根表、立方表，用来解二次方程和三次方程。从大约公元前1800 年开始，古巴比伦人已经使用较为系统的以60为基数的楔形文字记数体系。
　　古巴比伦人擅长计算，具备较高的解题技巧，能解一些一元二次、多元一次和少数三、四次方程。几何上掌握了一些不规则多边形的面积及一些锥体的体积的计算公式，并已知半圆内接三角形是直角三角形，了解并会利用图形的相似性概念。
　　另外，古巴比伦人还经常利用各种数表来进行计算，使计算更加简捷，在现有出土的300多块数学泥板文书中，就有200 多块是数学用表，包括乘法表、倒数表、平方表、立方表、平方根表、立方根表，甚至还有指数（对数）表。
　　总的来说，古代美索不达米亚数学与埃及数学一样主要是解决各类具体问题的实用知识，处于原始算法积累时期。埃及纸草书和古巴比伦泥板文书中汇集的各种几何图形面积、体积的计算法则，本质上属于算术的应用。
　　1.1.4 中国古代算术及记数体系
　　在古巴比伦和古埃及文明建立的同时，东方的中国和印度也创造了灿烂的数学文化。与以证明定理为中心的古希腊数学不同，中国古代数学是以创造算法特别是各种解方程的算法为主要特征。从线性方程组到高次多项式方程，中国古代数学家创造了一系列先进的算法，他们用这些算法求解相应类型的代数方程，从而解决导致这些方程的各种各样的科学和实际问题。因此，中国古代数学具有明显的算法化、机械化的特征。
　　1．中国古代的记数方法
　　中国古代记数方法的起源是很早的。原始社会末期，私有制和货物交换产生以后，数与形的概念就有了一定的发展。有数的观念和数字符号之后，便产生了原始的记数方法。
　　西安半坡出土的距今6000 年前的陶器上的几何花纹，提供了一个由物体形象到抽象的几何图案的演变过程的线索，如由鱼形变成梭形、菱形、三角形、长方形等几何图案。除此之外，半坡人还有了数目的观念。例如，在一个陶钵上有用1～8 个圆点组成的等边三角形和分正方形为100 个小正方形的图案。半坡遗址的房屋基址都是圆形和方形的。
　　为了画圆作方、确定平直，人们还创造了规、矩、准、绳等作图与测量工具。据《史记 夏本纪》记载：夏禹治水“左规矩，右准绳”。说明在当时已使用了这些几何工具。在甲骨文和金文中都有数学方面的资料的记载。
　　根据河南安阳出土的殷墟甲骨文及周代金文的考古证明，中国当时已经采用“十进位值记数法”，并有十、百、千等专用的大数名称，如图1-3 所示。商代中期，在甲骨文中已产生一套十进制数字和记数法，其中**的数字为万，如图1-4 所示。与此同时，殷人用十个天干和十二个地支组成甲子、乙丑、丙寅、丁卯等60 个名称来记60 天的日期。在周代，又把以前用阴（–）、阳（—）符号构成的八卦表示8 种事物发展为六十四卦，表示64 种事物。
　　图1-3 商代记数甲骨文 图1-4 甲骨文中的数的记法
　　公元前1世纪的《周髀算经》提到西周初期用矩测量高、深、广、远的方法，并举出勾股形的勾三、股四、弦五以及环矩可以为圆等例子。除此之外，中国古代对分数概念的认识也比较早，分数概念及其应用在《管子》、《墨子》、《商君书》、《考工记》等春秋战国时代的书籍中都有明确记载。到春秋战国时代，算术四则运算已经成熟。据汉时燕人韩婴所著《韩诗外传》记载，标志乘除法运算法则的“九九歌”在春秋时代已相当普及。
　　2．中国古代算术
　　中国古代数学与希腊数学相比，表现出强烈的算法精神。从线性方程组到高次多项式方程，乃至不定方程，中国古代数学家创造了一系列先进的算法（中国数学家称之为“术”）。他们用这些算法去求解相应类型的代数方程，从而解决导致这些方程的各种各样的科学和实际问题。特别是，将几何问题也归结为代数方程，然后用程式化的算法来求解。
　　到春秋末年，人们已经掌握了完备的十进位和位值制的记数方法，普遍使用了算筹这种中国特有的计算工具，人们的筹算技能水平很高。《管子》等典籍中有各种分数，说明分数概念和分数运算已经形成。
　　《周髀算经》既是我国现有*早的天文学著作，也是流传至今*早的算学著作，其中叙述了勾股定理与勾股测量等数学问题及其在天文、生产中的应用。
　　汉代初期数学名著《九章算术》反映的是中国先民在生产劳动、丈量土地和测量容积等实践活动中所创造的数学知识，是中国古代算法的基础。它含有上百个计算公式和246 个应用问题，有完整的分数四则运算法则、比例和比例分配算法、若干面积和体积公式、开平方和开立方程序、方程术—线性方程组解法、正负数加减法则、解勾股形公式和简单的测望问题算法，其中许多成就在当时处于****地位。
　　《九章算术》“方程术”的消元程序，在方程系数相减时会出现较小数减较大数的情况，由此引进了负数，并给出了正、负数的加减运算法则，即“正负术”。对负数的认识是人类数系扩充的重大步骤。公元7 世纪印度数学家也开始使用负数，但负数的认识在欧洲却进展缓慢，甚至到16 世纪，法国数学家韦达（F.Vieta，1540～1603 年）的著作里还回避负数这个问题。
　　公元3世纪，刘徽在长期精心研究《九章算术》的基础上，为其撰写注解文字，潜心编写了《九章算术注》。在《九章算术注》中，刘徽发展了中国古代“率”的思想和“出入相补”原理。用“率”统一证明《九章算术》的大部分算法和大多数题目，用“出入相补”原理证明了勾股定理以及一些求面积和体积的公式。创立了基于极限思想的割圆术，并应用割圆术，从圆内接正6 边形出发，依次计算出圆内接正12 边形、正24 边形、正48边形，直到圆内接正192 边形的面积，然后使用现在被称为“外推法”的近似计算方法，得到了圆周率的近似值π3.14，化成分数为，即为著名的“徽率”。“外推法”是现代近似计算技术的一个重要方法，它奠定了中国圆周率计算长期在世界上领先的基础。
　　宋、元时代，我国以算筹为计算工具的传统数学达到了其发展的高峰，*突出的是关于高次方程的数值解法，比欧洲早400多年。
　　宋元数学发展中另一个突出成就是符号化，即“天元术”和“四元术”的发明。天元术和四元术都是用专门的记号来表示未知数，这是中国数学史上首次引入符号，并用符号运算来解决建立高次方程的问题。把天元术推广到二元、三元和四元的高次联立方程组，是宋元数学家的又一项杰出创造。