计算机科学概论(原书第7版)/计算机科学丛书

本书由当今该领域备受赞誉且经验丰富的教育家Nell Dale和John Lewis共同编写，全面介绍计算机科学领域的基础知识，为广大学生勾勒了一幅生动的画卷。就整体而言，全书内容翔实、覆盖面广，旨在向读者展示计算机科学的全貌；从细节上看，本书层次清晰、描述生动，基于计算机系统的洋葱式结构，分别介绍信息层、硬件层、程序设计层、操作系统层、应用程序层和通信层，涉及计算机科学的各个层面。 本书贯穿了计算机系统的各个方面，非常适合作为计算机专业的计算机导论课程教材，为后续专业课程打下坚实的基础；同时还适合作为非计算机专业的计算机总论课程教材，提供计算机系统全面完整的介绍。

内尔?黛尔（Nell Dale） 计算机科学领域广受推崇的教育家。在得克萨斯大学奥斯汀分校执教的二十多年中，她编写了四十多本计算机科学方面的本科生教材。她于得克萨斯大学奥斯汀分校获得了硕士学位和计算机科学博士学位。由于在计算机科学领域做出了卓越贡献，她于1996年获得了ACM SIGCSE计算机科学教育杰出贡献奖，于2001年获得了ACM Karl Karlston杰出教师奖。她于2010年被选为ACM会士。 约翰?路易斯（John Lewis） 计算机科学领域的教育家和作家。他编写的Java软件及程序设计教材十分畅销。他于弗吉尼亚理工大学获得博士学位，并曾在维拉诺瓦大学计算机科学系执教14年，现任教于弗吉尼亚理工大学。执教期间，他获奖无数，包括大学卓越教学奖和Goff杰出教学奖。他的研究兴趣包括面向对象技术、多媒体和软件工程。

