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

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

译者序
前言
第1章 计数 1
1.1 基本计数 1
1.1.1 加法原理 1
1.1.2 抽象化 2
1.1.3 连续整数求和 3
1.1.4 乘法原理 3
1.1.5 二元子集 5
重要概念、公式和定理 5
习题 6
1.2 序列、排列和子集 7
1.2.1 使用加法和乘法原理 7
1.2.2 序列和函数 9
1.2.3 双射原理 10
1.2.4 集合的 k 元素排列 11
1.2.5 集合子集的计数 12
重要概念、公式和定理 14
习题 15
1.3 二项式系数 16
1.3.1 帕斯卡三角形 16
1.3.2 使用加法原理的证明 18
1.3.3 二项式定理 19
1.3.4 标记与三项式系数 21
重要概念、公式和定理 22
习题 22
1.4 关系 24
1.4.1 什么是关系 24
1.4.2 函数关系 24
1.4.3 关系的性质 25
1.4.4 等价关系 27
1.4.5 偏序和全序 29
重要概念、公式和定理 30
习题 31
1.5 在计数中运用等价关系 32
1.5.1 对称原理 32
1.5.2 等价关系 34
1.5.3 商原理 34
1.5.4 等价类计数 35
1.5.5 多重集 36
1.5.6 书柜安排问题 37
1.5.7 n 元集合的 k 元多重集的数目 38
1.5.8 使用商原理解释商 39
重要概念、公式和定理 39
习题 40
第2章 密码编码学与数论 43
2.1 密码编码学和模算法 43
2.1.1 密码编码学导论 43
2.1.2 私钥密码 43
2.1.3 公钥密码体制 46
2.1.4 模 n 算术 47
2.1.5 使用模 n 加法的密码编码 49
2.1.6 使用模 n 乘法的密码编码 50
重要概念、公式和定理 51
习题 52
2.2 逆元和优选公因子 54
2.2.1 方程的解和模 n 的逆元 54
2.2.2 模 n 的逆元 55
2.2.3 将模方程转化为普通方程 57
2.2.4 优选公因子 58
2.2.5 欧几里得除法定理 59
2.2.6 欧几里得优选公因子算法 61
2.2.7 广义优选公因子算法 62
2.2.8 计算逆元 64
重要概念、公式和定理 65
习题 66
2.3 RSA 密码体制 67
2.3.1 模 n 的指数运算 67
2.3.2 指数运算的规则 68
2.3.3 费马小定理 70
2.3.4 RSA 密码体制 71
2.3.5 中国剩余定理 74
重要概念、公式和定理 75
习题 76
2.4 RSA 加密体制的细节 78
2.4.1 模 n 指数运算的实用性 78
2.4.2 使用 RSA 算法会花费多长时间 79
2.4.3 因式分解有多难 80
2.4.4 找大素数 80
重要概念、公式和定理 83
习题 83
第3章 关于逻辑与证明的思考 85
3.1 等价和蕴含 85
3.1.1 语句的等价 85
3.1.2 真值表 87
3.1.3 德摩根律 89
3.1.4 蕴含 90
3.1.5 当且仅当 91
重要概念、公式和定理 93
习题 94
3.2 变元和量词 95
3.2.1 变元和论域 95
3.2.2 量词 96
……