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

出版者的话

译者序

前言

第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

......(更多)