计算机科学导论:基于计算思维的思想与方法

李云峰，湖南广播电视大学信息技术系教授，中南大学自动控制系毕业，之后一直从事教育工作，教学经验丰富。主要著作方向为计算机导论（理论篇）、计算机导论（实践篇），出版多部相关教材。

绪论 课程导学 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

本书参照靠前电子电气工程协会计算机学会和美国计算机学会（IEEE-CS＆ACM）计算学科教程（CC2005）和中国计算机教程（CCC2002）知识体系结构，将计算学科形态与计算思维本质紧密结合，按照基本概念、基本方法、基本理论、基本技术这一基础特性构建课程知识体系。本书共12章，以计算学科体系与计算机前沿技术为课程视野，对计算机的形成与发展、计算机学科的形态特征、计算机学科的根本问题与典型问题、计算机学科方法论、计算思维在计算机学科中的作用体现、计算机新技术的应用等进行了全面阐述，为计算机科学与技术专业学生学好本专业起到“导航”作用。本书结构新颖、层次分明、由浅入深、循序渐进，注重知识的系统性、科学性和实用性，并站在学科的高度阐述计算机科学技术基础知识。同时，注意与后继相关课程的分工与衔接，并按照教与学的规律，精心设计每一章的内容。本书可作为高等院校计算机类、电子信息类和电气信息类“计算机（科学）导论”课程教材，也可作为相关专业教学人员和从事计算机应用的工程技术人员的参考书。