《计算机科学导论——计算思维视角》以扩展的计算思维为主线，融入课程思政，理论与应用相结合，参照中国计算机学会、国际计算机协会以及美国电气与电子工程师协会的计算学科定义和建议，对计算机科学与技术进行科学、系统地阐述。《计算机科学导论——计算思维视角》共7篇14章，从计算思维涉及的逻辑思维、系统思维、算法思维、网络思维、数据思维和智能思维六个方面展开，具体阐述计算机科学相关定义，社会与道德问题，数的表示、存储与运算，数字逻辑与数字系统，计算机硬件，计算机软件，高级程序设计基础，数据结构与算法，计算机网络，移动通信与无线网络，数据库系统，大数据技术，机器学习和人工智能14个专题知识，目的是让读者了解计算机科学与技术学科的全貌，并对计算思维有深刻的认知。

**篇 计算机科学总论
　　1.中国**个计算机科研组的诞生
　　早在1947～1948年，华罗庚在美国普林斯顿大学高级研究院担任访问研究员，和冯？诺依曼等人交往甚密。华罗庚在数学上的造诣和成就受到冯？诺依曼的赞赏。当时，冯？诺依曼正在设计世界上**台存储程序的通用电子数字计算机，他让华罗庚参观他的实验室，并和华罗庚讨论有关学术问题，华罗庚心里开始盘算着回国后也要在中国开展电子计算机的工作。回国后，华罗庚在清华大学任教，并参与中国科学院数学研究所的筹建，1952年被任命为中国科学院数学研究所所长。在华罗庚领导下的数学研究所不但开展了纯数学的各个分支的研究，还开展了力学、理论物理和数理逻辑的研究，特别是华罗庚念念不忘要开展电子计算机的研究。华罗庚不愧是一位有远见的科学家，当很多人还不知道计算机为何物时，他已经意识到了计算技术是科学发展的新的生长点，并积极倡导和主持这方面的工作。
　　1952年，全国高等学校院系调整，华罗庚在清华大学电机系挑选了闵乃大、夏培肃和王传英三个人去数学研究所研究电子计算机，组建了我国**个计算机科研组。华罗庚布置的*要任务就是要设计和研制中国自己的电子计算机。这个计算机科研组在华罗庚的领导和支持下，逐渐成长和壮大起来，成为一个具有活力和有能力承担重担的科研组。
　　2.中国**个计算技术研究所的筹备
　　1956年6月19日，华罗庚被任命为中国科学院计算技术研究所筹备委员会主任。华罗庚以极大的热情投入到计算技术研究所的筹备工作中。虽然那时他也担任数学研究所的所长，但他的时间和精力主要花在计算技术研究所的筹备工作上，他千方百计地落实规划所规定的各项任务。华罗庚还在数学研究所动员研究纯粹数学的人改行，去计算技术研究所工作。在他的号召下，冯康、许孔时、魏道政等自愿来到了计算技术研究所工作。
　　当时的计算技术研究所是全国在计算技术方面唯一的科研单位，到1956年底，已集中了314人，华罗庚很好地协调了各合作单位之间的关系以及各单位人和人之间的关系，使研究所在筹备期间就成为一个团结奋进、朝气蓬勃的集体。
　　3.中国**台计算机的诞生
　　中国**代女性计算机科学家—夏培肃院士在近代物理研究所工作期间，对串行计算机的运算器所执行的四则运算的算法进行了比较深入的研究，初步完成运算器和控制器的逻辑设计，并完成一些基本电路实验。1958年，计算技术研究所提出要研制一台小型计算机，交由夏培肃负责，该计算机被命名为107计算机。
　　夏培肃负责107计算机的总体设计、逻辑设计、工程设计和可靠性设计。107计算机是一台小型的串行通用电子管数字计算机，采用冯？诺依曼体系结构，磁芯存储器。机器可执行16种操作：接收、发送、接收反码、逻辑加、逻辑乘、移位、加法、溢出不停机的加法、减法、乘法、除法、无条件转移、条件转移、非零转移、打印、停机。这是我国**台自行设计的通用电子数字计算机。该计算机工作很稳定，1960年4月机器考试时，连续无故障工作时间为20小时30分钟。
　　107计算机在计算所加工调试后，安装在中国科学技术大学。中国科学技术大学结合107计算机，编写了计算机原理和程序设计的讲义，作为该校计算机专业、力学系、自动化系、地球物理系的教材，共有600多名学生在107计算机上算题。107计算机除了为教学服务外，还接受了一些外单位的计算任务，它们包括潮汐预报计算、原子反应堆射线能量分布计算、原子核结构理论中的矩阵特征值及特征向量计算等数十项计算课题。
　　107计算机研制成功的意义不仅仅在于它是我国**台自行研制的通用电子数字计算机，更重要的是它说明了中国人有能力、有志气设计和研制自己的计算机。
　　第1章 计算机科学概述
　　从世界上**台电子计算机诞生至今，计算机以超常规发展的速度，让人们的学习和生活发生了根本性的改变，以计算机为基础的应用渗透到人们生活的方方面面。计算机的出现不仅提高了人们的工作效率，也使教育、商业、娱乐等诸多传统领域发生了巨大变革，更促进了信息和知识的传递，加速了人们进入信息时代和智能时代的步伐，当今的计算机已成为人类社会不可分割的一部分。本章*先对计算机科学的相关模型和概念进行介绍，其次分析计算思维和计算机科学的关系，然后介绍计算机的发展历程，*后给出计算机科学与技术学科的知识体系、应用领域和发展趋势。
　　1.1 引 言
　　本节的主要目的是介绍计算机科学的定义、图灵模型和冯？诺依曼模型、计算机系统的组成，为后续章节的学习做一个简单的铺垫。
　　1.1.1 计算机科学的定义
　　计算机科学是一门研究信息转换过程的设计、分析、实现、效率及应用的学问。构成所有计算机科学的基本问题是“什么可以自动化”。计算机科学伴随着存储程序电子计算机的发明，于20世纪40年代中期应运而生，并且自那以后发展迅速。
　　计算机科学深深地植根于数学、工程学和逻辑学。几千年来，数学主要研究计算。人们利用许多物理现象的模型来预测那些物理现象，例如，轨道弹道计算、天气预报和流体流动等。人们已经设计了许多解此类方程的通用方法，如线性方程、微分方程和积分函数。几乎是在同一时期内，工程学主要研究力学系统辅助设计的计算。例如，静止物体压力的计算，运动物体动量的计算，超过人们正常知觉的极长或极短距离的测量。
　　工程学与数学长期交互作用的一个结果是力学的辅助计算。一些勘测员与探险家的计算设备可以回溯到1000年前。在17世纪中叶，帕斯卡（Pascal）和莱布尼茨（Leibniz）就制成了算术计算器。19世纪30年代，巴贝奇（Babbage）设计了一台“分析机”，它能机械而又无误地计算对数函数和三角函数及其他算术函数。虽然巴贝奇的这台“分析机”并没有完成，但激励了后人的工作。20世纪20年代，布什（Bush）做了一台用于求解通用微分方程系统的电子模拟计算机。到20年代末，能够计算加减乘除和平方根的机电计算器投入使用。电子触发器为从模拟计算器到数字计算器的过渡提供了很自然的桥梁。
　　逻辑学也是一门古老的学科，它研究推论的有效性标准及推理的形式原理。从欧几里得的时代开始，逻辑学就一直是严格的数学和科学论断的工具。在1830年，人们就发现已知的演绎系统都是不完全的，因为总可以找到悖论。这导致了对完全演绎系统长达一个世纪的研究。所谓完全演绎系统就是在该系统内，总可以决定任一给定的语句是真还是假。1931年，哥德尔（Goedel）发表了他的“不完全性定理”，证明了完全的系统是不存在的。1936年，阿兰？图灵（AlanTuring）也发现了类似的结论，即存在着不能用机械过程求解的问题。逻辑的重要性不仅仅在于它对自动计算极限的深刻洞悉，而且在于它揭示了符号串（或者是被编码的数字），既当作数据又当作程序解释的可能性。
　　这是区别存储程序计算机与计算器的关键思想。算法的步骤可以表示成二进制代码存储在存储器内，而后由处理机进行译码和执行。二进制代码可以根据高级的符号形式程序设计语言机械地产生。
　　正是计算的古典思想与逻辑符号变换的这种明确然而又错综复杂的结合标志着计算机科学的诞生。
　　计算机科学在20世纪40年代尚处于摇篮时代，而到了20世纪80年代已逐步成长为一门内容丰富的学科。表1-1回顾了计算机科学的发展历程。表中所列的时间指的是新的领域从难以理解的技术转变为容易理解的核心原理的时间，即它们是何时成为绝大多数计算机科学系的必修课的，当然这些时间都是近似的。人工智能从计算机科学的早期开始就一直是一个很活跃的研究领域，但在许多大学是*近才由选修课变为必修课的。
　　这11个领域绝不是互相排斥的，每个领域都有自己的理论部分。大多数领域都有专用的程序设计语言作为表达算法和数据结构的记号。大多数实现都是在配备网络操作系统的机器上进行的。大多数领域处理的问题都有可并发执行的部分。有一些子学科，如软件工程，与以上这11个领域的每一个都有关。
　　下面，将对这11个领域的主要内容进行提要，并列出每个领域的基本问题和研究成果。
　　（1）理论。这一领域研究计算的数学基础。基本问题如下：机器可以解决什么问题？对于给定的问题类，优化算法是什么？相对于给定问题类而给定的机器类的固有的*好和*坏性能是什么？什么问题在计算复杂性上是互相等价的？主要成果如下所述。
　　①可计算性理论，定义了机器能够做什么及不能做什么。其分支包括自动机和形式语言理论。
　　②复杂性理论，研究如何测定可计算函数的时间和空间要求，该理论用解决问题的算法的*坏和*好性能来讨论问题的规模。
　　③问题的复杂性分类，如多项式时间界限内确定可解的问题（P-问题）和多项式时间界限内非确定可解的问题（NP-问题）。
　　④自动定理证明。
　　（2）数值计算。这个领域研究有效而准确地求解由系统的数学模型导出的方程的通用方法。基本问题如下：如何用有限离散的过程来准确地逼近连续或无限过程？如何处理由于近似而引起的误差？对于一给定的方程类，如何能够快速求解以达到给定的精确度？如何执行方程的符号操作，如积分、微分、*小项归约？怎样把这些问题的解放入有效、可靠、高质量的数学软件包？主要成果如下所述。
　　①方法的稳定性理论和由于有限离散表示引起的错误传播理论，特别地，回溯误差分析。
　　②对于如快速傅里叶（Fourier）变换及泊松（Poisson）方程求解的快速算法，算法的精确性和效率的扩充估计。
　　③可由规则网格和边界值说明的一大类问题的有限元模型，相关循环方法和收敛性理论，数值积分时的自动网格求精。
　　④处理一些有关矩阵、常微分方程和统计学理论的通用问题的数学软件包；有关偏微分方程、优化和非线性方程的非通用问题的数学软件包。
　　⑤能够进行表达式的有效隐含归约，微分、积分的符号操作。
　　（3）体系结构。这个领域研究把许多硬件和软件组织成有效而可靠的系统的方法。基本问题如下：在机器上实现处理存储和通信功能的*好方法是什么？怎样制造一个大型计算系统使得尽管会发生各种故障仍可正常工作？主要的研究成果如下所述。
　　①有限状态自动机理论与布尔电路代数，它们表明了硬件功能与结构的关系。
　　②单指令流存储程序的所谓冯？诺依曼计算机。
　　③快速算术计算的硬件单元。
　　④在各种介质上，信息编码及存储的有效方法。
　　⑤可靠计算理论，包括冗余部件、重构、诊断和测试。
　　⑥同基本部件组成大的复杂系统的方法。
　　⑦能够支持成百上千个同时执行的处理机的多处理机机器的模型。
　　⑧微电子电路技术及超大规模集成电路的计算机辅助设计。
　　（4）程序设计语言和方法学。该领域研究表达算法和数据的记号，以及从高级语言到机器代码的翻译和有效地构造正确程序的方法。基本问题如下：在各种类型的问题中，基本的数据类型是什么？它们如何表示？控制计算执行的基本方法是什么？如何使用语言的句法描述来构造有效的编译程序并且产生优化代码？应该借助什么方法来证明一个程序完成了所要求的功能？主要成果如下所述。
　　①面向过程的程序设计语言，如Cobol、Fortron、Algol、Pascal和Ada；函数型语言，如APL、Lisp、Prolog和VAL；目标操作语言，如Smalltalk和CLU。
　　②程序设计语言基本概念的组合，如基本数据类型（子界、数据、记录、串）和控制结构（串行、循环、选择、子程序、递归）。
　　③编译及代码产生的理论及其在实际编译程序中的应用。
　　④验证程序的功能描述与其执行是否相符合。
　　⑤句法制导的编辑程序，控制程序构成并且提醒用户避免潜在错误。
　　（5）算法和数据结构。该领域研究特定的问题类和它们的有效解法，基本问题如下：对于给定的一类问题，*好的算法是什么？算法所需的空间和时间为多少？空间和

