| 作者 |
| 克利福德·斯坦罗伯特·L.戴斯得尔肯尼斯·博加特 汤姆·詹金斯 本·斯蒂芬森 |
| 丛书名 |
| 计算机科学丛书 |
| 出版社 |
| 机械工业出版社 |
| ISBN |
| 9782109279270 |
| 简要 |
| 简介 |
| 内容简介书籍计算机书籍 ---------------------------8084209 - 离散数学：面向计算机科学专业--------------------------- 本书由计算机和数学领域的三位教授联合撰写，是为计算机专业量身定制的离散数学教材。针对初入学的本科生不理解为何要学习高深的数学，授课教师苦于向毫无编程经验的学生讲授繁杂的算法程序的问题，本书打破了传统的课程顺序和教学方法，明确“为何学”和“有何用”，不仅清晰呈现了计算机专业学生必需的数学知识，而且通过实践和应用启发学生对后续课程的学习兴趣。主要内容涵盖计数、密码学与数论、逻辑与证明、归纳法、递归、概率以及图论等。本书推导严谨、代码清晰、练习丰富，可作为高等学校计算机相关专业的离散数学课程的教材，也可供计算机技术人员学习与参考。 ---------------------------8069660 - 计算机离散数学基础--------------------------- 本书选取了计算机科学专业的学生需要掌握的离散数学基础知识和核心理论进行系统的介绍，以利用计算机解决问题为主要目标，将理论与实践结合起来，使学生充分认识抽象的重要性。全书选材适当、结构清晰、叙述简明、推理严谨，适合作为高校计算机专业离散数学课程的教材，也适合从事计算机软件开发工作的技术人员学习。 |
| 目录 |
| [套装书具体书目] 8069660 - 计算机离散数学基础 - 9787111652267 - 机械工业出版社 - 定价 79 8084209 - 离散数学：面向计算机科学专业 - 9787111689454 - 机械工业出版社 - 定价 99 ---------------------------8084209 - 离散数学：面向计算机科学专业--------------------------- 译者序 前言 第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 3.2.3 量词化的标准记号 98 3.2.4 关于变元的语句 99 3.2.5 重写语句以包含更大的论域 99 3.2.6 证明量词语句的真假 100 3.2.7 量词语句的否定101 3.2.8 隐式量词化 102 3.2.9 量词语句的证明103 重要概念、公式和定理 104 习题 105 3.3 推理 106 3.3.1 直接推理（演绎推理）和证明 106 3.3.2 直接证明的推理规则 108 3.3.3 推理的逆否（对换）规则 109 3.3.4 反证法 110 重要概念、公式和定理 112 习题 113 第4章 归纳、递归和递推式 115 4.1 数学归纳法 115 4.1.1 最小反例 115 4.1.2 数学归纳法原理118 4.1.3 强归纳法 120 4.1.4 归纳法的一般形式 121 4.1.5 从递归视角看归纳法 123 4.1.6 结构归纳法 126 重要概念、公式和定理 128 习题 128 4.2 递归、递推式和归纳法 130 4.2.1 递归130 4.2.2 一阶线性递推式举例 132 4.2.3 迭代递推式 133 4.2.4 等比级数 134 4.2.5 一阶线性递推式137 重要概念、公式和定理 140 习题 141 4.3 递推式解的增长率142 4.3.1 分治算法 142 4.3.2 递归树 144 4.3.3 三种不同的行为149 重要概念、公式和定理 151 习题 152 4.4 主定理153 4.4.1 主定理基础 153 4.4.2 求解更一般的递推式 156 4.4.3 扩展主定理 156 重要概念、公式和定理 158 习题 158 4.5 更一般的递推式 159 4.5.1 递推不等式 159 4.5.2 不等式主定理 160 4.5.3 归纳法的一个窍门 161 4.5.4 更多归纳证明的窍门 163 4.5.5 处理 nc 以外的函数 165 重要概念、公式和定理 166 习题 167 4.6 递推式和选择 168 4.6.1 选择的理念 168 4.6.2 一种递归选择算法 169 4.6.3 中位数未知情况下的选择 170 4.6.4 一种查找中间一半中元素的算法 171 4.6.5 对修改后的选择算法的分析174 4.6.6 不均匀划分 175 重要概念、公式和定理 177 习题 178 第5章 概率179 5.1 概率导论 179 5.1.1 为什么学习概率179 5.1.2 概率计算举例 181 5.1.3 互补概率 182 5.1.4 概率与散列法 182 5.1.5 均匀概率分布 184 重要概念、公式和定理 186 习题 187 5.2 并集和交集 188 5.2.1 并集事件的概率188 5.2.2 概率的容斥原理190 5.2.3 计数的容斥原理195 重要概念、公式和定理 196 习题 197 5.3 条件概率和独立性198 5.3.1 条件概率 198 5.3.2 贝叶斯定理 201 5.3.3 独立性 201 5.3.4 独立试验过程 203 5.3.5 树形图 204 5.3.6 素数测试 207 重要概念、公式和定理 208 习题 209 5.4 随机变量 210 5.4.1 什么是随机变量210 5.4.2 二项式概率 211 5.4.3 体验生成函数 212 5.4.4 期望值 213 5.4.5 期望值的求和与数值乘法 216 5.4.6 指示器随机变量218 5.4.7 第一次成功的尝试次数 219 重要概念、公式和定理 220 习题 222 5.5 散列中的概率计算223 5.5.1 每个位置上元素的期望个数224 5.5.2 空位置的期望个数 224 5.5.3 冲突的期望个数225 5.5.4 元素在散列表的一个位置上的最大期望个数 227 重要概念、公式和定理 231 习题 231 5.6 条件期望、递推和算法 234 5.6.1 当运行时间不仅依赖输入的大小时 234 5.6.2 条件期望值 236 5.6.3 随机算法 237 5.6.4 重温选择算法 239 5.6.5 快速排序 240 5.6.6 随机选择的更详细分析 243 重要概念、公式和定理 244 习题 245 5.7 概率分布和方差 247 5.7.1 随机变量的分布247 5.7.2 方差250 重要概念、公式和定理 255 习题 256 第6章 图论259 6.1 图 259 6.1.1 顶点的度 261 6.1.2 连通性 263 6.1.3 环 264 6.1.4 树 265 6.1.5 树的其他性质 265 重要概念、公式和定理 267 习题 269 6.2 生成树和根树 270 6.2.1 生成树 270 6.2.2 广度优先搜索 272 6.2.3 根树275 重要概念、公式和定理 278 习题 279 6.3 欧拉图和哈密顿图281 6.3.1 欧拉环游和迹 281 6.3.2 寻找欧拉环游 284 6.3.3 哈密顿路径和回路 285 6.3.4 NP 完全问题 289 6.3.5 证明问题是 NP 完全的 291 重要概念、公式和定理 293 习题 294 6.4 匹配定理 296 6.4.1 匹配的概念 296 6.4.2 使得匹配更大 299 6.4.3 二部图的匹配 301 6.4.4 搜索二部图的增广路径 302 6.4.5 增广覆盖算法 304 6.4.6 高效算法 308 重要概念、公式和定理 309 习题 310 6.5 着色与平面性 311 6.5.1 着色的概念 311 6.5.2 区间图 313 6.5.3 平面性 315 6.5.4 平面画法的面 316 6.5.5 五色定理 319 重要概念、公式和定理 322 习题 322 附录 A 更一般的主定理推导 324 附录 B 习题答案和提示332 参考文献 347 索引 349 ---------------------------8069660 - 计算机离散数学基础--------------------------- 出版者的话 译者序 前言 第1章 算法、数和机器1 1.1 什么是算法3 1.2 整数算法和复杂度6 1.2.1 素数测试7 1.2.2 实数8 1.2.3 改进素数测试算法9 1.2.4 素数分解11 1.2.5 对数12 1.2.6 最大公约数14 1.3 数的机器表示16 1.3.1 近似误差17 1.3.2 二进制、八进制和十六进制19 1.4 数值求解25 1.4.1 牛顿的平方根求解方法26 1.4.2 二分法27 习题30 第2章 集合、序列和计数32 2.1 朴素集合论32 2.1.1 可恶的图书管理员34 2.1.2 集合运算和基数34 2.1.3 鸽巢原理36 2.2 序列37 2.2.1 子集的特征序列38 2.3 计数39 2.3.1 n元集合上的k元序列数40 2.3.2 n元集合的子集数40 2.3.3 n元集合上的k元排列数40 2.3.4 n的阶乘41 2.3.5 n元集合上的k元子集数42 2.3.6 Pascal三角形44 2.3.7 非公式的计数策略46 2.4 无限序列和复杂度函数49 2.4.1 汉诺塔51 2.4.2 差的复杂度函数53 习题54 第3章 布尔表达式、逻辑和证明56 3.1 贪心算法和饼干选择问题56 3.1.1 贪心算法56 3.2 布尔表达式和真值表60 3.2.1 否算子60 3.2.2 合取算子60 3.2.3 析取算子60 3.2.4 条件算子62 3.2.5 双向条件算子63 3.3 谓词和量词64 3.4 有效推理65 3.5 证明实例68 3.5.1 直接证明70 3.5.2 间接证明71 3.5.3 Cantor的对角线方法73 3.6 数学归纳法75 3.6.1 强归纳法82 3.7 第1章的待证明结论83 3.7.1 RPM的正确性证明83 3.7.2 切蛋糕难题的正确性证明85 3.7.3 舍九法的正确性证明87 3.7.4 GCD欧几里得算法的正确性证明88 3.8 第2章的待证明结论90 习题92 第4章 查找和排序95 4.1 查找95 4.1.1 查找任意列表95 4.1.2 查找有序列表96 4.2 分支图100 4.2.1 二分查找的第二个版本101 4.3 排序106 4.3.1 选择排序106 4.3.2 交换排序108 4.4 至少有n!个叶子的二叉树113 4.5 划分排序120 4.6 排序算法比较129 4.6.1 时间和运算的计数130 习题131 第5章 图和树134 5.1 引言134 5.1.1 度137 5.1.2 欧拉图138 5.1.3 哈密顿图139 5.2 路径、回路和多边形139 5.2.1 路径确定的子图140 5.3 树142 5.3.1 遍历142 5.4 边带权图153 5.4.1 最短路径157 5.5 有向图157 5.5.1 有向路径158 5.5.2 距离函数159 5.5.3 Dijkstra算法159 5.5.4 Floyd-Warshall算法165 习题169 第6章 关系：特别是(整数)序列上的关系171 6.1 关系和表示171 6.1.1 矩阵表示171 6.1.2 有向图表示172 6.1.3 关系的性质172 6.2 等价关系173 6.2.1 等价关系的矩阵和有向图表示174 6.3 序关系176 6.3.1 偏序的矩阵和有向图表示177 6.3.2 极小元和极大元178 6.4 有限序列上的关系180 6.4.1 支配180 6.4.2 字典序182 6.5 无限序列上的关系184 6.5.1 渐近支配和大O表示法185 6.5.2 渐近等价和大Θ表示189 6.5.3 渐近排序191 6.5.4 强渐近支配和小o表示192 习题194 第7章 序列和级数197 7.1 递推方程实例197 7.2 求解一阶线性递推方程202 7.3 Fibonacci序列206 7.3.1 Fibonacci序列算法208 7.3.2 黄金比例210 7.3.3 Fibonacci序列和黄金比例210 7.3.4 Fibonacci序列的阶213 7.3.5 GCD的欧几里得算法的复杂度213 7.4 求解二阶线性递推方程216 7.5 无限级数221 7.5.1 芝诺悖论221 7.5.2 序列和级数收敛的形式化定义222 习题227 第8章 生成序列和子集231 8.1 以字典序生成序列232 8.2 生成{1..n}的所有k元序列234 8.2.1 平均情况复杂度235 8.3 生成{1..n}的升序序列子集237 8.4 按字典序生成全排列244 8.4.1 按字典序生成{1..n}的所有k元排列251 习题254 第9章 离散概率和平均情况复杂度260 9.1 概率模型260 9.1.1 采样空间260 9.1.2 概率函数261 9.1.3 特例：等概率输出262 9.2 条件概率264 9.2.1 组合事件265 9.2.2 条件概率265 9.2.3 独立事件266 9.2.4 互斥事件266 9.3 随机变量和期望值270 9.3.1 期望频率270 9.3.2 期望值271 9.3.3 概率分布272 9.4 标准分布及其期望值273 9.4.1 均匀分布273 9.4.2 二项分布276 9.4.3 几何分布277 9.5 条件期望值279 9.5.1 条件期望282 9.6 平均情况复杂度284 9.6.1 将期望应用于线性查找284 9.6.2 将期望应用于QuickSort285 习题289 第10章 图灵机293 10.1 什么是算法293 10.1.1 Church-Turing理论299 10.1.2 通用图灵机：计算模型299 10.1.3 停机问题300 习题302 索引304 |