计算机科学导论（原书第4版）

出版者的话
译者序
前言
第1章　绪论 1
1.1　图灵模型 1
1.1.1　数据处理器 1
· · · · · · (更多)

出版者的话
译者序
前言
第1章　绪论 1
1.1　图灵模型 1
1.1.1　数据处理器 1
1.1.2　可编程数据处理器 2
1.1.3　通用图灵机 3
1.2　冯·诺依曼模型 3
1.2.1　4个子系统 3
1.2.2　存储程序概念 4
1.2.3　指令的顺序执行 4
1.3　计算机组成部分 4
1.3.1　计算机硬件 4
1.3.2　数据 4
1.3.3　计算机软件 5
1.4　历史 6
1.4.1　机械计算机器（1930年以前） 6
1.4.2　电子计算机的诞生（1930～1950年） 7
1.4.3　计算机的诞生（1950年至今） 7
1.5　计算机科学作为一门学科 8
1.6　课程纲要 8
1.6.1　第一部分：数据的表示与运算 8
1.6.2　第二部分：计算机硬件 8
1.6.3　第三部分：计算机软件 8
1.6.4　第四部分：数据组织与抽象 9
1.6.5　第五部分：高级话题 9
1.6.6　第六部分：社交媒体和社会话题 9
1.7　章末材料 9
1.8　练习 10
第2章　数字系统 11
2.1　引言 11
2.2　位置化数字系统 11
2.2.1　十进制系统 12
2.2.2　二进制系统 13
2.2.3　十六进制系统 14
2.2.4　八进制系统 15
2.2.5　4种位置化数字系统小结 16
2.2.6　转换 16
2.3　非位置化数字系统 21
2.4　章末材料 22
2.5　练习 23
第3章　数据存储 27
3.1　数据类型 27
3.1.1　计算机内部的数据 28
3.1.2　数据压缩 28
3.1.3　错误检测和纠正 29
3.2　存储数字 29
3.2.1　存储整数 29
3.2.2　3种系统的比较 34
3.2.3　实数 35
3.3　存储文本 41
3.3.1　代码 41
3.4　存储音频 42
3.4.1　采样 42
3.4.2　量化 42
3.4.3　编码 43
3.4.4　声音编码标准 43
3.5　存储图像 43
3.5.1　光栅图 43
3.5.2　矢量图 44
3.6　存储视频 45
3.7　章末材料 45
3.8　练习 47
第4章　数据运算 50
4.1　逻辑运算 50
4.1.1　位层次上的逻辑运算 50
4.1.2　模式层次上的逻辑运算 52
4.2　移位运算 54
4.2.1　逻辑移位运算 54
4.3　算术运算 56
4.3.1　整数的算术运算 56
4.3.2　实数的算术运算 58
4.4　章末材料 58
4.5　练习 59
第5章　计算机组成 61
5.1　引言 61
5.2　中央处理单元 61
5.2.1　算术逻辑单元 62
5.2.2　寄存器 62
5.2.3　控制单元 63
5.3　主存储器 63
5.3.1　地址空间 63
5.3.2　存储器的类型 64
5.3.3　存储器的层次结构 65
5.3.4　高速缓冲存储器 65
5.4　输入/输出子系统 66
5.4.1　非存储设备 66
5.4.2　存储设备 66
5.5　子系统的互连 70
5.5.1　CPU和存储器的连接 70
5.5.2　I/O设备的连接 71
5.5.3　输入／输出设备的寻址 73
5.6　程序执行 74
5.6.1　机器周期 74
5.6.2　输入／输出操作 75
5.7　不同的体系结构 77
5.7.1　CISC 77
5.7.2　RISC 77
5.7.3　流水线 77
5.7.4　并行处理 78
5.8　简单计算机 79
5.8.1　CPU 80
5.8.2　主存 80
5.8.3　输入/输出子系统 80
5.8.4　指令集 81
5.8.5　处理指令 82
5.8.6　存储程序和数据 83
5.8.7　指令周期 83
5.8.8　另一个例子 85
5.8.9　可重用性 87
5.9　章末材料 87
5.10　练习 89
第6章　计算机网络和因特网 92
6.1　引言 92
6.1.1　网络 92
6.1.2　因特网 93
6.1.3　硬件和软件 95
6.1.4　协议分层 95
6.1.5　TCP/IP协议族 97
6.2　应用层 99
6.2.1　提供服务 100
6.2.2　应用层模式 100
6.2.3　标准客户机-服务器应用 101
6.2.4　文件传输协议 103
6.2.5　电子邮件 104
6.2.6　TELNET 105
6.2.7　安全外壳 106
6.2.8　域名系统 106
6.2.9　端到端模式 108
6.3　传输层 109
6.3.1　传输层服务 110
6.3.2　传输层协议 111
6.4　网络层 111
6.4.1　网络层提供的服务 112
6.4.2　网络层协议 114
6.5　数据链路层 116
6.5.1　节点和链接 117
6.5.2　局域网 118
6.5.3　广域网 120
6.6　物理层 122
6.6.1　数据和信号 122
6.6.2　数字化传输 124
6.6.3　模拟传输 124
6.7　传输介质 125
6.7.1　导向介质 125
6.7.2　非导向介质：无线 126
6.8　章末材料 127
6.9　练习 129
第7章　操作系统 132
7.1　引言 132
7.1.1　操作系统 132
7.1.2　自举过程 133
7.2　演化 133
7.2.1　批处理系统 133
7.2.2　分时系统 133
7.2.3　个人系统 134
7.2.4　并行系统 134
7.2.5　分布式系统 134
7.2.6　实时系统 134
7.3　组成部分 134
7.3.1　用户界面 135
7.3.2　内存管理器 135
7.3.3　进程管理器 138
7.3.4　文件管理器 142
7.4　主流操作系统 142
7.4.1　UNIX 143
7.4.2　Linux 144
7.4.3　Windows 144
7.5　章末材料 145
7.6　练习 147
第8章　算法 149
8.1　概念 149
8.1.1　非正式定义 149
8.1.2　示例 149
8.1.3　定义动作 151
8.1.4　细化 151
8.1.5　泛化 152
8.2　三种结构 152
8.2.1　顺序 152
8.2.2　判断 152
8.2.3　循环 152
8.3　算法的表示 153
8.3.1　UML 153
8.3.2　伪代码 153
8.4　更正式的定义 155
8.4.1　定义良好 156
8.4.2　明确步骤 156
8.4.3　产生结果 156
8.4.4　在有限的时间内终止 156
8.5　基本算法 156
8.5.1　求和 156
8.5.2　乘积 157
8.5.3　最大和最小 157
8.5.4　排序 157
8.5.5　查找 161
8.6　子算法 163
8.6.1　结构图 163
8.7　递归 164
8.7.1　迭代的定义 164
8.7.2　递归的定义 164
8.8　章末材料 166
8.9　练习 167
第9章　程序设计语言 170
9.1　演化 170
9.1.1　机器语言 170
9.1.2　汇编语言 171
9.1.3　高级语言 171
9.2　翻译 172
9.2.1　编译 172
9.2.2　解释 172
9.2.3　翻译过程 173
9.3　编程模式 173
9.3.1　过程式模式 174
9.3.2　面向对象模式 176
9.3.3　函数式模式 177
9.3.4　声明式模式 179
9.4　共同概念 179
9.4.1　标识符 179
9.4.2　数据类型 179
9.4.3　变量 180
9.4.4　字面值 180
9.4.5　常量 181
9.4.6　输入和输出 181
9.4.7　表达式 181
9.4.8　语句 182
9.4.9　子程序 184
9.5　章末材料 187
9.6　练习 188
第10章　软件工程 191
10.1　软件生命周期 191
10.1.1　开发过程模型 191
10.2　分析阶段 192
10.2.1　面向过程分析 192
10.2.2　面向对象分析 193
10.3　设计阶段 194
10.3.1　面向过程设计 194
10.3.2　面向对象设计 195
10.4　实现阶段 195
10.4.1　语言的选择 196
10.4.2　软件质量 196
10.5　测试阶段 197
10.5.1　白盒测试 197
10.5.2　黑盒测试 199
10.6　文档 199
10.6.1　用户文档 199
10.6.2　系统文档 199
10.6.3　技术文档 200
10.7　章末材料 200
10.8　练习 201
第11章　数据结构 203
11.1　数组 203
11.1.1　数组名与元素名 205
11.1.2　多维数组 205
11.1.3　存储配置 205
11.1.4　数组操作 206
11.1.5　字符串 207
11.1.6　数组的应用 207
11.2　记录 208
11.2.1　记录名与域名 208
11.2.2　记录与数组的比较 208
11.2.3　记录数组 209
11.2.4　数组与记录数组 209
11.3　链表 209
11.3.1　数组与链表 210
11.3.2　链表名与节点名 211
11.3.3　链表操作 211
11.3.4　链表的应用 218
11.4　章末材料 218
11.5　练习 219
第12章　抽象数据类型 221
12.1　背景 221
12.1.1　简单抽象数据类型 221
12.1.2　复杂抽象数据类型 222
12.1.3　定义 222
12.1.4　抽象数据类型的模型 222
12.1.5　实现 223
12.2　栈 223
12.2.1　栈的操作 223
12.2.2　栈的抽象数据类型 224
12.2.3　栈的应用 224
12.2.4　栈的实现 226
12.3　队列 227
12.3.1　队列的操作 227
12.3.2　队列的抽象数据类型 228
12.3.3　队列的应用 229
12.3.4　队列的实现 230
12.4　广义线性表 230
12.4.1　广义线性表的操作 231
12.4.2　广义线性表的抽象数据类型 232
12.4.3　广义线性表的应用 233
12.4.4　广义线性表的实现 234
12.5　树 234
12.5.1　二叉树 235
12.5.2　二叉树的操作 236
12.5.3　二叉树的应用 237
12.5.4　二叉树的实现 238
12.5.5　二叉搜索树 238
12.6　图 240
12.7　章末材料 240
12.8　练习 242
第13章　文件结构 244
13.1　引言 244
13.1.1　顺序存取 244
13.1.2　随机存取 244
13.2　顺序文件 245
13.2.1　更新顺序文件 245
13.3　索引文件 246
13.3.1　倒排文件 247
13.4　散列文件 247
13.4.1　散列方法 248
13.4.2　冲突 249
13.5　目录 251
13.5.1　UNIX操作系统中的目录 251
13.6　文本文件与二进制文件 252
13.6.1　文本文件 253
13.6.2　二进制文件 253
13.7　章末材料 253
13.8　练习 255
第14章　数据库 257
14.1　引言 257
14.1.1　定义 257
14.1.2　数据库的优点 257
14.1.3　数据库管理系统 258
14.2　数据库体系结构 259
14.2.1　内层 259
14.2.2　概念层 259
14.2.3　外层 259
14.3　数据库模型 259
14.3.1　层次模型 259
14.3.2　网状模型 260
14.3.3　关系模型 260
14.4　关系数据库模型 260
14.4.1　关系 260
14.4.2　关系的操作 261
14.5　数据库设计 265
14.5.1　实体关系模型 266
14.5.2　从E-R图到关系 266
14.5.3　规范化 267
14.6　其他数据库模型 268
14.6.1　分布式数据库 268
14.6.2　面向对象数据库 269
14.7　章末材料 269
14.8　练习 271
第15章　数据压缩 273
15.1　引言 273
15.2　无损压缩方法 273
15.2.1　游程长度编码 274
15.2.2　赫夫曼编码 275
15.2.3　Lempel Ziv编码 276
15.3　有损压缩方法 279
15.3.1　图像压缩：JPEG 280
15.3.2　视频压缩：MPEG 282
15.3.3　音频压缩 283
15.4　章末材料 283
15.5　练习 285
第16章　安全 287
16.1　引言 287
16.1.1　安全目标 287
16.1.2　攻击 288
16.1.3　服务和技术 289
16.2　机密性 289
16.2.1　对称密钥密码术 290
16.2.2　非对称密钥密码术 295
16.3　其他安全服务 299
16.3.1　消息完整性 299
16.3.2　消息验证 300
16.3.3　数字签名 301
16.3.4　实体验证 304
16.3.5　密钥管理 306
16.4　防火墙 309
16.4.1　包过滤防火墙 310
16.4.2　代理防火墙 311
16.5　章末材料 311
16.6　练习 313
第17章　计算理论 316
17.1　简单语言 316
17.1.1　递增语句 316
17.1.2　递减语句 316
17.1.3　循环语句 317
17.1.4　简单语言的威力 317
17.2　图灵机 319
17.2.1　图灵机组成部件 319
17.2.2　对简单语言的模拟 321
17.2.3　邱奇-图灵论题 323
17.3　歌德尔数 324
17.3.1　表示一个程序 324
17.3.2　翻译一个数字 324
17.4　停机问题 325
17.4.1　停机问题是不可解的 325
17.5　问题的复杂度 326
17.5.1　不可解问题 327
17.5.2　可解问题 327
17.6　章末材料 328
17.7　练习 329
第18章　人工智能 331
18.1　引言 331
18.1.1　什么是人工智能 331
18.1.2　人工智能简史 331
18.1.3　图灵测试 332
18.1.4　智能体 332
18.1.5　编程语言 332
18.2　知识表示 332
18.2.1　语义网 333
18.2.2　框架 333
18.2.3　谓词逻辑 334
18.2.4　基于规则的系统 338
18.3　专家系统 339
18.3.1　抽取知识 339
18.3.2　抽取事实 340
18.3.3　体系结构 340
18.4　感知 341
18.4.1　图像处理 341
18.4.2　语言理解 343
18.5　搜索 345
18.5.1　搜索方法 345
18.6　神经网络 348
18.6.1　生物神经元 348
18.6.2　感知器 349
18.6.3　多层网络 350
18.6.4　应用 350
18.7　章末材料 350
18.8　练习 351
第19章　社交媒体导论 354
19.1　引言 354
19.2　Facebook 355
19.2.1　梗概 355
19.2.2　网页 356
19.2.3　成员 357
19.2.4　获取Facebook的服务 358
19.2.5　朋友 358
19.2.6　交换信息 359
19.3　Twitter 360
19.3.1　梗概 360
19.3.2　页面 361
19.3.3　成员 361
19.3.4　获取Twitter的服务 362
19.3.5　跟随以及被跟随 362
19.3.6　发送推文 363
19.3.7　接收推文 364
19.4　章末材料 364
19.5　练习 365
第20章　社会和道德问题 366
20.1　道德原则 366
20.1.1　道德规则 366
20.1.2　使用 366
20.1.3　社会契约 366
20.2　知识产权 367
20.2.1　知识产权的类型 367
20.3　隐私 368
20.4　计算机犯罪 368
20.4.1　攻击的类型 368
20.4.2　动机 369
20.4.3　攻击保护 369
20.4.4　花费 369
20.5　黑客 369
20.6　章末材料 369
20.7　练习 370
附录A　Unicode 372
附录B　UML 376
附录C　伪代码 384
附录D　结构图 387
附录E　布尔代数和逻辑电路 390
附录F　C、C++和Java程序示例 403
附录G　数学知识 410
附录H　错误检测和纠正 417
附录I　符号加绝对值整数的加减法 428
附录J　实数的加减法 431
缩略语 434
术语表 436
· · · · · · (收起)