计算机科学导论――基于计算思维的思想与方法(第4版)

绪论 课程导学 1
§0．1 课程教学定位 1
§0．2 课程教学思维 2
§0．3 课程知识结构 4
§0．4 课程教学辅导 7

基本概念――计算工具、计算学科、计算思维
第1章 计算机科学概述 8
§1．1 人类计算工具的进步 8
1．1．1 手工时代 9
1．1．2 机械时代 10
1．1．3 机电时代 13
1．1．4 电子时代 14
§1．2 计算机科学体系的形成 16
1．2．1 布尔提出的逻辑代数 16
1．2．2 香农提出的逻辑电路 17
1．2．3 维纳提出的计算机设计原则 18
1．2．4 图灵提出的图灵机和图灵测试 18
1．2．5 冯??诺依曼提出的EDVAC 20
§1．3 基于Neumann结构的现代计算机 22
1．3．1 计算机的组成 22
1．3．2 计算机的主要特点 24
1．3．3 计算机的基本性能 25
1．3．4 计算机的主要应用 26
§1．4 突破与超越Neumann机结构 28
1．4．1 突破Neumann机的体系结构 28
1．4．2 突破Neumann机的组成结构 31
1．4．3 超越Neumann机的体系结构 32
本章小结 34
习题1 34
第2章 计算机学科体系 36
§2．1 计算机学科体系的构建 36
2．1．1 科学与学科的概念 36
2．1．2 计算作为一门学科 37
2．1．3 CC2005学科体系 39
2．1．4 CCC2002学科体系 42
§2．2 计算机学科方法论 44
2．2．1 计算机学科方法论概念 44
2．2．2 计算机学科的三个形态 45
2．2．3 计算机学科的核心概念 46
2．2．4 计算机学科的典型方法 47
§2．3 计算机学科中的数学方法 49
2．3．1 数学方法及其作用体现 49
2．3．2 构造性数学与证明方法 50
2．3．3 计算机学科的根本问题 52
§2．4 计算机学科的经典问题 53
2．4．1 理论意义上的不可计算问题――图论问题 53
2．4．2 现实意义上的不可计算问题――计算复杂性 56
2．4．3 理论意义上的可计算问题――计算机智能问题 59
2．4．4 现实意义上的可计算问题――并发控制问题 61
本章小结 62
习题2 63
第3章 计算思维及其作用体现 64
§3．1 计算思维及其本质特性 64
3．1．1 人类思维的类别 64
3．1．2 计算思维的概念 67
3．1．3 计算思维的本质 68
3．1．4 计算思维的特征 69
§3．2 计算思维的问题求解 70
3．2．1 问题求解的数学建模 70
3．2．2 问题求解的基本策略 71
3．2．3 问题求解的过程抽象 73
§3．3 计算思维与计算机学科 77
3．3．1 计算思维本质与学科形态的关系 77
3．3．2 计算思维在计算机学科中的体现 79
§3．4 计算思维的学科作用与能力培养 84
3．4．1 计算思维与计算机教育相互促进 84
3．4．2 计算思维有助于跨越专业鸿沟 85
3．4．3 计算思维有助于其他学科发展 86
3．4．4 计算思维能力培养的基本策略 88
本章小结 90
习题3 90
基本方法：机器计算的思维方法
第4章 数据表示的基本思维 92
§4．1 数制及其转换――“人机兼容”的基本思维 92
4．1．1 进位计数制 92
4．1．2 数制之间的转换 95
§4．2 数值数据的编码表示――“语义符号数值化”的基本思维 98
4．2．1 整型数的编码表示 98
4．2．2 实型数的编码表示 103
§4．3 字符数据的编码表示――“字符信息数字化”的基本思维 105
4．3．1 西文字符的编码表示 105
4．3．2 汉字字符的编码表示 107
4．3．3 综合实例――字符处理 110
§4．4 逻辑数据的编码表示――“逻辑符号数字化”的基本思维 111
4．4．1 逻辑代数概念 111
4．4．2 逻辑代数运算 112
§4．5 多媒体数据的编码表示――“动态信息数值化”的基本思维 114
4．5．1 多媒体基本概念 114
4．5．2 音频数字化的编码表示 115
4．5．3 图像数字化的编码表示 116
4．5．4 视频数字化的编码表示 118
4．5．5 计算机动画简介 119
本章小结 119
习题4 120
第5章 计算系统的基本思维 122
§5．1 计算系统的基本概念――“系统组成”的基本思维 122
5．1．1 计算机硬件系统 122
5．1．2 计算机软件系统 123
5．1．3 计算机操作系统 124
5．1．4 软件与硬件的关系 127
§5．2 处理器系统――“控制执行”的基本思维 128
5．2．1 处理器的结构组成 128
5．2．2 计算机指令系统 130
5．2．3 操作系统对处理器的管理 131
§5．3 存储器系统――“存储优化组合”的基本思维 135
5．3．1 内存储器 135
5．3．2 外存储器 137
5．3．3 存储体系 138
5．3．4 操作系统对存储器的管理 140
5．3．5 综合实例――计算机的工作过程 142
§5．4 文件管理系统――“长治久安”的基本思维 144
5．4．1 文件与文件系统 144
5．4．2 文件组织与结构 145
5．4．3 文件目录和目录结构 146
§5．5 总线系统和输入/输出系统――“组织与协调”的基本思维 148
5．5．1 总线系统 148
5．5．2 输入/输出设备 149
5．5．3 输入/输出接口 150
5．5．4 操作系统对I/O的管理 150
本章小结 153
习题5 153
第6章 程序设计的基本思维 155
§6．1 程序设计概念――“问题抽象”的基本思维 155
6．1．1 程序设计与问题求解 155
6．1．2 程序设计的基本抽象 157
§6．2 程序设计语言――“语言抽象”的基本思维 158
6．2．1 程序设计语言的演化 158
6．2．2 程序设计语言的构成 162
6．2．3 计算机源程序的翻译 165
§6．3 程序设计方法――“方法抽象”的基本思维 168
6．3．1 面向过程方法 168
6．3．2 面向对象方法 171
6．3．3 程序与软件的关系 173
§6．4 软件工程方法――“过程抽象”的基本思维 174
6．4．1 软件工程概念 174
6．4．2 软件工程目标 176
6．4．3 软件工程原则 177
6．4．4 软件开发模型 178
6．4．5 软件开发方法 181
本章小结 184
习题6 184
基本理论：问题求解的数学方法
第7章 问题求解的算法基础 186
§7．1 算法――问题求解的核心 186
7．1．1 算法的基本概念 186
7．1．2 算法的设计要求 187
7．1．3 算法的复杂性 188
7．1．4 算法的描述方法 190
7．2 数值数据求解――算法策略 192
7．2．1 穷举算法 192
7．2．3 递推算法 194
7．2．4 迭代算法 196
7．2．5 递归算法 197
7．2．6 分治算法 198
7．2．7 贪心算法 199
7．2．8 动态规划 199
§7．3 非数值数据处理――数据结构 200
7．3．1 线性表结构 201
7．3．2 栈结构 203
7．3．3 队列结构 203
7．3．4 树结构 204
§7．4 数据元素操作――查找和排序 206
7．4．1 查找算法 206
7．4．2 排序算法 208
本章小结 213
习题7 214
*第8章 问题求解的近似计算 215
§8．1 定积分的近似计算 215
8．1．1 近似计算方法 215
8．1．2 计算求解方法 219
§8．2 有限元方法 223
8．2．1 有限元方法的基本概念 223
8．2．2 有限元方法的计算思维 224
§8．3 随机事件及其概率 223
8．2．1 随机事件 223
8．2．2 随机概率 224
8．3．3 随机变量 226
§8．4 蒙特卡罗方法 227
8．4．1 蒙特卡罗方法的概念 228
8．4．2 蒙特卡罗方法求定积分 229
§8．5 圆周率的近似计算 231
8．5．1 圆周率的计算史 231
8．5．2 蒙特卡罗方法求圆周率 232
8．5．3 研究计算圆周率的意义 233
§8．6 仿生学算法 234
8．6．1 遗传算法的基本概念 235
8．6．2 遗传算法的基本方法 236
8．6．3 群体智能优化算法概念 238
本章小结 239
习题8 240
*第9章 问题求解的离散结构 241
§9．1 数理逻辑 241
9．1．1 数理逻辑引例 241
9．1．2 命题逻辑 242
9．1．3 谓词逻辑 245
9．1．4 数理逻辑在计算机科学中的应用 247
§9．2 集合论 248
9．2．1 集合论引例 248
9．2．2 集合的表示与运算 249
9．2．3 二元关系 251
9．2．4 函数 255
9．2．5 集合论在计算机科学中的应用 256
§9．3 逻辑代数 257
9．3．1 逻辑代数引例 257
9．3．2 逻辑代数的表示 258
9．3．3 逻辑电路的简化 259
9．3．4 代数系统在计算机科学中的应用 260
§9．4 图论 261
9．4．1 图论引例 261
9．4．2 图论的基本概念 262
9．4．3 图的矩阵表示 264
9．4．4 路径、回路与连通图 265
9．4．5 欧拉图和哈密尔顿图 266
9．4．6 *短路径和*小生成树 268
9．4．7 图论在计算机科学中的应用 270
本章小结 271
习题9 271
基本技术：数据共享与前沿技术
第10章 数据库技术 273
§10．1 数据库技术概述――抽象（Ⅰ） 273
10．1．1 数据与信息 273
10．1．2 数据库 275
10．1．3 数据库管理系统 277
10．1．4 数据库系统 277
§10．2 数据模型――抽象（Ⅱ） 279
10．2．1 数据模型概念 279
10．2．2 概念数据模型 281
10．2．3 关系数据模型 283
10．2．4 关系数据模式 285
§10．3 关系数据库――理论 287
10．3．1 关系代数运算 287
10．3．2 关系数据查询优化 291
10．3．3 关系模式的规范化 292
10．3．4 关系数据的一致性 293
§10．4 构建数据库应用系统――设计 294
10．4．1 数据库应用系统设计要求 295
10．4．2 数据库应用系统设计过程 296
本章小结 300
习题10 300
第11章 计算机网络技术 302
§11．1 计算机网络概述――抽象 302
11．1．1 计算机网络的基本概念 302
11．1．2 网络的基本类型 303
11．1．3 OSI/RM体系结构 305
11．1．4 TCP/IP体系结构 307
§11．2 网络数据传输――理论 308
11．2．1 数据通信 308
11．2．2 数据传输方式 309
11．2．3 多路复用传输 311
11．2．4 数据调制编码 312
11．2．5 数据分组交换 313
§11．3 网络的结构组成――设计（Ⅰ） 314
11．3．1 网络的拓扑结构 314
11．3．2 网络的逻辑结构 316
11．3．3 计算机网络互连设备 317
§11．4 计算机因特网――设计（Ⅱ） 319
11．4．1 Internet的IP地址 319
11．4．2 Internet的域名系统 320
11．4．3 Internet提供的服务 322
§11．5 计算机信息安全技术――理论与设计 323
11．5．1 防病毒技术 323
11．5．2 防黑客技术 324
11．5．3 防火墙技术 325
11．5．4 信息加密技术 325
11．5．5 数字认证技术 328
本章小结 329
习题11 329
第12章 计算机前沿技术 331
§12．1 人工智能技术 331
12．1．1 人工智能的概念 331
12．1．2 人工智能关键技术 333
12．1．3 人工智能技术应用 334
§12．2 虚拟现实技术 336
12．2．1 虚拟现实的概念 336
12．2．2 虚拟现实关键技术 337
12．2．3 虚拟现实技术应用 338
§12．3 移动互联网技术 340
12．3．1 移动互联网的概念 340
12．3．2 移动互联网关键技术 341
12．3．3 移动互联网技术应用 342
§12．4 物联网技术 343
12．4．1 物联网的概念 344
12．4．2 物联网关键技术 345
12．4．3 物联网技术应用 346
§12．5 云计算技术 348
12．5．1 云计算的概念 348
12．5．2 云计算关键技术 349
12．5．3 云计算技术应用 350
§12．6 大数据技术 351
12．5．1 大数据的概念 352
12．6．2 大数据关键技术 353
12．6．3 大数据技术应用 354
本章小结 355
习题12 355
参考文献 357