计算机离散数学基础

本书主要讲述计算机科学专业的学生需要掌握的离散数学基础知识和核心理论。书中以读者容易接受的形式，围绕提高编程能力的目标，鼓励学生展开思考，从而有效地解决问题。本书选材适当，结构清晰，叙述简明，推理严谨，可作为高等院校计算机科学及相关专业学生的教材。

出版者的话
译者序
前言
第1章算法、数和机器
1.1什么是算法
1.2整数算法和复杂度
1.2.1素数测试
1.2.2实数
1.2.3改进素数测试算法
1.2.4素数分解
1.2.5对数
1.2.6优选公约数
1.3数的机器表示
1.3.1近似误差
1.3.2二进制、八进制和十六进制
1.4数值求解
1.4.1牛顿的平方根求解方法
1.4.2二分法
习题
第2章集合、序列和计数
2.1朴素集合论
2.1.1可恶的图书管理员
2.1.2集合运算和基数
2.1.3鸽巢原理
2.2序列
2.2.1子集的特征序列
2.3计数
2.3.1n元集合上的k元序列数
2.3.2n元集合的子集数
2.3.3n元集合上的k元排列数
2.3.4n的阶乘
2.3.5n元集合上的k元子集数
2.3.6Pascal三角形
2.3.7非公式的计数策略
2.4无限序列和复杂度函数
2.4.1汉诺塔
2.4.2差的复杂度函数
习题
第3章布尔表达式、逻辑和证明
3.1贪心算法和饼干选择问题
3.1.1贪心算法
3.2布尔表达式和真值表
3.2.1否算子
3.2.2合取算子
3.2.3析取算子
3.2.4条件算子
3.2.5双向条件算子
3.3谓词和量词
3.4有效推理
3.5证明实例
3.5.1直接证明
3.5.2间接证明
3.5.3Cantor的对角线方法
3.6数学归纳法
3.6.1强归纳法
3.7第1章的待证明结论
3.7.1RPM的正确性证明
3.7.2切蛋糕难题的正确性证明
3.7.3舍九法的正确性证明
3.7.4GCD欧几里得算法的正确性证明
3.8第2章的待证明结论
习题
第4章查找和排序
4.1查找
4.1.1查找任意列表
4.1.2查找有序列表
4.2分支图
4.2.1二分查找的第二个版本
4.3排序
4.3.1选择排序
4.3.2交换排序
4.4至少有n!个叶子的二叉树
4.5划分排序
4.6排序算法比较
4.6.1时间和运算的计数
习题
第5章图和树
5.1引言
5.1.1度
5.1.2欧拉图
5.1.3哈密顿图
5.2路径、回路和多边形
5.2.1路径确定的子图
5.3树
5.3.1遍历
5.4边带权图
5.4.1最短路径
5.5有向图
5.5.1有向路径
5.5.2距离函数
5.5.3Dijkstra算法
5.5.4Floyd-Warshall算法
习题
第6章关系：特别是(整数)序列上的关系
6.1关系和表示
6.1.1矩阵表示
6.1.2有向图表示
6.1.3关系的性质
6.2等价关系
6.2.1等价关系的矩阵和有向图表示
6.3序关系
6.3.1偏序的矩阵和有向图表示
6.3.2极小元和极大元
6.4有限序列上的关系
6.4.1支配
6.4.2字典序
6.5无限序列上的关系
6.5.1渐近支配和大O表示法
6.5.2渐近等价和大Θ表示
6.5.3渐近排序
6.5.4强渐近支配和小o表示
习题
第7章序列和级数
7.1递推方程实例
7.2求解一阶线性递推方程
7.3Fibonacci序列
7.3.1Fibonacci序列算法
7.3.2黄金比例
7.3.3Fibonacci序列和黄金比例
7.3.4Fibonacci序列的阶
7.3.5GCD的欧几里得算法的复杂度
7.4求解二阶线性递推方程
7.5无限级数
7.5.1芝诺悖论
7.5.2序列和级数收敛的形式化定义
习题
第8章生成序列和子集
8.1以字典序生成序列
8.2生成{1..n}的所有k元序列
8.2.1平均情况复杂度
8.3生成{1..n}的升序序列子集
8.4按字典序生成全排列
8.4.1按字典序生成{1..n}的所有k元排列
习题
第9章离散概率和平均情况复杂度
9.1概率模型
9.1.1采样空间
9.1.2概率函数
9.1.3特例：等概率输出
9.2条件概率
9.2.1组合事件
9.2.2条件概率
9.2.3独立事件
9.2.4互斥事件
9.3随机变量和期望值
9.3.1期望频率
9.3.2期望值
9.3.3概率分布
9.4标准分布及其期望值
9.4.1均匀分布
9.4.2二项分布
9.4.3几何分布
9.5条件期望值
9.5.1条件期望
9.6平均情况复杂度
9.6.1将期望应用于线性查找
9.6.2将期望应用于QuickSort
习题
第10章图灵机
10.1什么是算法
10.1.1Church-Turing理论
10.1.2通用图灵机：计算模型
10.1.3停机问题
习题
索引