目录
**篇 计算机科学总论
第1章 计算机科学概述 3
1.1 引言 3
1.1.1 计算机科学的定义 3
1.1.2 图灵模型和冯？诺依曼模型 8
1.1.3 计算机系统组成 11
1.2 计算思维和计算机科学 15
1.2.1 逻辑思维 16
1.2.2 系统思维 17
1.2.3 算法思维 19
1.2.4 网络思维 20
1.2.5 数据思维 22
1.2.6 智能思维 25
1.3 计算机的发展历程 27
1.4 计算机科学与技术学科知识体系 31
1.5 计算机的应用与发展趋势 34
1.6 本章小结 37
第2章 社会与道德问题 39
2.1 道德原则 39
2.2 知识产权 43
2.3 隐私保护 46
2.4 计算机犯罪 49
第二篇 数理逻辑思维基础
第3章 数的表示、存储与运算 55
3.1 计算机数据组织简介 55
3.2 数的表示及进制转换 56
3.2.1 数的表示 56
3.2.2 进制转换 58
3.3 数的码制 60
3.3.1 原码 61
3.3.2 反码 61
3.3.3 补码 62
3.4 定点数和浮点数 65
3.4.1 定点数 65
3.4.2 浮点数 66
3.4.3 二进制小数 66
3.4.4 IEEE浮点表示 68
3.5 十进制数的编码 70
3.5.1 有权码 70
3.5.2 无权码 70
3.6 数的存储 71
3.6.1 数字存储 72
3.6.2 文本存储 74
3.6.3 音频存储 76
3.6.4 图像存储 77
3.7 数据运算 81
3.7.1 移位运算 81
3.7.2 算术运算 84
第4章 数字逻辑与数字系统 89
4.1 基本逻辑关系 89
4.2 逻辑函数 89
4.2.1 基本逻辑运算 89
4.2.2 逻辑函数基本定理 91
4.2.3 逻辑函数基本运算规则 92
4.3 逻辑函数标准型 93
4.3.1 逻辑函数的两种标准形式 94
4.3.2 将逻辑函数化为标准型 95
第三篇 计算机系统（系统思维）
第5章 计算机硬件 101
5.1 引言 101
5.2 冯？诺依曼模型 101
5.2.1 五个部件 102
5.2.2 存储的程序概念 103
5.2.3 指令的顺序执行 103
5.3 中央处理单元 104
5.3.1 算术逻辑单元 104
5.3.2 寄存器组 105
5.3.3 控制单元 105
5.4 分层存储体系 105
5.4.1 地址空间 106
5.4.2 存储器的类型 106
5.4.3 存储器的层次结构 107
5.4.4 高速缓冲存储器 108
5.5 输入/输出系统 109
5.5.1 非存储设备 109
5.5.2 存储设备 111
5.6 计算机硬件扩展技术 114
5.6.1 多核技术 114
5.6.2 高性能计算机 115
5.6.3 并行计算机 116
5.6.4 分布式系统 118
第6章 计算机软件 120
6.1 引言 120
6.2 操作系统基本概念 121
6.2.1 操作系统的目标 122
6.2.2 操作系统的作用 123
6.2.3 推动操作系统发展的主要动力 124
6.3 操作系统的发展历程 126
6.3.1 未配置操作系统的计算机系统 126
6.3.2 单道批处理系统 127
6.3.3 多道批处理系统 129
6.3.4 分时系统 130
6.3.5 实时系统 132
6.3.6 微机操作系统的发展 133
6.4 操作系统的组成 135
6.4.1 并发 136
6.4.2 共享 136
6.4.3 虚拟 137
6.4.4 异步 139
6.5 操作系统的功能 139
6.5.1 处理机管理功能 139
6.5.2 存储器管理功能 141
6.5.3 设备管理功能 142
6.5.4 文件管理功能 143
6.5.5 操作系统与用户之间的接口 144
6.5.6 现代操作系统的新功能 145
6.6 主流操作系统 146
6.6.1 UNIX 146
6.6.2 Linux 148
6.6.3 Windows 149
6.6.4 Mac OS 150
6.7 计算机软件设计方法 152
6.7.1 软件工程基本概念 152
6.7.2 软件开发模型 154
6.7.3 软件开发步骤 161
第四篇 程序基础及算法（算法思维）
第7章 高级程序设计基础 167
7.1 程序设计简介 167
7.1.1 程序设计范型 167
7.1.2 程序设计语言 169
7.1.3 程序设计步骤 171
7.2 程序的编译过程 171
7.2.1 源程序、目标程序和可执行程序的概念 171
7.2.2 程序开发步骤 172
7.3 数据的组织结构 173
7.3.1 基本数据类型 174
7.3.2 运算符和表达式 175
7.3.3 数组 180
7.3.4 指针 185
7.3.5 结构体与共用体 188
7.4 程序的组织结构 191
7.4.1 顺序结构 191
7.4.2 选择结构 192
7.4.3 循环结构 195
7.4.4 函数 197
第8章 数据结构与算法 201
8.1 数据结构简介 201
8.2 三大基本数据结构 204
8.2.1 线性表 204
8.2.2 树 210
8.2.3 图 216
8.3 数据操作 228
8.3.1 查找 228
8.3.2 排序 237
8.4 算法概念及描述 245
8.4.1 算法的定义 245
8.4.2 算法的特性 245
8.4.3 算法的效率度量方法 247
8.5 常用算法 248
8.5.1 递推算法 248
8.5.2 递归算法 249
8.5.3 穷举算法 252
8.6 算法的分析与评价 252
8.6.1 时间复杂度 253
8.6.2 空间复杂度 256
第五篇 网络与互联（网络思维）
第9章 计算机网络 261
9.1 数字通信基础 261
9.1.1 数字通信信号处理 261
9.1.2 数据通信系统的模型 262
9.1.3 基本的数字通信术语 263
9.1.4 有关信道的基本概念 263
9.1.5 计算机网络 264
9.1.6 开放式系统与网络协议 265
9.1.7 TCP/IP 266
9.1.8 高层协议 267
9.2 物理层和数据链路层 268
9.2.1 物理层的基本概念 268
9.2.2 物理层下面的传输媒体 269
9.2.3 信道复用技术 271
9.2.4 数据链路层的基本概念 271
9.2.5 数据链路层提供的服务 272
9.2.6 常见的数据链路层协议 273
9.3 网际层 274
9.3.1 概述 274
9.3.2 网际协议IP 275
9.4 传输层 278
9.4.1 概述 279
9.4.2 用户数据报协议 280
9.4.3 传输控制协议 281
9.5 应用层 283
9.5.1 域名系统 283
9.5.2 文件传输协议 284
9.5.3 远程终端协议 284
9.5.4 万维网 285
9.5.5 电子邮件 285
9.6 网络安全 286
9.6.1 计算机网络面临的安全性威胁 286
9.6.2 安全的计算机网络 286
9.6.3 密码学 287
9.6.4 数字签名 288
第10章 移动通信与无线网络 289
10.1 无线移动通信基础 289
10.1.1 蜂窝网络基础 289
10.1.2 蜂窝系统的基础设施 291
10.2 无线个域网 293
10.2.1 蓝牙 293
10.2.2 低速WPAN 294
10.2.3 高速WPAN 295
10.3 无线局域网 295
10.3.1 IEEE 802.11 296
10.3.2 802.11局域网的物理层 296
10.3.3 802.11局域网的CSMA/CA协议 297
10.4 无线城域网与无线广域网 298
10.4.1 无线城域网 299
10.4.2 无线广域网 299
10.5 无线自组网络 300
10.6 无线传感器网络与物联网 301
10.6.1 无线传感器网络 301
10.6.2 物联网 302
10.7 卫星通信网络 303
第六篇 数据管理（数据思维）
第11章 数据库系统 307
11.1 数据管理简介 307
11.1.1 数据库的基本概念 307
11.1.2 数据库系统的历史 308
11.1.3 数据库系统的特点 309
11.1.4 数据模型 310
11.2 关系数据库模型 314
11.2.1 关系模型的数据结构 315
11.2.2 关系模型的数据操作 315
11.2.3 关系模型的完整性约束 316
11.2.4 关系代数 318
11.3 关系数据库设计 320
11.3.1 关系数据库设计概述 320
11.3.2 关系数据库概念结构设计 322
11.3.3 关系数据库逻辑结构设计 326
11.3.4 关系数据库物理结构设计 327
11.3.5 关系数据库的安全性 328
11.3.6 关系数据库的完整性 331
11.3.7 关系数据库恢复技术 332
11.3.8 关系数据库并发控制 335
11.4 数据库新进展 337
11.4.1 分布式数据库 337
11.4.2 空间数据库 337
11.4.3 多媒体数据库 337
11.4.4 数据仓库 338
11.4.5 信息存储与检索 338
11.4.6 超文本和超媒体 339
11.4.7 多媒体信息与多媒体系统 339
11.4.8 数字图书馆 340
11.4.9 数字地球与智慧城市 340
第12章 大数据技术 341
12.1 大数据的概念与特征 341
12.1.1 大数据的概念 341
12.1.2 大数据的特征 342
12.2 数据采集、管理、分析和可视化技术 344
12.2.1 数据采集与预处理 344
12.2.2 数据存储与管理 346
12.2.3 数据处理与分析 348
12.2.4 数据可视化 349
12.3 大数据管理系统 350
12.3.1 NoSQL数据管理系统 350
12.3.2 Ne