出版者的话 译者序 前言 第一部分　基础篇 第1章　全景图 2 1.1　计算系统 2 1.1.1　计算系统的分层 3 1.1.2　抽象 4 1.2　计算的历史 6 1.2.1　计算硬件简史 6 1.2.2　计算软件简史 13 1.2.3　预言 17 1.3　计算工具与计算学科 17 小结 19 道德问题：数字鸿沟 19 关键术语 20 练习 20 思考题 21 第二部分　信息层 第2章　二进制数值与记数系统 24 2.1　数字与计算 24 2.2　位置记数法 25 2.2.1　二进制、八进制和十六进制 26 2.2.2　其他记数系统中的运算 29 2.2.3　以2的幂为基数的记数系统 30 2.2.4　将十进制数转换成其他数制的数 31 2.2.5　二进制数值与计算机 32 小结 33 道德问题：FISA法庭 34 关键术语 34 练习 34 思考题 36 第3章　数据表示法 37 3.1　数据与计算机 37 3.1.1　模拟数据与数字数据 38 3.1.2　二进制表示法 40 3.2　数字数据表示法 41 3.2.1　负数表示法 41 3.2.2　实数表示法 44 3.3　文本表示法 46 3.3.1　ASCII字符集 47 3.3.2　Unicode字符集 48 3.3.3　文本压缩 48 3.4　音频数据表示法 52 3.4.1　音频格式 53 3.4.2　MP3音频格式 54 3.5　图像与图形表示法 54 3.5.1　颜色表示法 54 3.5.2　数字化图像与图形 55 3.5.3　图形的矢量表示法 57 3.6　视频表示法 57 小结 58 道德问题：Snowden事件的影响 58 关键术语 59 练习 59 思考题 61 第三部分　硬件层 第4章　门和电路 64 4.1　计算机和电学 64 4.2　门 66 4.2.1　非门 66 4.2.2　与门 67 4.2.3　或门 68 4.2.4　异或门 68 4.2.5　与非门和或非门 68 4.2.6　门处理回顾 69 4.2.7　具有更多输入的门 70 4.3　门的构造 70 4.4　电路 72 4.4.1　组合电路 72 4.4.2　加法器 75 4.4.3　多路复用器 76 4.5　存储器电路 77 4.6　集成电路 78 4.7　CPU芯片 78 小结 79 道德问题：道德规范 79 关键术语 80 练习 80 思考题 82 第5章　计算部件 83 5.1　独立的计算机部件 83 5.2　存储程序的概念 86 5.2.1　冯·诺伊曼体系结构 88 5.2.2　读取–执行周期 91 5.2.3　RAM和ROM 93 5.2.4　二级存储设备 93 5.2.5　触摸屏 97 5.3　嵌入式系统 98 5.4　并行体系结构 99 5.4.1　并行计算 99 5.4.2　并行硬件分类 100 小结 101 道德问题：隐私是否已经是过去时？ 101 关键术语 102 练习 102 思考题 103 第四部分　程序设计层 第6章　低级程序设计语言与伪代码 106 6.1　计算机操作 106 6.2　机器语言 107 6.2.1　Pep/9：一台虚拟机 107 6.2.2　Pep/9的输入/输出 112 6.3　一个程序实例 112 6.3.1　Pep/9模拟器 113 6.3.2　另一个机器语言实例 114 6.4　汇编语言 115 6.4.1　Pep/9汇编语言 115 6.4.2　数字数据、分支、标签 117 6.4.3　汇编语言中的循环 120 6.5　表达算法 121 6.5.1　伪代码的功能 121 6.5.2　执行伪代码算法 124 6.5.3　写伪代码算法 126 6.5.4　翻译伪代码算法 127 6.6　测试 129 小结 130 道德问题：软件盗版 131 关键术语 131 练习 131 思考题 133 第7章　问题求解与算法设计 134 7.1　如何解决问题 134 7.1.1　提出问题 135 7.1.2　寻找熟悉的情况 136 7.1.3　分治法 137 7.1.4　算法 137 7.1.5　计算机问题求解过程 137 7.1.6　方法总结 139 7.1.7　测试算法 139 7.2　有简单变量的算法 140 7.2.1　带有选择的算法 140 7.2.2　带有循环的算法 140 7.3　复杂变量 143 7.3.1　数组 144 7.3.2　记录 144 7.4　搜索算法 145 7.4.1　顺序搜索 145 7.4.2　有序数组中的顺序搜索 146 7.4.3　二分检索 147 7.5　排序 148 7.5.1　选择排序 148 7.5.2　冒泡排序 150 7.5.3　插入排序 151 7.6　递归算法 152 7.6.1　子程序语句 153 7.6.2　递归阶乘 153 7.6.3　递归二分检索 154 7.6.4　快速排序 154 7.7　几个重要思想 157 7.7.1　信息隐蔽 157 7.7.2　抽象 157 7.7.3　事物命名 158 7.7.4　测试 158 小结 158 道德问题：开源软件 159 关键术语 160 练习 160 思考题 162 第8章　抽象数据类型与子程序 163 8.1　抽象数据类型 163 8.2　栈 164 8.3　队列 164 8.4　列表 165 8.5　树 167 8.5.1　二叉树 167 8.5.2　二叉检索树 169 8.5.3　其他操作 173 8.6　图 173 8.6.1　创建图 174 8.6.2　图算法 175 8.7　子程序 179 8.7.1　参数传递 180 8.7.2　值参与引用参数 181 小结 183 道德问题：工作场所监视 183 关键术语 184 练习 184 思考题 187 第9章　面向对象设计与高级程序设计语言 188 9.1　面向对象方法 188 9.1.1　面向对象 189 9.1.2　设计方法 189 9.1.3　示例 191 9.2　翻译过程 194 9.2.1　编译器 194 9.2.2　解释器 195 9.3　程序设计语言范型 196 9.3.1　命令式范型 197 9.3.2　声明式范型 197 9.4　高级程序设计语言的功能性 199 9.4.1　布尔表达式 199 9.4.2　数据归类 200 9.4.3　输入/输出结构 203 9.4.4　控制结构 204 9.5　面向对象语言的功能性 208 9.5.1　封装 209 9.5.2　类 209 9.5.3　继承 210 9.5.4　多态 211 9.6　过程设计与面向对象设计的区别 211 小结 212 道德问题：恶作剧与诈骗 213 关键术语 214 练习 214 思考题 216 第五部分　操作系统层 第10章　操作系统 218 10.1　操作系统的角色 218 10.1.1　内存、进程与CPU管理 220 10.1.2　批处理 220 10.1.3　分时 221 10.1.4　其他OS要素 222 10.2　内存管理 223 10.2.1　单块内存管理 224 10.2.2　分区内存管理 225 10.2.3　页式内存管理 227 10.3　进程管理 228 10.3.1　进程状态 229 10.3.2　进程控制块 229 10.4　CPU调度 230 10.4.1　先到先服务 231 10.4.2　最短作业优先 231 10.4.3　轮询法 232 小结 233 道德问题：医疗隐私——健康保险携带与责任法案（HIPAA） 234 关键术语 234 练习 235 思考题 237 第11章　文件系统和目录 238 11.1　文件系统 238 11.1.1　文本文件和二进制文件 239 11.1.2　文件类型 239 11.1.3　文件操作 240 11.1.4　文件访问 241 11.1.5　文件保护 242 11.2　目录 243 11.2.1　目录树 244 11.2.2　路径名 246 11.3　磁盘调度 247 11.3.1　先到先服务磁盘调度法 248 11.3.2　最短寻道时间优先磁盘调度法 249 11.3.3　SCAN磁盘调度法 249 小结 251 道德问题：选择加入和选择退出 251 关键术语 252 练习 252 思考题 254 第六部分　应用层 第12章　信息系统 256 12.1　信息管理 256 12.2　电子制表软件 257 12.2.1　电子数据表公式 259 12.2.2　循环引用 262 12.2.3　电子数据表分析 263 12.3　数据库管理系统 264 12.3.1　关系模型 265 12.3.2　关系 267 12.3.3　结构化查询语言 268 12.3.4　数据库设计 270 12.4　电子商务 270 12.5　大数据 271 小结 272 道德问题：政治与网络 273 关键术语 274 练习 274 思考题 276 第13章　人工智能 277 13.1　思维机 277 13.1.1　图灵测试 278 13.1.2　AI问题的各个方面 279 13.2　知识表示 279 13.2.1　语义网 280 13.2.2　检索树 282 13.3　专家系统 284 13.4　神经网络 286 13.4.1　生物神经网络 286 13.4.2　人工神经网络 287 13.5　自然语言处理 288 13.5.1　语音合成 289 13.5.2　语音识别 290 13.5.3　自然语言理解 291 13.6　机器人学 292 13.6.1　感知–规划–执行范型 292 13.6.2　包孕体系结构 293 13.6.3　物理部件 294 小结 295 道德问题：首次公开发行 296 关键术语 297 练习 297 思考题 298 第14章　模拟、图形学、游戏和其他应用 299 14.1　什么是模拟 299 14.1.1　复杂系统 299 14.1.2　模型 300 14.1.3　构造模型 300 14.2　特殊模型 301 14.2.1　排队系统 301 14.2.2　气象模型 303 14.2.3　计算生物学 307 14.2.4　其他模型 307 14.2.5　必要的计算能力 307 14.3　计算机图形学 308 14.3.1　光的工作原理 309 14.3.2　物体形状 310 14.3.3　光模拟 310 14.3.4　复杂对象的建模 311 14.3.5　让物体动起来 314 14.4　游戏 315 14.4.1　游戏的历史 316 14.4.2　创建虚拟世界 316 14.4.3　游戏设计与开发 317 14.4.4　游戏编程 318 小结 319 道德问题：游戏成瘾 319 关键术语 320 练习 320 思考题 321 第七部分　通信层 第15章　网络 324 15.1　连网 324 15.1.1　网络的类型 325 15.1.2　Internet连接 327 15.1.3　包交换 330 15.2　开放式系统与协议 331 15.2.1　开放式系统 331 15.2.2　网络协议 331 15.2.3　TCP/IP 332 15.2.4　高层协议 333 15.2.5　MIME类型 334 15.2.6　防火墙 334 15.3　网络地址 335 15.3.1　域名系统 336 15.3.2　谁控制因特网 338 15.4　云计算 339 15.5　区块链 340 小结 341 道德问题：社交网络的影响 341 关键术语 342 练习 343 思考题 344 第16章　万维网 345 16.1　Web简介 345 16.1.1　搜索引擎 346 16.1.2　即时消息 347 16.1.3　博客 348 16.1.4　cookie 348 16.1.5　Web分析 349 16.2　HTML和CSS 350 16.2.1　基本的HTML元素 352 16.2.2　标记的属性 353 16.2.3　关于CSS的更多内容 353 16.2.4　更多HTML5的元素 355 16.3　交互式网页 356 16.3.1　Java小程序 356 16.3.2　Java服务器页 357 16.4　XML 358 16.5　社交网络演化 360 小结 361 道德问题：赌博与互联网 363 关键术语 363 练习 364 思考题 365 第17章　计算机安全 366 17.1　各级安全 366 17.2　阻止未授权访问 368 17.2.1　密码 369 17.2.2　验证码 370 17.2.3　指纹分析 371 17.3　恶意代码 372 17.3.1　杀毒软件 373 17.3.2　安全攻击 373 17.4　密码学 375 17.5　保护你的在线信息 377 17.5.1　共同的责任 379 17.5.2　安全与可移动设备 379 17.5.3　维基解密 379 小结 381 道德问题：博客和新闻 382 关键术语 383 练习 384 思考题 385 第八部分　总结 第18章　计算的限制 388 18.1　硬件 388 18.1.1　算术运算的限制 388 18.1.2　部件的限制 393 18.1.3　通信的限制 394 18.2　软件 394 18.2.1　软件的复杂度 395 18.2.2　当前提高软件质量的方法 395 18.2.3　臭名昭著的软件错误 399 18.3　问题 400 18.3.1　算法比较 400 18.3.2　图灵机 405 18.3.3　停机问题 408 18.3.4　算法分类 409 小结 410 道德问题：Therac-25灾难剖析 410 关键术语 411 练习 411 思考题 413 参考文献 414 索引 421