离散数学及其应用(原书第4版)
2002-1-1
机械工业出版社
Kenneth H.Rosen
801
无
本书介绍了离散数学的理论和方法，内容涉及数学推理、组合分析、离散结构和算法设计。本书取材极其广泛，除包括定义、定理的严密陈述外，还配备大量的实例和图、表的说明，适合各种需求的练习和题目，以及丰富的历史资料和网站资源。本书的第3版曾被全世界几百所大学选为教材，第4版作了新的改进和补充。本书适合于数学、计算机科学和工程技术专业人员使用。
第l章 基础：逻辑、集合和函数1．1 逻辑1．1．1 引言1．1．2 命题1．1．3 翻译语言的句子1．1．4 布尔检索l. 1．5 逻辑运算和位运算练习1．2 命题等价1. 2．1 引言1．2．2 逻辑等价练习1．3 谓词和量词1．3．1 引言1．3．2 量词1．3．3 翻译语句为逻辑表达式1．3．4 选自Lewis Carroll的例子(选读)1．3．5 绑定变量1．3．6 否定练习1．4 集合1．4．1 引言1．4．2 幂集合1．4．3 笛卡儿积练习1．5 集合运算1．5．1 引言1．5．2 集合相等1．5．3 扩展的并集和交集1．5．4 集合的计算机表示练习1．6 函数1．6．1 引言1．6．2 一对一函数和映上函数1．6．3 反函数和函数组合1．6．4 函数的图像1．6．5 几个重要的函数练习1．7 序列与求和1．7．1 引言1．7．2 序列1．7．3 特殊的整数序列1．7．4 求和1．7．5 基数(选读)练习1．8 函数增长1．8．1 引言1．8．2 大O符号1．8．3 函数组合的增长1．8．4 大Ω和大Ξ符号练习关键术语和结果复习题补充练习计算机题目计算和研究写作题目第2章 基础：算法、整数和矩阵2．1 算法2．1．1 引言2．1．2 搜索算法练习2．2 算法的复杂性2．2．1 引言练习2．3 整数和除法2．3．1 引言2．3．2 除法2．3．3 素数2．3．4 除法算法2．3．5 最大公约数和最小公倍数2．3．6 模运算2. 3．7 同余应用2．3．8 密码学练习2．4 整数和算法2．4．1 引言2．4．2 欧几里德算法2．4．3 整数表示2．4．4 整数运算算法练习2．5 数论应用2．5．1 引言2．5．2 若干有用的结果2．5．3 线性同余2．5．4 中国余数定理2．5. 5 大整数的计算机算术运算2．5．6 伪素数2．5．7 公钥密码学2．5．8 RSA加密2．5．9 RSA解密2．5．10 用RSA作公钥系统练习2．6 矩阵2．6．1 引言2．6．2 矩阵运算2．6．3 矩阵乘法运算2．6．4 矩阵的转置和幂2．6．5 0-1矩阵练习关键术语和结果复习题补充练习计算机题目计算和研究写作题目第3章 数学推理3．1 证明方法3．1．1 引言3．1．2 推理规则3．1．3 谬误3．1．4 带量词命题的推理规则3．1．5 证明定理的方法3．1．6 定理与量词3．1．7 停机问题3．1．8 关于证明的一些评注练习3．2 数学归纳法3．2．1 引言3．2．2 良序性3．2．3 数学归纳法3．2．4 数学归纳法证明的例子3．2．5 数学归纳法的第二原理练习3．3 递归定义3．3．1 引言3．3．2 递归地定义函数3．3．3 递归地定义集合练习3．4 递归算法3．4．1 引言3．4．2 递归与迭代练习3．5 程序正确性3．5．1 引言3．5．2 程序验证3．5．3 推理规则3．5．4 条件语句3．5．5 循环不变量练习关键术语和结果复习题补充练习计算机题目计算和研究写作题目第4章 计数4．1 计数的基础4．1．1 引言4．1．2 基本的计数原则4．1．3 容斥原理4．1．4 树图练习4．2 鸽巢原理4．2．1 引言4．2．2 推广的鸽巢原理4．2．3 巧妙使用鸽巢原理练习4．3 排列与组合4．3．1 引言4．3．2 排列4．3．3 组合4．3．4 二项式系数4．3．5 二项式定理练习4．4 离散概率4．4．1 引言4．4．2 有限概率4．4．3 事件组合的概率4．4．4 概率的推理练习4．5 概率论4．5．1 引言4．5．2 概率赋值4．5．3 事件的组合4．5．4 条件概率4．5．5 独立性4．5．6 伯努利实验与二项式分布4．5．7 随机变量4．5．8 期望值4．5．9 独立随机变量4．5．10 方差4．5．11 切比雪夫不等式4．5．12 平均状态下的计算复杂性练习4．6 一般性的排列和组合4．6．1 引言4．6．2 有重复的排列4．6．3 有重复的组合4．6．4 具有不可区别物体的集合的排列4．6．5 把物体放入盒子练习4. 7 生成排列和组合4．7．1 引言4．7．2 生成排列4．7．3 生成组合练习关键术语和结果复习题补充练习计算机题目计算和研究写作题目第5章 高级计数技术5．1 递推关系5．1．1 引言5．1．2 递推关系5．1．3 用递推关系构造模型练习5．2 求解递推关系5．2．1 引言5．2．2 求解常系数线性齐次递推关系5．2．3 常系数线性非齐次的递推关系练习5．3 分而治之关系5．3．1 引言5．3．2 分而治之关系练习5．4 生成函数5．4．1 引言5．4．2 关于幂级数的有用的事实5．4．3 计数问题与生成函数5．4．4 使用生成函数求解递推关系5．4．5 使用生成函数证明恒等式练习5．5 容斥5．5．1 引言5．5．2 容斥原理练习5．6 容斥原理的应用5．6．1 引言5．6．2 容斥原理的另一种形式5．6．3 伊拉脱森筛5．6．4 映上函数的个数5．6．5 错位排列练习关键术语和结果复习题补充练习计算机题目计算和研究写作题目第6章 关系6．1 关系及其性质6．1．1 引言6．1．2 函数作为关系6．1．3 集合上的关系6．1．4 关系的性质6．1．5 关系的组合练习6．2 n元关系及其应用6．2．1 引言6. 2．2 n元关系6．2．3 数据库和关系练习6．3 关系的表示6．3．1 引言6．3．2 用矩阵表示关系6．3．3 用图表示关系练习6．4 关系的闭包6．4．1 引言6．4．2 闭包6．4．3 有向图的路径6．4．4 传递闭包6．4．5 沃舍尔算法练习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．6．5 格6．6．6 拓扑排序练习关键术语和结果复习题补充练习计算机题目计算和研究写作题目第7章 图7．1 图的介绍7．1．1 图的种类7．1．2 图模型练习7．2 图的术语7．2．1 引言7．2．2 基本术语7．2．3 一些特殊的简单图7．2．4 偶图7．2．5 特殊类型的图的一些应用7．2．6 从旧图到新图练习7．3 图的表示和图的同构7．3．1 引言7．3．2 图的表示7．3．3 相邻矩阵7．3．4 关联矩阵7．3．5 图的同构练习7. 4 连通性7．4．1 引言7．4．2 通路7．4．3 无向图连通性7．4．4 有向图中的连通性7．4．5 通路与同构7．4．6 统计顶点之间的通路练习7．5 欧拉通路与哈密顿通路7．5．1 引言7．5．2 欧拉回路和欧拉通路的充要条件7．5．3 哈密顿通路和回路练习7．6 最短通路问题7．6．1 引言7．6．2 一个最短通路算法7．6．3 旅行推销员问题练习7．7 平面性图7．7．1 引言7．7．2 欧拉公式7．7．3 库拉图斯基定理练习7．8 图着色7．8．1 引言7．8．2 图着色的应用练习关键术语和结果复习题补充练习计算机题目计算和研究写作题目第8章 树8．1 介绍树8．1．1 树作为模型8．1．2 树的性质练习8．2 树的应用8．2．1 引言8．2．2 二叉搜索树8．2．3 决策树8．2．4 前缀码练习8．3 树的遍历8．3．1 引言8．3．2 通用地址系统8．3．3 遍历算法8．3．4 中缀、前缀和后缀记法练习8．4 树与排序8．4．1 引言8．4．2 排序的复杂性8．4．3 冒泡排序8．4．4 归并排序练习8．5 生成树8．5．1 引言8．5．2 一些构造生成树的算法8．5．3 回溯练习8．6 最小生成树8．6．1 引言8．6．2 最小生成树算法练习关键术语和结果复习题补充练习计算机题目计算和研究写作题目第9章 布尔代数9．1 布尔函数9．1．1 引言9．1．2 布尔表达式和布尔函数9．1．3 布尔代数中的恒等式9．1．4 对偶性9．1．5 布尔代数的抽象定义练习9．2 布尔函数的表示9．2．1 积之和展开式9．2．2 函数完备性练习9．3 逻辑门电路9．3．1 引言9．3. 2 门的组合9．3．3 电路的例子9．3．4 加法器练习9．4 电路的极小化9．4．1 引言9．4．2 卡诺图9．4．3 无需在意条件9．4．4 奎因-莫可拉斯基方法练习关键术语和结果复习题补充练习计算机题目计算和研究写作题目第10章 计算模型10．1 语言和文法10．1．1 引言10．1．2 短语结构文法10．1．3 短语结构文法的类型10．1．4 派生树10．1．5 巴科斯-诺尔范式练习10．2 带输出的有限状态机10．2．1 引言10．2．2 带输出的有限状态机练习10．3 不带输出的有限状态机10．3．1 引言10．3．2 串的集合10．3．3 有限状态自动机练习10．4 语言的识别10．4．1 引言10．4．2 正则集合10．4．3 克莱因定理10．4．4 正则集合和正则文法10．4．5 一个不能由有限状态自动机识别语言10．4．6 一些更强大的机器练习10．5 图灵机10．5．1 引言10．5．2 图灵机的定义10．5．3 用图灵机识别集合10．5．4 用图灵机计算函数10．5．5 不同类型的图灵机10. 5．6 丘奇-图灵论题练习关键术语和结果复习题补充练习计算机题目计算和研究写作题目附录A 指数函数和对数函数附录B 伪代码奇数练习题答案推荐读物参考文献
无