第0章 绪论 1
0.1算法的作用 1
0.2计算机器的由来 3
0.3算法的科学 7
0.4抽象 8
0.5学习大纲 8
0.6社会影响 9
社会问题 11
课外阅读 12
第1章 数据存储 13
1.1位和位存储 13
1.1.1布尔运算 13
1.1.2门和触发器 14
1.1.3十六进制记数法 17
1.2主存储器 18
1.2.1存储器结构 18
1.2.2存储器容量的度量 19
1.3海量存储器 20
1.3.1磁学系统 20
1.3.2光学系统 22
1.3.3闪存驱动器 23
1.3.4文件存储及检索 24
1.4用位模式表示信息 25
1.4.1文本的表示 25
1.4.2数值的表示 26
1.4.3图像的表示 27
1.4.4声音的表示 28
1.5二进制系统 29
1.5.1二进制记数法 29
1.5.2二进制加法 31
1.5.3二进制中的小数 32
1.6整数存储 33
1.6.1二进制补码记数法 33
1.6.2余码记数法 36
1.7小数的存储 37
1.7.1浮点记数法 37
1.7.2截断误差 39
1.8数据压缩 41
1.8.1通用的数据压缩技术 41
1.8.2图像压缩 43
1.8.3音频和视频压缩 44
1.9通信差错 45
1.9.1奇偶校验位 45
1.9.2纠错编码 46
复习题 47
社会问题 50
课外阅读 51
第2章 数据操控 52
2.1计算机体系结构 52
2.1.1 CPU基础知识 52
2.1.2存储程序概念 53
2.2机器语言 54
2.2.1指令系统 54
2.2.2一种演示用的机器语言 56
2.3程序执行 58
2.3.1程序执行的一个例子 60
2.3.2程序与数据 62
2.4算术／逻辑指令 63
2.4.1逻辑运算 63
2.4.2循环移位及移位运算 65
2.4.3算术运算 66
2.5与其他设备通信 67
2.5.1控制器的作用 67
2.5.2直接内存存取 68
2.5.3握手 69
2.5.4流行的通信媒介 69
2.5.5通信速率 70
2.6其他体系结构 70
2.6.1流水线 70
2.6.2多处理器计算机 71
复习题 72
社会问题 77
课外阅读 77
第3章 操作系统 79
3.1操作系统的历史 79
3.2操作系统的体系结构 82
3.2.1软件概述 82
3.2.2操作系统组件 84
3.2.3系统启动 86
3.3协调机器的活动 88
3.3.1进程的概念 88
3.3.2进程管理 88
3.4处理进程间的竞争 90
3.4.1信号量 90
3.4.2死锁 91
3.5安全性 93
3.5.1来自机器外部的攻击 93
3.5.2来自机器内部的攻击 94
复习题 95
社会问题 98
课外阅读 98
第4章 组网及因特网 99
4.1网络基础 99
4.1.1网络分类 99
4.1.2协议 100
4.1.3网络互连 102
4.1.4进程间通信的方法 104
4.1.5分布式系统 105
4.2因特网 106
4.2.1因特网体系结构 106
4.2.2因特网编址 108
4.2.3因特网应用 109
4.3万维网 113
4.3.1万维网实现 113
4.3.2 HTML 114
4.3.3 XML 117
4.3.4客户端和服务器端的活动 118
4.4因特网协议 119
4.4.1因特网软件的分层方法 119
4.4.2 TCP/IP协议簇 122
4.5安全性 123
4.5.1入侵的形式 124
4.5.2防护和对策 125
4.5.3加密 126
4.5.4网络安全的法律途径 128
复习题 130
社会问题 131
课外阅读 132
第5章 算法 134
5.1算法的概念 134
5.1.1概览 134
5.1.2算法的正式定义 135
5.1.3算法的抽象本质 136
5.2算法的表示 136
5.2.1原语 137
5.2.2伪代码 139
5.3算法的发现 142
5.3.1问题求解的艺术 142
5.3.2入门 144
5.4迭代结构 146
5.4.1顺序搜索法 147
5.4.2循环控制 148
5.4.3插入排序算法 151
5.5递归结构 154
5.5.1二分搜索算法 154
5.5.2递归控制 159
5.6有效性和正确性 160
5.6.1算法有效性 160
5.6.2软件验证 163
复习题 167
社会问题 171
课外阅读 171
第6章 程序设计语言 172
6.1历史回顾 172
6.1.1早期程序设计语言 172
6.1.2独立并超越机器 174
6.1.3程序设计范型 175
6.2传统的程序设计概念 179
6.2.1变量和数据类型 180
6.2.2数据结构 181
6.2.3常量和字面量 182
6.2.4赋值语句 183
6.2.5控制语句 184
6.2.6注释 187
6.3过程单元 188
6.3.1过程 188
6.3.2参数 189
6.3.3函数 192
6.4语言实现 193
6.4.1翻译过程 193
6.4.2软件开发包 198
6.5面向对象程序设计 199
6.5.1类和对象 199
6.5.2构造器 202
6.5.3附加特性 202
6.6程序设计中的并发活动 204
6.7说明性程序设计 206
6.7.1逻辑推演 206
6.7.2 Prolog 208
复习题 210
社会问题 213
课外阅读 214
第7章 软件工程 215
7.1软件工程学科 215
7.2软件生命周期 217
7.2.1周期是个整体 217
7.2.2传统的开发阶段 218
7.3软件工程方法 220
7.4模块化 221
7.4.1模块式实现 222
7.4.2耦合 224
7.4.3内聚 225
7.4.4信息隐藏 225
7.4.5构件 226
7.5行业工具 227
7.5.1较老的工具 227
7.5.2统一建模语言 228
7.5.3设计模式 232
7.6质量保证 233
7.6.1质量保证的范围 233
7.6.2软件测试 234
7.7文档编制 235
7.8人机界面 236
7.9软件所有权和责任 238
复习题 240
社会问题 242
课外阅读 243
第8章 数据抽象 244
8.1数据结构基础 244
8.1.1数组 244
8.1.2列表、栈和队列 245
8.1.3树 245
8.2相关概念 247
8.2.1抽象 247
8.2.2静态结构与动态结构 247
8.2.3指针 248
8.3数据结构的实现 248
8.3.1数组的存储 248
8.3.2列表的存储 251
8.3.3栈和队列的存储 254
8.3.4二叉树的存储 255
8.3.5数据结构的操作 257
8.4.个简短案例 259
8.5定制的数据类型 263
8.5.1用户自定义数据类型 263
8.5.2抽象数据类型 264
8.6类和对象 266
8.7机器语言中的指针 267
复习题 269
社会问题 273
课外阅读 274
第9章 数据库系统 275
9.1数据库基础 275
9.1.1数据库系统的重要性 275
9.1.2模式的作用 276
9.1.3数据库管理系统 277
9.1.4数据库模型 278
9.2关系模型 279
9.2.1关系设计中的问题 279
9.2.2关系运算 282
9.2.3 SQL 285
9.3面向对象数据库 287
9.4维护数据库的完整性 289
9.4.1提交／回滚协议 289
9.4.2锁定 290
9.5传统的文件结构 291
9.5.1顺序文件 291
9.5.2索引文件 294
9.5.3散列文件 294
9.6数据挖掘 297
9.7数据库技术的社会影响 299
复习题 300
社会问题 303
课外阅读 304
第10章 计算机图形学 305
10.1计算机图形学的范围 305
10.2 3D图形概述 307
10.3建模 308
10.3.1单个物体的建模 308
10.3.2整个场景的建模 313
10.4渲染 314
10.4.1光-表面交互 314
10.4.2裁剪、扫描转换和隐藏面的消除 316
10.4.3着色 319
10.4.4渲染-流水线硬件 320
10.5处理全局照明 321
10.5.1光线跟踪 321
10.5.2辐射度 323
10.6动画 323
10.6.1动画基础 323
10.6.2运动学和动力学 325
10.6.3动画制作过程 326
复习题 326
社会问题 328
课外阅读 329
第11章 人工智能 330
11.1智能与机器 330
11.1.1智能体 330
11.1.2研究方法 332
11.1.3图灵测试 332
11.2感知 333
11.2.1理解图像 333
11.2.2语言处理 335
11.3推理 338
11.3.1产生式系统 338
11.3.2搜索树 340
11.3.3启发式搜索 342
11.4其他研究领域 346
11.4.1知识的表达和处理 346
11.4.2学习 347
11.4.3遗传算法 349
11.5人工神经网络 349
11.5.1基本特性 350
11.5.2训练人工神经网络 351
11.5.3联想记忆 353
11.6机器人学 356
11.7后果的思考 358
复习题 359
社会问题 363
课外阅读 364
第12章 计算理论 365
12.1函数及其计算 365
12.2图灵机 367
12.2.1图灵机的原理 367
12.2.2丘奇-图灵论题 369
12.3通用程序设计语言 370
12.3.1 Bare Bones语言 370
12.3.2用Bare Bones语言编程 372
12.3.3 Bare Bones的通用性 373
12.4一个不可计算的函数 375
12.4.1停机问题 375
12.4.2停机问题的不可解性 376
12.5问题的复杂性 379
12.5.1问题复杂性的度量 379
12.5.2多项式问题与非多项式问题 382
12.5.3 NP问题 383
12.6公钥密码学 386
12.6.1模表示法 386
12.6.2 RSA公钥加密系统 387
复习题 389
社会问题 392
课外阅读 392
附录A ASCII码 394
附录B 处理二进制补码表示的电路 395
附录C 一种简单的机器语言 397
附录D 高级编程语言 399
附录E 迭代结构与递归结构的等价性 401
索引 403