大学计算机:计算思维导论

第1章 引论 001 1.1 什么是计算 002 1.2 计算机科学与计算科学 002 1.3 来自计算机发展史的启示 003 1.3.1 来自计算工具发展的启示 003 1.3.2 来自元器件发展的启示 005 1.3.3 来自计算机硬件发展的启示 007 1.3.4 来自计算机软件发展的启示 009 1.3.5 一些重要思想/重要事件及其带来的影响 011 1.4 计算机应用 013 1.5 计算机发展趋势 015 1.5.1 高性能计算：无所不能的计算 015 1.5.2 普适计算：无所不在的计算 016 1.5.3 服务计算与云计算：万事皆服务的计算 017 1.5.4 智能计算 018 1.5.5 生物计算 019 1.5.6 未来互联网与智慧地球 020 思考题 022 参考文献 023 第2章 计算系统的基本思维 025 2.1 理解0和1的思维 026 2.1.1 语义符号化的典型案例：0/1与《易经》 026 2.1.2 思维方式与逻辑运算：0/1与逻辑 027 2.1.3 二进制与算术运算：0/1与数值信息 028 2.1.4 编码与符号运算：0/1与非数值信息 031 2.1.5 0和1与电子元器件 034 2.1.6 0和1思维小结 038 2.2 图灵机与冯·诺依曼计算机 039 2.2.1 图灵机：关于通用机器及指令、程序及其自动执行 039 2.2.2 冯·诺依曼计算机 041 2.2.3 存储器：可按地址自动存取内容的部件 042 目 录 XVIII 2.2.4 机器指令与机器级程序与算法 045 2.2.5 机器级程序的存储与执行 047 2.2.6 关于冯·诺依曼计算机的贯通性思维小结 050 2.3 现代计算机 051 2.3.1 现代计算机的构成 051 2.3.2 存储体系：不同性能资源的组合优化思维 052 2.3.3 为什么要有操作系统——硬件功能扩展的基本思维 055 2.3.4 化整为零的基本思维——磁盘与文件管理 057 2.3.5 任务-作业与内存管理： 分工合作与协同求解复杂系统问题的基本思维 059 2.3.6 分时-并行控制思维：任务-作业管理与处理机管理 062 2.3.7 现代计算机的工作过程 064 2.3.8 现代计算机的发展 065 2.3.9 关于现代计算机的贯通性思维小结 067 2.4 不同抽象层级的计算机（软件） 067 2.4.1 人-机交互层面的计算机——计算机语言与编译器 068 2.4.2 机-机交互层级的计算机： 协议与编码器/解码器/转换器/处理器 075 2.4.3 分层抽象进行复杂问题化简的示例： 操作系统对设备的分层控制 078 2.4.4 关于不同抽象层级计算机的思维小结 085 思考题 085 参考文献 087 第3章 问题求解框架 089 3.1 传统程序的基本构成要素 090 3.1.1 常量、变量、表达式 090 3.1.2 语句与程序控制 092 3.1.3 函数与函数调用 097 3.1.4 常量/变量、数据存储与数据结构 098 3.1.5 程序构造及其表达方法 102 3.2 算法类问题求解框架 105 3.2.1 算法的基本概念 105 3.2.2 数学建模：建立问题的数学模型 108 3.2.3 算法思想：算法策略选择 109 3.2.4 算法设计：算法思想的精确表达 110 3.2.5 算法的模拟与分析 113 3.2.6 算法的复杂性 114 XIX 3.2.7 算法类问题求解框架 115 3.3 现代程序的基本构成要素 116 3.3.1 对象与类的概念——通俗示例 116 3.3.2 类与对象的概念——面向对象的程序 119 3.3.3 面向对象程序构造的一个例子——可视化编程的思维模式 121 3.3.4 现代程序构造及其表达方法 123 3.4 系统类问题求解框架 126 3.4.1 什么是系统 126 3.4.2 建立问题域/业务模型 130 3.4.3 建立软件域模型 135 3.4.4 软件模块的构造与实现 141 3.4.5 软件系统的构造与实现 145 3.4.6 软件系统的测试、部署与运行 147 3.4.7 软件体系结构与软件模式问题 150 3.4.8 系统的可靠性和安全性问题 156 3.4.9 小结 158 思考题 159 参考文献 161 第4章 算法与复杂性 163 4.1 排序问题及其算法 164 4.1.1 排序问题 164 4.1.2 基本排序算法 167 4.1.3 PageRank排序：排序问题的不同思考方法 174 4.2 递归及递归算法 180 4.2.1 递归：用有限的语句定义对象的无限集合 180 4.2.2 递归算法：自身调用自身，高阶调用低阶 187 4.3 遗传算法：计算复杂性与仿生学算法示例 194 4.3.1 可求解与难求解问题 194 4.3.2 遗传算法：仿生学算法的简单示例 196 4.3.3 遗传算法暨问题求解算法的进一步探讨 202 思考题 210 参考文献 211 第5章 数据抽象、设计与挖掘 213 5.1 数据与大数据 214 5.2 数据管理和数据库：数据聚集的核心 216 5.2.1 数据聚集成“库”——数据库及数据库管理 216 XX 5.2.2 数据库的基本结构形式——数据表 217 5.2.3 数据表的操作——关系操作 220 5.2.4 用数学定义数据表及其操作——关系模型 223 5.2.5 数据库语言——用计算机语言表达数据表及其操作 226 5.2.6 DBMS——数据库语言的执行或者数据表操作的自动实现 231 5.3 数据分析的核心——联机数据分析和数据挖掘 232 5.3.1 例子——超市数据库 232 5.3.2 超市数据分析方法——二维交叉表 234 5.3.3 数据仓库联机数据分析（OLAP）： 由二维数据分析到多维数据分析 235 5.3.4 数据也是生产力——数据挖掘 240 5.4 抽象、理论和设计 248 5.4.1 抽象：理解→区分→命名→表达 249 5.4.2 理论：定义→性质（公理和定理）→证明 254 5.4.3 设计：形式→构造→自动化 257 5.4.4 抽象—理论—设计之间的关系 259 思考题 260 参考文献 261 第6章 计算机网络、信息网络与网络化社会 263 6.1 网络与社会 264 6.2 计算机网络 264 6.2.1 网络通信的基本原理 264 6.2.2 计算机网络连接：不同类别的机器网络 269 6.3 因特网与Web——信息网络 279 6.3.1 由计算机网络走向文档/信息网络Web 279 6.3.2 超文本/超媒体的表达与解析 280 6.3.3 超文本/超媒体的组织与管理 284 6.3.4 无限资源库的发掘和利用：搜索引擎 286 6.3.5 互动网络与群体网络： 互联网的创新更重要的是思维的创新 287 6.4 网络化社会与网络计算：用科学方法研究网络问题 290 6.4.1 形形色色的网络 290 6.4.2 网络问题抽象与基本网络计算问题 291 6.4.3 网络计算示例：社会网络的一个问题研究 297 思考题 302 参考文献 304