书籍封面
书籍目录
封面
数字版权声明
扉页
版权页
序
阅读前提
计算机科学基础课程相关建议
两学季或两学期的课程
一学期的CS2类课程
一学期的离散数学课程
本书特色
封面简介
致谢
代码、勘误和注释的在线访问
目 录
第1章 计算机科学：将抽象机械化
1.1 本书主要内容
1.1.1 数据模型
1.1.2 数据结构
1.1.3 算法
1.1.4 基本思路
1.2 本章主要内容
1.3 数据模型
1.3.1 编程语言数据模型
1.3.2 系统软件的数据模型
1.3.3 电路的数据模型
1.3.4 习题
1.4 C语言数据模型
1.4.1 C语言类型系统
1.4.2 函数
1.4.3 C语言数据模型中的操作
1.4.4 数据对象的创建和销毁
1.4.5 数据的访问和修改
1.4.6 数据的组合
1.4.7 习题
1.5 算法和程序设计
1.5.1 软件的创建
1.5.2 编程风格
1.6 本书中用到的一些C语言约定
1.7 小结
1.8 参考文献
第2章 迭代、归纳和递归
2.1 本章主要内容
2.2 迭代
2.2.1 排序
2.2.2 选择排序：一种迭代排序算法
2.2.3 习题
2.3 归纳证明
2.3.1 归纳证明为何有效
2.3.2 检错码
2.3.3 习题
2.4 完全归纳
2.4.1 使用多个依据情况进行归纳
2.4.2 验证完全归纳
2.4.3 算术表达式的规范形式
2.4.4 习题
2.5 证明程序的属性
2.5.1 循环不变式
2.5.2 while循环的循环不变式
2.5.3 习题
2.6 递归定义
2.6.1 表达式
2.6.2 平衡圆括号
2.6.3 习题
2.7 递归函数
习题
2.8 归并排序：递归的排序算法
2.8.1 合并
2.8.2 分割表
2.8.3 排序算法
2.8.4 完整的程序
2.8.5 习题
2.9 证明递归程序的属性
习题
2.10 小结
2.11 参考文献
第3章 程序的运行时间
3.1 本章主要内容
3.2 算法的选择
3.3 度量运行时间
3.3.1 基准测试
3.3.2 对程序的分析
3.3.3 运行时间
3.3.4 不同运行时间的比较
3.3.5 习题
3.4 大O运行时间和近似运行时间
3.4.1 大O的定义
3.4.2 证明大O关系
3.4.3 证明大O关系不成立
3.4.4 习题
3.5 简化大O表达式
3.5.1 大O表达式的传递律
3.5.2 描述程序的运行时间
3.5.3 紧凑性
3.5.4 简单性
3.5.5 求和规则
3.5.6 不相称函数
3.5.7 习题
3.6 分析程序的运行时间
3.6.1 简单语句的运行时间
3.6.2 简单for循环的运行时间
3.6.3 选择语句的运行时间
3.6.4 程序块的运行时间
3.6.5 复杂循环的运行时间
3.6.6 习题
3.7 边界运行时间的递归规则
3.7.1 程序结构的树表示
3.7.2 攀爬结构树以确定运行时间
3.7.3 循环运行时间更精确的上界
3.7.4 习题
3.8 含函数调用的程序的分析
习题
3.9 递归函数的分析
习题
3.10 归并排序的分析
3.10.1 merge函数的分析
3.10.2 split函数的分析
3.10.3 MergeSort函数
3.10.4 习题
3.11 为递推关系求解
3.11.1 通过反复代换为递推关系求解
3.11.2 通过猜测解为递推关系求解
3.11.3 习题
3.12 小结
3.13 参考文献
第4章 组合与概率
4.1 本章主要内容
4.2 为分配计数
4.2.1 为分配计数的规则
4.2.2 为位串计数
4.2.3 习题
4.3 为排列计数
4.3.1 排列公式
4.3.2 排序要花多久
4.3.3 习题
4.4 有序选择
4.4.1 无放回选择的一般规则
4.4.2 习题
4.5 无序选择
4.5.1 为组合计数
4.5.2 n选m的递归定义
4.5.3 计算的算法的运行时间
4.5.4 函数的图像
4.5.5 二项式系数
4.5.6 习题
4.6 相同项的次序
习题
4.7 将对象分装入箱
4.7.1 装箱问题的一般规则
4.7.2 分装有区别的对象
4.7.3 习题
4.8 计数规则的组合
4.8.1 将计数分解为一系列选择
4.8.2 用计数的差来计算计数
4.8.3 将计数表示为子情况的和
4.8.4 习题
4.9 概率论简介
4.9.1 概率空间
4.9.2 概率的计算
4.9.3 基本关系
4.9.4 习题
4.10 条件概率
4.10.1 独立实验
4.10.2 概率的分配律
4.10.3 独立实验的乘积法则
4.10.4 习题
4.11 概率推理
4.11.1 OR结合的两个事件的概率
4.11.2 AND结合的事件的概率
4.11.3 处理事件间关系的一些方法
4.11.4 习题
4.12 期望值的计算
习题
4.13 概率在程序设计中的应用
4.13.1 概率分析
4.13.2 使用概率的算法
4.13.3 习题
4.14 小结
4.15 参考文献
第5章 树
5.1 本章主要内容
5.2 基本术语
5.2.1 树的等价递归定义
5.2.2 路径、祖先和子孙
5.2.3 子树
5.2.4 叶子节点和内部节点
5.2.5 高度和深度
5.2.6 有序树
5.2.7 标号树
5.2.8 表达式树——一类重要的树
5.2.9 习题
5.3 树的数据结构
5.3.1 树的指针数组表示
5.3.2 树的最左子节点右兄弟节点表示
5.3.3 父指针
5.3.4 习题
5.4 对树的递归
习题
5.5 结构归纳法
5.5.1 结构归纳法为何有效
5.5.2 习题
5.6 二叉树
5.6.1 二叉树的术语
5.6.2 二叉树的数据结构
5.6.3 对二叉树的递归
5.6.4 习题
5.7 二叉查找树
5.7.1 用二叉查找树实现词典
5.7.2 二叉查找树中元素的查找
5.7.3 二叉查找树元素的插入
5.7.4 二叉查找树元素的删除
5.7.5 习题
5.8 二叉查找树操作的效率
5.8.1 最坏情况
5.8.2 最佳情况
5.8.3 一般情况
5.8.4 习题
5.9 优先级队列和偏序树
5.9.1 偏序树
5.9.2 平衡偏序树和堆
5.9.3 优先级队列操作在堆上的执行
5.9.4 优先级队列操作的运行时间
5.9.5 习题
5.10 堆排序：利用平衡偏序树排序
5.10.1 数组的堆化
5.10.2 Heapify的运行时间
5.10.3 完整的堆排序算法
5.10.4 堆排序的运行时间
5.10.5 习题
5.11 小结
5.12 参考文献
第6章 表数据模型
6.1 本章主要内容
6.2 基本术语
6.2.1 表的长度
6.2.2 表的部分
6.2.3 表中元素的位置
6.2.4 习题
6.3 对表的操作
6.3.1 插入、删除和查找
6.3.2 串接
6.3.3 表的其他操作
6.3.4 习题
6.4 链表数据结构
6.4.1 词典操作的链表实现
6.4.2 查找
6.4.3 删除
6.4.4 插入
6.4.5 带重复的插入、查找和删除
6.4.6 表示词典的已排序表
6.4.7 各种方法的比较
6.4.8 双向链表
6.4.9 习题
6.5 表基于数组的实现
6.5.1 线性查找
6.5.2 带哨兵的查找
6.5.3 利用二叉查找对已排序表进行查找
6.5.4 习题
6.6 栈
6.6.1 对栈的操作
6.6.2 栈的数组实现
6.6.3 栈的链表实现
6.6.4 习题
6.7 使用栈实现函数调用
习题
6.8 队列
6.8.1 对队列的操作
6.8.2 队列的链表实现
6.8.3 习题
6.9 最长公共子序列
6.9.1 对LCS计算的递归
6.9.2 用于LCS的动态规划算法
6.9.3 LCS的恢复
6.9.4 习题
6.10 字符串的表示
6.10.1 C语言中的字符串
6.10.2 定长数组表示
6.10.3 字符串的链表表示
6.10.4 字符串的海量存储
6.10.5 习题
6.11 小结
6.12 参考文献
第7章 集合数据模型
7.1 本章主要内容
7.2 基本定义
7.2.1 原子
7.2.2 通过抽象对集合的定义
7.2.3 集合的相等性
7.2.4 无限集
7.2.5 习题
7.3 集合的运算
7.3.1 并集、交集和差集
7.3.2 文氏图
7.3.3 并集、交集和差集的代数法则
7.3.4 利用文氏图证明相等性
7.3.5 利用变形证明相等性
7.3.6 子集关系
7.3.7 通过证明则包含关系对相等性加以证明
7.3.8 集合的幂集
7.3.9 幂集的大小
7.3.10 习题
7.4 集合的链表实现
7.4.1 并集、交集和差集
7.4.2 使用已排序表的并集、交集和差集
7.4.3 并集运算的运行时间
7.4.4 交集和差集
7.4.5 习题
7.5 集合的特征向量实现
7.5.1 集合的数组实现
7.5.2 习题
7.6 散列
7.6.1 散列表数据结构
7.6.2 词典操作的散列表实现
7.6.3 散列表操作的运行时间
7.6.4 习题
7.7 关系和函数
7.7.1 笛卡儿积
7.7.2 两个以上集合的笛卡儿积
7.7.3 二元关系
7.7.4 关系的中缀表示
7.7.5 表示二元关系的图
7.7.6 函数
7.7.7 一一对应
7.7.8 习题
7.8 将函数作为数据来实现
7.8.1 对函数的操作
7.8.2 函数的链表表示
7.8.3 函数的向量表示
7.8.4 函数的散列表表示
7.8.5 对用散列表表示的函数的操作
7.8.6 函数操作的效率
7.8.7 习题
7.9 二元关系的实现
7.9.1 对二元关系的操作
7.9.2 二元关系的链表实现
7.9.3 特征向量法
7.9.4 二元关系的散列表表示
7.9.5 二元关系操作的运行时间
7.9.6 习题
7.10 二元关系的一些特殊属性
7.10.1 传递性
7.10.2 自反性
7.10.3 对称性与反对称性
7.10.4 偏序和全序
7.10.5 等价关系
7.10.6 等价类
7.10.7 关系的闭包
7.10.8 习题
7.11 无限集
7.11.1 无限集的正式定义
7.11.2 可数集与不可数集
7.11.3 习题
7.12 小结
7.13 参考文献
第8章 关系数据模型
8.1 本章主要内容
8.2 关系
8.2.1 关系的表示
8.2.2 数据库
8.2.3 数据库的查询
8.2.4 表示关系的数据结构的设计
8.2.5 习题
8.3 键
8.3.1 键的确定
8.3.2 习题
8.4 关系的主要存储结构
8.4.1 插入、删除和查找操作
8.4.2 习题
8.5 辅助索引结构
8.5.1 非键字段上的辅助索引
8.5.2 辅助索引结构的更新
8.5.3 习题
8.6 关系间的导航
8.6.1 利用索引为导航提速
8.6.2 多关系上的导航
8.6.3 习题
8.7 关系代数
8.7.1 关系代数的操作数
8.7.2 关系代数的集合运算符
8.7.3 选择运算符
8.7.4 投影运算符
8.7.5 关系的联接
8.7.6 自然联接
8.7.7 关系代数表达式的表达式树
8.7.8 习题
8.8 关系代数运算的实现
8.8.1 并交差的实现
8.8.2 投影的实现
8.8.3 选择的实现
8.8.4 联接的实现
8.8.5 联接方法的比较
8.8.6 习题
8.9 关系的代数法则
8.9.1 涉及并交差的法则
8.9.2 涉及联接的法则
8.9.3 涉及选择的法则
8.9.4 涉及投影的法则
8.9.5 习题
8.10 小结
8.11 参考文献
第9章 图数据模型
9.1 本章主要内容
9.2 基本概念
9.2.1 前导和后继
9.2.2 标号
9.2.3 路径
9.2.4 有环图和无环图
9.2.5 无环路径
9.2.6 无向图
9.2.7 无向图中的路径和环路
9.2.8 习题
9.3 图的实现
9.3.1 邻接表
9.3.2 邻接矩阵
9.3.3 对图的操作
9.3.4 无向图的实现
9.3.5 标号图的表示
9.3.6 习题
9.4 无向图的连通分支
9.4.1 作为等价类的连通分支
9.4.2 计算连通分支的算法
9.4.3 用于形成分支的数据结构
9.4.4 连通分支算法的运行时间
9.4.5 习题
9.5 最小生成树
9.5.1 找到最小生成树
9.5.2 克鲁斯卡尔算法起效的原因
9.5.3 克鲁斯卡尔算法的运行时间
9.5.4 习题
9.6 深度优先搜索
9.6.1 构建深度优先搜索树
9.6.2 深度优先搜索树弧的分类
9.6.3 深度优先搜索森林
9.6.4 深度优先搜索算法的运行时间
9.6.5 有向图的后序遍历
9.6.6 后序编号的特殊属性
9.6.7 习题
9.7 深度优先搜索的一些用途
9.7.1 有向图中环路的寻找
9.7.2 无环测试的运行时间
9.7.3 拓扑排序
9.7.4 可达性问题
9.7.5 可达性测试的运行时间
9.7.6 通过深度优先搜索寻找连通分支
9.7.7 习题
9.8 用于寻找最短路径的迪杰斯特拉算法
9.8.1 迪杰斯特拉算法起效的原因
9.8.2 迪杰斯特拉算法的数据结构
9.8.3 迪杰斯特拉算法的辅助函数
9.8.4 初始化
9.8.5 迪杰斯特拉算法的实现
9.8.6 迪杰斯特拉算法的运行时间
9.8.7 习题
9.9 最短路径的弗洛伊德算法
9.9.1 弗洛伊德算法为何奏效
9.9.2 习题
9.10 图论简介
9.10.1 完全图
9.10.2 平面图
9.10.3 平面性的应用
9.10.4 图着色
9.10.5 图着色的应用
9.10.6 团
9.10.7 习题
9.11 小结
9.12 参考文献
第10章 模式、自动机和正则表达式
10.1 本章主要内容
10.2 状态机和自动机
10.2.1 状态机的图表示
10.2.2 习题
10.3 确定自动机和非确定自动机
10.3.1 确定自动机
10.3.2 非确定自动机
10.3.3 非确定自动机的接受
10.3.4 习题
10.4 从不确定到确定
10.4.1 自动机的等价性
10.4.2 子集构造
10.4.3 子集构造起效的原因
10.4.4 习题
10.5 正则表达式
10.5.1 正则表达式的操作数
10.5.2 正则表达式的值
10.5.3 正则表达式的运算
10.5.4 正则表达式运算符的优先级
10.5.5 正则表达式的其他一些示例
10.5.6 习题
10.6 UNIX对正则表达式的扩展
10.6.1 字符类
10.6.2 行的开头和结尾
10.6.3 通配符
10.6.4 额外的运算符
10.6.5 习题
10.7 正则表达式的代数法则
10.7.1 取并和串接与加法和乘法的类比
10.7.2 取并和串接与加法和乘法的区别
10.7.3 涉及闭包的等价
10.7.4 习题
10.8 从正则表达式到自动机
10.8.1 具有转换的自动机
10.8.2 从正则表达式到具有转换的自动机
10.8.3 消除转换
10.8.4 习题
10.9 从自动机到正则表达式
10.9.1 状态消除的构造
10.9.2 自动机的完全简化
10.9.3 习题
10.10 小结
10.11 参考文献
第11章 模式的递归描述
11.1 本章主要内容
11.2 上下文无关文法
11.2.1 与文法相关的术语
11.2.2 习题
11.3 源自文法的语言
习题
11.4 分析树
11.4.1 分析树的构建
11.4.2 分析树为何“行得通”
11.4.3 习题
11.5 二义性和文法设计
11.5.1 表达式中的二义性
11.5.2 表示表达式的无二义文法
11.5.3 习题
11.6 分析树的构造
11.6.1 递归下降分析
11.6.2 用于平衡括号串的递归下降分析器
11.6.3 递归下降分析器的构建
11.6.4 习题
11.7 表驱动分析算法
11.7.1 分析表
11.7.2 表驱动分析器的工作原理
11.7.3 分析树的构建
11.7.4 让文法变得可分析
11.7.5 习题
11.8 文法与正则表达式
11.8.1 用文法模拟正则表达式
11.8.2 有文法但没有正则表达式的语言
11.8.3 证明E不能用任何正则表达式定义
11.8.4 习题
11.9 小结
11.10 参考文献
第12章 命题逻辑
12.1 本章主要内容
12.2 什么是命题逻辑
命题和真值
12.3 逻辑表达式
12.3.1 逻辑运算符的优先级
12.3.2 逻辑表达式的求值
12.3.3 布尔函数
12.3.4 习题
12.4 真值表
12.4.1 真值表的大小
12.4.2 布尔函数数量的计算
12.4.3 更多逻辑运算符
12.4.4 具有多个参数的运算符
12.4.5 逻辑运算符的结合性与优先级
12.4.6 利用真值表为逻辑表达式求值
12.4.7 习题
12.5 从布尔函数到逻辑表达式
12.5.1 简化符号
12.5.2 从真值表构建逻辑表达式
12.5.3 习题
12.6 利用卡诺图设计逻辑表达式
12.6.1 卡诺图
12.6.2 双变量卡诺图
12.6.3 蕴涵项
12.6.4 质蕴涵项
12.6.5 三变量卡诺图
12.6.6 四变量卡诺图
12.6.7 习题
12.7 重言式
12.7.1 替换原则
12.7.2 重言式问题
12.7.3 重言式测试的运行时间
12.7.4 习题
12.8 逻辑表达式的一些代数法则
12.8.1 等价的法则
12.8.2 类似算术的法则
12.8.3 AND和OR与加和乘的区别
12.8.4 德摩根律
12.8.5 对偶性原理
12.8.6 涉及蕴涵的法则
12.8.7 习题
12.9 重言式及证明方法
12.9.1 排中律
12.9.2 换质位法
12.9.3 反证法
12.9.4 等价于真
12.9.5 习题
12.10 演绎
12.10.1 演绎证明的构成
12.10.2 演绎证明“起作用”的原因
12.10.3 习题
12.11 分解证明
12.11.1 把逻辑表达式变成合取范式
12.11.2 利用分解的推理
12.11.3 利用反证法的分解证明
12.11.4 习题
12.12 小结
12.13 参考文献
第13章 利用逻辑设计计算机元件
13.1 本章主要内容
13.2 门
13.3 电路
13.3.1 组合电路和时序电路
13.3.2 习题
13.4 逻辑表达式和电路
13.4.1 从表达式到电路
13.4.2 从电路到逻辑表达式
13.4.3 习题
13.5 电路的一些物理限制
13.5.1 电路速度
13.5.2 大小限制
13.5.3 扇入和扇出限制
13.5.4 习题
13.6 分治加法电路
13.6.1 递归加法电路
13.6.2 分治加法器的延迟
13.6.3 分治加法器使用的门的数量
13.6.4 习题
13.7 多路复用器的设计
13.7.1 分治多路复用器
13.7.2 分治MUX的延迟
13.7.3 门的数量
13.7.4 习题
13.8 存储单元
习题
13.9 小结
13.10 参考文献
第14章 谓词逻辑
14.1 本章主要内容
14.2 谓词
14.2.1 原子公式
14.2.2 常量和变量的区分
14.2.3 习题
14.3 逻辑表达式
14.3.1 文字
14.3.2 逻辑表达式
14.3.3 其他术语
14.3.4 习题
14.4 量词
14.4.1 逻辑表达式的递归定义
14.4.2 运算符的优先级
14.4.3 约束变量和自由变量
14.4.4 习题
14.5 解释
14.5.1 表达式的含义
14.5.2 习题
14.6 重言式
14.6.1 替换原则
14.6.2 表达式的等价
14.6.3 习题
14.7 涉及量词的重言式
14.7.1 变量的重命名
14.7.2 自由变量的全称量词化
14.7.3 闭表达式
14.7.4 把量词移过NOT
14.7.5 把量词移过AND和OR
14.7.6 前束式
14.7.7 量词的重新排列
14.7.8 习题
14.8 谓词逻辑中的证明
14.8.1 隐式全称量词
14.8.2 作为推理规则的变量替换
14.8.3 习题
14.9 根据规则和事实的证明
14.9.1 简化的推理规则
14.9.2 习题
14.10 真理和可证性
14.10.1 模型
14.10.2 蕴涵
14.10.3 可证性与蕴涵的比较
14.10.4 哥德尔不完备性定理
14.10.5 计算机能完成的工作的限制
14.10.6 习题
14.11 小结
14.12 参考文献
看完了
没有回复内容