离散数学：面向计算机科学专业

本书由计算机和数学领域的三位教授联合撰写，是为计算机专业量身定制的离散数学教材。针对初入学的本科生不理解为何要学习高深的数学，授课教师苦于向毫无编程经验的学生讲授繁杂的算法程序的问题，本书打破了传统的课程顺序和教学方法，明确“为何学”和“有何用”，不仅清晰呈现了计算机专业学生必需的数学知识，而且通过实践和应用启发学生对后续课程的学习兴趣。主要内容涵盖计数、密码学与数论、逻辑与证明、归纳法、递归、概率以及图论等。本书推导严谨、代码清晰、练习丰富，可作为高等学校计算机相关专业的离散数学课程的教材，也可供计算机技术人员学习与参考。

译者序 <br/>前言 <br/>第1章 计数 1 <br/>1.1 基本计数 1 <br/>1.1.1 加法原理 1 <br/>1.1.2 抽象化 2 <br/>1.1.3 连续整数求和 3 <br/>1.1.4 乘法原理 3 <br/>1.1.5 二元子集 5 <br/>重要概念、公式和定理 5 <br/>习题 6 <br/>1.2 序列、排列和子集 7 <br/>1.2.1 使用加法和乘法原理 7 <br/>1.2.2 序列和函数 9 <br/>1.2.3 双射原理 10 <br/>1.2.4 集合的 k 元素排列 11 <br/>1.2.5 集合子集的计数 12 <br/>重要概念、公式和定理 14 <br/>习题 15 <br/>1.3 二项式系数 16 <br/>1.3.1 帕斯卡三角形 16 <br/>1.3.2 使用加法原理的证明 18 <br/>1.3.3 二项式定理 19 <br/>1.3.4 标记与三项式系数 21 <br/>重要概念、公式和定理 22 <br/>习题 22 <br/>1.4 关系 24 <br/>1.4.1 什么是关系 24 <br/>1.4.2 函数关系 24 <br/>1.4.3 关系的性质 25 <br/>1.4.4 等价关系 27 <br/>1.4.5 偏序和全序 29 <br/>重要概念、公式和定理 30 <br/>习题 31 <br/>1.5 在计数中运用等价关系 32 <br/>1.5.1 对称原理 32 <br/>1.5.2 等价关系 34 <br/>1.5.3 商原理 34 <br/>1.5.4 等价类计数 35 <br/>1.5.5 多重集 36 <br/>1.5.6 书柜安排问题 37 <br/>1.5.7 n 元集合的 k 元多重集的数目 38 <br/>1.5.8 使用商原理解释商 39 <br/>重要概念、公式和定理 39 <br/>习题 40 <br/>第2章 密码编码学与数论 43 <br/>2.1 密码编码学和模算法 43 <br/>2.1.1 密码编码学导论 43 <br/>2.1.2 私钥密码 43 <br/>2.1.3 公钥密码体制 46 <br/>2.1.4 模 n 算术 47 <br/>2.1.5 使用模 n 加法的密码编码 49 <br/>2.1.6 使用模 n 乘法的密码编码 50 <br/>重要概念、公式和定理 51 <br/>习题 52 <br/>2.2 逆元和最大公因子 54 <br/>2.2.1 方程的解和模 n 的逆元 54 <br/>2.2.2 模 n 的逆元 55 <br/>2.2.3 将模方程转化为普通方程 57 <br/>2.2.4 最大公因子 58 <br/>2.2.5 欧几里得除法定理 59 <br/>2.2.6 欧几里得最大公因子算法 61 <br/>2.2.7 广义最大公因子算法 62 <br/>2.2.8 计算逆元 64 <br/>重要概念、公式和定理 65 <br/>习题 66 <br/>2.3 RSA 密码体制 67 <br/>2.3.1 模 n 的指数运算 67 <br/>2.3.2 指数运算的规则 68 <br/>2.3.3 费马小定理 70 <br/>2.3.4 RSA 密码体制 71 <br/>2.3.5 中国剩余定理 74 <br/>重要概念、公式和定理 75 <br/>习题 76 <br/>2.4 RSA 加密体制的细节 78 <br/>2.4.1 模 n 指数运算的实用性 78 <br/>2.4.2 使用 RSA 算法会花费多长时间 79 <br/>2.4.3 因式分解有多难 80 <br/>2.4.4 找大素数 80 <br/>重要概念、公式和定理 83 <br/>习题 83 <br/>第3章 关于逻辑与证明的思考 85 <br/>3.1 等价和蕴含 85 <br/>3.1.1 语句的等价 85 <br/>3.1.2 真值表 87 <br/>3.1.3 德摩根律 89 <br/>3.1.4 蕴含 90 <br/>3.1.5 当且仅当 91 <br/>重要概念、公式和定理 93 <br/>习题 94 <br/>3.2 变元和量词 95 <br/>3.2.1 变元和论域 95 <br/>3.2.2 量词 96 <br/>3.2.3 量词化的标准记号 98 <br/>3.2.4 关于变元的语句 99 <br/>3.2.5 重写语句以包含更大的论域 99 <br/>3.2.6 证明量词语句的真假 100 <br/>3.2.7 量词语句的否定 101 <br/>3.2.8 隐式量词化 102 <br/>3.2.9 量词语句的证明 103 <br/>重要概念、公式和定理 104 <br/>习题 105 <br/>3.3 推理 106 <br/>3.3.1 直接推理（演绎推理）和证明 106 <br/>3.3.2 直接证明的推理规则 108 <br/>3.3.3 推理的逆否（对换）规则 109 <br/>3.3.4 反证法 110 <br/>重要概念、公式和定理 112 <br/>习题 113 <br/>第4章 归纳、递归和递推式 115 <br/>4.1 数学归纳法 115 <br/>4.1.1 最小反例 115 <br/>4.1.2 数学归纳法原理 118 <br/>4.1.3 强归纳法 120 <br/>4.1.4 归纳法的一般形式 121 <br/>4.1.5 从递归视角看归纳法 123 <br/>4.1.6 结构归纳法 126 <br/>重要概念、公式和定理 128 <br/>习题 128 <br/>4.2 递归、递推式和归纳法 130 <br/>4.2.1 递归 130 <br/>4.2.2 一阶线性递推式举例 132 <br/>4.2.3 迭代递推式 133 <br/>4.2.4 等比级数 134 <br/>4.2.5 一阶线性递推式 137 <br/>重要概念、公式和定理 140 <br/>习题 141 <br/>4.3 递推式解的增长率 142 <br/>4.3.1 分治算法 142 <br/>4.3.2 递归树 144 <br/>4.3.3 三种不同的行为 149 <br/>重要概念、公式和定理 151 <br/>习题 152 <br/>4.4 主定理 153 <br/>4.4.1 主定理基础 153 <br/>4.4.2 求解更一般的递推式 156 <br/>4.4.3 扩展主定理 156 <br/>重要概念、公式和定理 158 <br/>习题 158 <br/>4.5 更一般的递推式 159 <br/>4.5.1 递推不等式 159 <br/>4.5.2 不等式主定理 160 <br/>4.5.3 归纳法的一个窍门 161 <br/>4.5.4 更多归纳证明的窍门 163 <br/>4.5.5 处理 nc 以外的函数 165 <br/>重要概念、公式和定理 166 <br/>习题 167 <br/>4.6 递推式和选择 168 <br/>4.6.1 选择的理念 168 <br/>4.6.2 一种递归选择算法 169 <br/>4.6.3 中位数未知情况下的选择 170 <br/>4.6.4 一种查找中间一半中元素的算法 171 <br/>4.6.5 对修改后的选择算法的分析 174 <br/>4.6.6 不均匀划分 175 <br/>重要概念、公式和定理 177 <br/>习题 178 <br/>第5章 概率 179 <br/>5.1 概率导论 179 <br/>5.1.1 为什么学习概率 179 <br/>5.1.2 概率计算举例 181 <br/>5.1.3 互补概率 182 <br/>5.1.4 概率与散列法 182 <br/>5.1.5 均匀概率分布 184 <br/>重要概念、公式和定理 186 <br/>习题 187 <br/>5.2 并集和交集 188 <br/>5.2.1 并集事件的概率 188 <br/>5.2.2 概率的容斥原理 190 <br/>5.2.3 计数的容斥原理 195 <br/>重要概念、公式和定理 196 <br/>习题 197 <br/>5.3 条件概率和独立性 198 <br/>5.3.1 条件概率 198 <br/>5.3.2 贝叶斯定理 201 <br/>5.3.3 独立性 201 <br/>5.3.4 独立试验过程 203 <br/>5.3.5 树形图 204 <br/>5.3.6 素数测试 207 <br/>重要概念、公式和定理 208 <br/>习题 209 <br/>5.4 随机变量 210 <br/>5.4.1 什么是随机变量 210 <br/>5.4.2 二项式概率 211 <br/>5.4.3 体验生成函数 212 <br/>5.4.4 期望值 213 <br/>5.4.5 期望值的求和与数值乘法 216 <br/>5.4.6 指示器随机变量 218 <br/>5.4.7 第一次成功的尝试次数 219 <br/>重要概念、公式和定理 220 <br/>习题 222 <br/>5.5 散列中的概率计算 223 <br/>5.5.1 每个位置上元素的期望个数 224 <br/>5.5.2 空位置的期望个数 224 <br/>5.5.3 冲突的期望个数 225 <br/>5.5.4 元素在散列表的一个位置上的最大期望个数 227 <br/>重要概念、公式和定理 231 <br/>习题 231 <br/>5.6 条件期望、递推和算法 234 <br/>5.6.1 当运行时间不仅依赖输入的大小时 234 <br/>5.6.2 条件期望值 236 <br/>5.6.3 随机算法 237 <br/>5.6.4 重温选择算法 239 <br/>5.6.5 快速排序 240 <br/>5.6.6 随机选择的更详细分析 243 <br/>重要概念、公式和定理 244 <br/>习题 245 <br/>5.7 概率分布和方差 247 <br/>5.7.1 随机变量的分布 247 <br/>5.7.2 方差 250 <br/>重要概念、公式和定理 255 <br/>习题 256 <br/>第6章 图论 259 <br/>6.1 图 259 <br/>6.1.1 顶点的度 261 <br/>6.1.2 连通性 263 <br/>6.1.3 环 264 <br/>6.1.4 树 265 <br/>6.1.5 树的其他性质 265 <br/>重要概念、公式和定理 267 <br/>习题 269 <br/>6.2 生成树和根树 270 <br/>6.2.1 生成树 270 <br/>6.2.2 广度优先搜索 272 <br/>6.2.3 根树 275 <br/>重要概念、公式和定理 278 <br/>习题 279 <br/>6.3 欧拉图和哈密顿图 281 <br/>6.3.1 欧拉环游和迹 281 <br/>6.3.2 寻找欧拉环游 284 <br/>6.3.3 哈密顿路径和回路 285 <br/>6.3.4 NP 完全问题 289 <br/>6.3.5 证明问题是 NP 完全的 291 <br/>重要概念、公式和定理 293 <br/>习题 294 <br/>6.4 匹配定理 296 <br/>6.4.1 匹配的概念 296 <br/>6.4.2 使得匹配更大 299 <br/>6.4.3 二部图的匹配 301 <br/>6.4.4 搜索二部图的增广路径 302 <br/>6.4.5 增广覆盖算法 304 <br/>6.4.6 高效算法 308 <br/>重要概念、公式和定理 309 <br/>习题 310 <br/>6.5 着色与平面性 311 <br/>6.5.1 着色的概念 311 <br/>6.5.2 区间图 313 <br/>6.5.3 平面性 315 <br/>6.5.4 平面画法的面 316 <br/>6.5.5 五色定理 319 <br/>重要概念、公式和定理 322 <br/>习题 322 <br/>附录 A 更一般的主定理推导 324 <br/>附录 B 习题答案和提示 332 <br/>参考文献 347 <br/>索引 349