第0章 简介 1
0.1 算法的研究 2
0.2 计算机的起源 4
0.3 算法的科学 7
0.4 抽象的角色 9
0.5 社会的反作用 10
0.6 社会问题 11
0.7 课外阅读 12
第一部分 计算机体系结构 17
第1章 数据存储 17
1.1 位与它们的存储 18
1.1.1 门与触发器 18
1.1.2 其他存储技术 21
1.1.3 十六进制表示法 22
1.2 主存储器 24
1.2.1 存储器结构 24
1.2.2 度量主存容量 25
1.3 大容量存储器 26
1.3.1 磁盘 26
1.3.2 光盘(CD) 28
1.3.3 磁带 28
1.3.4 文件存储与检索 29
1.4 以二进制编码表示数据 31
1.4.1 文本的表示 31
1.4.2 数字值的表示 32
1.4.3 图像的表示 34
1.4.4 音频的表示 35
1.5 二进制系统 37
1.5.1 二进制加法 37
1.5.2 二进制中的分数 38
1.6 整数的存储 39
1.6.1 二进制补码表示法 39
1.6.2 余码 42
1.7.1 浮点记数法 44
1.7 小数的存储 44
1.7.2 截断误差 45
1.8 数据压缩 47
1.8.1 普通数据压缩技术 47
1.8.2 图像的压缩 50
1.9 通信错误 51
1.9.1 奇偶校验位 51
1.9.2 错误纠正码 52
1.10 本章复习题 54
1.11 社会问题 59
1.12 课外阅读 60
第2章 数据操作 61
2.1 计算机体系结构 62
2.2 机器语言 64
2.2.1 指令系统 64
2.2.2 一种说明性的机器语言 65
2.3 程序的执行 68
2.3.1 程序执行的一个例子 69
2.3.2 程序与数据 72
2.4 算术逻辑指令 74
2.4.1 逻辑运算 74
2.4.2 循环移位操作 75
2.4.3 算术操作 76
2.5 与其他设备的通信 77
2.5.1 通信控制器 78
2.5.2 数据传输速率 80
2.6.2 多处理器计算机 81
2.6 其他体系结构 81
2.6.1 流水线 81
2.7 本章复习题 83
2.8 社会问题 89
2.9 课外阅读 90
第二部分 软件 93
第3章 操作系统与网络 93
3.1 操作系统的变革 94
3.1.1 单处理器系统 94
3.1.2 多处理器系统 96
3.2.1 软件概览 97
3.2 操作系统体系结构 97
3.2.2 操作系统的组成 98
3.2.3 系统启动 101
3.3 协调机器活动 102
3.3.1 进程的概念 102
3.3.2 进程管理 102
3.3.3 客户/服务器模型 104
3.4.1 旗语 105
3.4 进程间的竞争处理 105
3.4.2 死锁 106
3.5 网络 108
3.5.1 网络基础 109
3.5.2 互联网 110
3.6 网络协议 115
3.6.1 控制传输协议 115
3.6.2 互联网软件的分层结构 117
3.6.3 TCP/IP协议族 120
3.7 安全 121
3.8 本章复习题 124
3.9 社会问题 127
3.10 课外阅读 128
第4章 算法 129
4.1 算法的概念 130
4.1.1 概览 130
4.1.2 算法的正式定义 130
4.1.3 算法的抽象本质 131
4.2 算法表示 132
4.2.1 原语 132
4.2.2 伪码 135
4.3 算法发现 139
4.3.1 解决问题的技巧 139
4.3.2 进入问题 141
4.4 迭代结构 144
4.4.1 顺序查找法 144
4.4.2 循环控制 145
4.4.3 插入排序法 148
4.5 递归结构 151
4.5.1 二分查找法 152
4.5.2 递归控制 156
4.6 效率和正确性 157
4.6.1 算法效率 157
4.6.2 软件确认 160
4.7 本章复习题 165
4.8 社会问题 170
4.9 课外阅读 171
第5章 程序设计语言 172
5.1 历史回顾 173
5.1.1 早期程序设计语言 173
5.1.2 机器独立性及其超越 175
5.1.3 程序设计范型 176
5.2 传统的程序设计概念 180
5.2.1 变量和数据类型 181
5.2.2 数据结构 183
5.2.3 常数和文字 185
5.2.4 赋值语句 185
5.2.5 控制语句 186
5.2.6 注释 189
5.3 过程单元 190
5.3.1 过程 190
5.3.2 参数 192
5.3.3 函数 195
5.3.4 输入/输出语句 196
5.4 语言的执行 198
5.4.1 翻译进程 198
5.4.2 连接与加载 203
5.4.3 软件开发包 204
5.5 面向对象程序设计 205
5.5.1 类和对象 205
5.5.2 构造函数 207
5.5.3 附加特性 208
5.6 程序设计的并发行为 210
5.7 声明程序设计 212
5.7.1 逻辑推演 212
5.7.2 Prolog 215
5.8 本章复习题 217
5.9 社会问题 223
5.10 课外阅读 223
第6章 软件工程 225
6.1 软件工程学科 226
6.2 软件生命周期 227
6.2.1 作为整体的周期 228
6.2.2 传统开发阶段 229
6.2.3 趋势 230
6.3 模块化 231
6.3.1 模块的实现 232
6.3.2 耦合 233
6.3.3 聚合 235
6.4.1 自顶向下与自底向上 236
6.4 设计方法学 236
6.4.2 设计模式 237
6.4.3 开放源码运动 238
6.5 专业工具 239
6.6 测试 242
6.7 文档 243
6.8 软件的所有权和责任 245
6.9 本章复习题 247
6.11 课外阅读 250
6.10 社会问题 250
第三部分 数据组织 255
第7章 数据结构 255
7.1 数据结构基础 256
7.1.1 抽象 256
7.1.2 静态与动态结构的比较 256
7.1.3 指针 256
7.2 数组 257
7.3.2 链接表 260
7.3.1 邻接表 260
7.3 表 260
7.3.3 抽象概念表 262
7.4 堆栈 263
7.4.1 回溯 263
7.4.2 栈的实现 265
7.5 队列 266
7.6 树 269
7.6.1 树的实现 270
7.6.2 二叉树包 273
7.7 自定义数据类型 278
7.7.1 用户定义类型 278
7.7.2 类 279
7.8 机器语言中的指针 282
7.9 本章复习题 284
7.10 社会问题 290
7.11 课外阅读 291
第8章 文件结构 292
8.1 操作系统的任务 293
8.2 顺序文件 295
8.2.1 顺序文件的处理 295
8.2.2 文本文件 298
8.2.3 编程概念 300
8.3 索引 302
8.3.1 索引的原理 303
8.3.2 编程概念 305
8.4 散列 305
8.4.1 一个特殊的散列系统 306
8.4.2 分配问题 307
8.4.3 编程思想 309
8.5 本章复习题 311
8.6 社会问题 313
8.7 课外阅读 314
第9章 数据库结构 315
9.1 概论 316
9.2.1 数据库管理系统 318
9.2 数据库的分层实现 318
9.2.2 数据库模型 319
9.3 关系模型 320
9.3.1 关系的设计 320
9.3.2 关系操作 324
9.3.3 执行的问题 327
9.3.4 SQL 328
9.4 面向对象的数据库 330
9.5.1 提交/回滚协议 332
9.5 维持数据完整性 332
9.5.2 锁 333
9.6 数据库技术的社会影响 334
9.7 本章复习题 337
9.8 社会问题 341
9.9 课外阅读 342
第四部分 机器的潜力 345
第10章 人工智能 345
10.1.1 执行与仿真 346
10.1 智能与计算机 346
10.1.2 图灵测试 347
10.1.3 “8数码问题”机器 348
10.2 图像识别 349
10.3 推理 350
10.3.1 产生式系统 351
10.3.2 搜索树 353
10.3.3 启发式搜索 355
10.4 人工神经网络 359
10.4.1 基本概念 359
10.4.2 一个特殊的应用 361
10.4.3 联想记忆 365
10.5 遗传算法 368
10.6 其他研究领域 370
10.6.1 语言处理 370
10.6.2 机器人 373
10.6.3 数据库系统 373
10.6.4 专家系统 374
10.7 考虑的问题 376
10.8 本章复习题 378
10.9 社会问题 382
10.10 课外阅读 383
第11章 计算理论 385
11.1 函数与计算 386
11.2 图灵机 387
11.2.1 图灵机的基本原理 387
11.2.2 Church-Turing论题 390
11.3 通用编程语言 390
11.3.1 原语言 391
11.3.2 利用原语言编程 393
11.3.3 原语言的通用性 394
11.4 不可计算的函数 396
11.4.1 停机问题 396
11.4.2 停机问题的不可解性 397
11.5.1 衡量一个问题的复杂度 400
11.5 问题复杂度 400
11.5.2 多项式对非多项式的问题 403
11.5.3 NP问题 405
11.6 公钥加密系统 407
11.6.1 通过背包问题加密 407
11.6.2 模运算 410
11.6.3 返回加密 411
11.7 本章复习题 414
11.8 社会问题 419
11.9 课外阅读 420
第五部分 附录 423
附录A ASCⅡ码 423
附录B 二进制补码的操作电路 425
附录C 一个简单的机器语言 427
附录D 高级程序设计语言示例 429
附录E 迭代与递归结构的等价性 436
附录F “问题与练习”答案 438
词汇表 472