离散数学

作者简介

离散数学是计算机科学基础理论的核心课程，也是现代数学的一个重要分支。《高等学校计算机类课程应用型人才培养规划教材:离散数学》包含了集合论、图论、数理逻辑、组合数学、代数系统等内容。在介绍离散数学主要内容的同时，对相关知识的专业应用也做了实用性介绍。

书籍目录

第一篇 集 合 论 第1章 集合 1.1 集合的概念与表示 1.1.1 集合及其表示 1.1.2 子集与幂集 1.2 集合的运算 1.2.1 集合的交、并、补、差 1.2.2 集合运算的性质 1.3 容斥原理 本章小结 习题一 第2章 关系 2.1 关系的概念与表示 2.1.1 笛卡儿积 2.1.2 关系的概念 2.1.3 关系的表示 2.2 关系的基本性质 2.2.1 自反 2.2.2 对称 2.2.3 传递 2.3 关系的运算 2.3.1 关系的交、并、补、差 2.3.2 关系的复合 2.3.3 关系的逆 2.3.4 关系的闭包 2.4 等价关系与序关系 2.4.1 等价关系与划分 2.4.2 序关系 本章小结 习题二 第3章 函数 3.1 函数的概念与分类 3.1.1 函数的概念 3.1.2 函数的分类 3.2 函数的运算 3.2.1 函数的复合 3.2.2 函数的逆 3.3 计算机科学中常用的两类函数 3.3.1 取整函数 3.3.2 哈希函数 3.4 基数 3.4.1 基数的概念 3.4.2 可数集与不可数集 本章小结 习题三 第二篇 图 论 第4章 图 4.1 图的概念与表示 4.1.1 图的基本概念 4.1.2 图的矩阵表示 4.2 路径与连通性 4.2.1 路径与回路 4.2.2 图的连通性 4.3 欧拉图与汉密尔顿图 4.3.1 欧拉图 4.3.2 汉密尔顿图 4.4 图的应用 4.4.1 最短路径问题 4.4.2 支配集与通信系统建站问题 本章小结 习题四 第5章 树 5.1 树与图的生成树 5.1.1 树的概念与性质 5.1.2 图的生成树 5.2 根树 5.2.1 根树的基本概念 5.2.2 二叉树 5.2.3 二叉树的遍历 5.3 树的应用 5.3.1 决策树 5.3.2 二叉搜索树 5.3.3 最优二叉树与哈夫曼编码 本章小结 习题五 第三篇 数理逻辑 第6章 命题逻辑 6.1 命题与命题公式 6.1.1 命题的概念与表示 6.1.2 命题联结词 6.1.3 命题公式 6.2 命题公式的真值赋值与分类 6.2.1 真值表 6.2.2 重言式、矛盾式与可满足式 6.2.3 逻辑等价与逻辑蕴涵 6.3 范式 6.3.1 合取范式与析取范式 6.3.2 主析取范式与主合取范式 6.3.3 联结词的完备集 6.4 命题逻辑的推理理论 6.4.1 推理的形式结构 6.4.2 推理规則 本章小结 习题六 第7章 谓词逻辑 7.1 谓词与谓词公式 7.1.1 个体、谓词与量词 7.1.2 项与谓词公式 7.1.3 变元的约束 7.2 谓词逻辑的语义 7.2.1 真值与解释 7.2.2 永真式、矛盾式与可满足式 7.2.3 逻辑等价与逻辑蕴涵 7.3 前束范式 7.4 谓词逻辑的推理理论 本章小结 习题七 第四篇 组合数学 第8章 组合数学 8.1 基本计数原理 8.1.1 加法原理 8.1.2 乘法原理 8.2 排列与组合 8.2.1 排列 8.2.2 组合 8.2.3 广义的排列与组合 8.3 二项式系数与组合恒等式 8.3.1 二项式系数 8.3.2 组合恒等式 8.4 鸽笼原理 8.4.1 鸽笼原理的简单形式 8.4.2 鸽笼原理的一般形式 8.5 递归关系及其解法 8.5.1 递归关系的定义 8.5.2 逆向代换法 8.5.3 常系数齐次线性递归关系 8.5.4 常系数非齐次线性递归关系 本章小结 习题八 第五篇 代数系统 第9章 代数系统 9.1 代数系统的概念及运算性质 9.1.1 代数系统的概念 9.1.2 二元运算的性质 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.5 格与布尔代数 9.5.1 格的概念与性质 9.5.2 分配格、有补格 9.5.3 布尔代数 本章小结 习题九 附录A 参考文献

编辑推荐

《高等学校计算机类课程应用型人才培养规划教材:离散数学》适合作为计算机和相关专业本科生“离散数学”的教学用书，也可以作为对离散数学感兴趣的学生的参考书。

章节摘录

版权页：   插图：   5.2.3 二叉树的遍历 利用树进行信息处理，经常会涉及逐个不重复地访问树中的所有结点，这称为树的遍历。二叉树的遍历是最基本的遍历算法，下面介绍二叉树遍历的三种常用算法。 根据定义，二叉树由根结点和左、右两棵子树三部分构成，如果用T代表访问根结点，L代表遍历左子树，尺代表遍历右子树，則二叉树可以有TLR、LTR、LRT、TRL、RTL和RLT六种遍历方式，然而经常用到的总是先左后右的顺序，所以我们将TLR表示的遍历称为先根遍历，LTR表示的遍历称为中根遍历，而LRT表示的遍历称为后根遍历。具体的说，二叉树的先根遍历算法如下： （1）访问根结点； （2）对根结点的左子树进行先根遍历； （3）对根结点的右子树进行先根遍历。 二叉树的中根遍历算法如下： （1）对根结点的左子树进行中根遍历； （2）访问根结点； （3）对根结点的右子树进行中根遍历。 二叉树的后根遍历算法如下： （1）对根结点的左子树进行后根遍历； （2）对根结点的右子树进行后根遍历； （3）访问根结点。 [例5.14） 对图5-15中的二叉树，先根遍历访问各结点的川页序依次为：v1，v2，v4，v8，v5，v3，v6，v9，v10，v7；中根遍历访问各结点的顺序依次为：v4 v8 v2 v5 v1 v9 v6 v10 v3 v7；后根遍历访问各结点的顺序依次为： v8 v4 v5 v2 v9 v10 v6 v7 v3 v10。 利用二叉树可以表示算术表达式。表示时，通常将运算符放在分支结点上；数值或变量放在叶结点上；被减数和被除数作为其双亲结点的左孩子。 （例5.15] 算术表达式a+b×c-（d+e）／f可表示成图5-16中的二叉树。 中根遍历访问各结点的结果是：a+b×c-（d+e）／f。 先根遍历访问各结点的结果是：+a-×bc／+df／。 后根遍历访问各结点的结果是：abc×de+f／-+。 上述遍历结果显示，中根遍历的结果是还原算术表达式，这样的表示因为运算符放在参与运算的两个量之间，也称为中缀表示；先根遍历的结果是将运算符放在参加运算的两个量之前，因而称为前缀表示或波兰式；后根遍历的结果是将运算符放在参加运算的两个量之后，因而称为后缀表示或逆波兰式。对于每个运算，由于参与运算的量的个数固定，因此前缀表示和后缀表示都无须括号；只有中缀表示为了区分不同运算之间的优先级，才须加上括号。

图书封面

---

 离散数学下载

---