离散数学结构——理论与应用(翻译版)
作者： 邱仲潘
出版时间：2005-11-30
出版社：高等教育出版社
- 高等教育出版社
- 9787040173901
- 1
- 101932
- 44211894-9
- 平装
- 异16开
- 2005-11-30
- 1340
- 940
- 理学
- 数学
- O158
- 计算机科学与技术
- 本科
离散数学结构是计算机学科课程体系中一门重要的课程。本书采用一种全新的方法来讲授计算机科学的数学基础，包括逻辑、布尔代数、图论基础、有限状态机、语法和算法等。这门计算机专业必修课有助于学生理解数学论题的构建和数学推理的过程。
本书特色：专为大学本科离散数学课程设计，书中各章均包含l00多道练习题，贯穿全书的习题解答为培养学生解决问题的技巧提供了示范，提供了丰富的样例集和可视图表，清晰地定义和解释了重要概念，通过教学网站提供给学生额外的练习题、资源网站链接和习题解答手册。
本书中所介绍的方法是作者多年教学经验的结晶，采用这种理论与应用相结合的方法，可以提高学生的学习兴趣，降低学习难度。在各章，作者使用现实世界中具体的事例来激发学生理解数学中抽象概念的能力。本书包含有大量的示例和补充练习，使学生在编程实践中灵活运用计算机科学知识，学习并巩固了一些重要的概念。本书不仅在讲授方法上是理论与实践相结合的范本，而且在语言叙述上与课堂授课的风格相一致。
第一章 集合论、逻辑与算法基础
1.1 集合
1.1.1 文氏图
1.1.2 集合运算
1.1.3 有序对与笛卡儿叉积
1.1.4 集合的计算机表示
课堂练习
本节小结
习题1.1
1.2 数理逻辑
1.2.1 非
1.2.2 合取
1.2.3 析取
1.2.4 蕴涵
1.2.5 双向蕴涵
1.2.6 命题公式(公式)
课堂练习
本节小结
习题1.2
1.3 论证有效性
1.3.1 一些有效论证形式
课堂练习
本节小结
习题1.3
1.4 量词与一阶逻辑
1.4.1 谓词求非
1.4.2 其他推理规则
课堂练习
本节小结
习题1.4
1.5 证明方法
1.5.1 直接证明
1.5.2 间接证明
1.5.3 反证法
1.5.4 证明双向蕴涵
1.5.5 证明等价命题
1.5.6 证明中的错误
课堂练习
本节小结
习题1.5
1.6 算法
1.6.1 伪码约定
1.6.2 多项式运算
课堂练习
本节小结
习题1.6
编程练习
第二章 整数与数学归纳法
2.1 整数
2.1.1 除法算法
2.1.2 最大公约数
2.1.3 最小公倍数
课堂练习
本节小结
习题2.1
2.2 计算机中的整数表示
2.2.1 二进制数运算
课堂练习
本节小结
习题2.2
2.3 数学归纳法
2.3.1 应用：循环不变量(程序正确性)
课堂练习
本节小结
习题2.3
2.4 素数
2.4.1 正整数因子分解
课堂练习
本节小结
习题2.4
2.5 线性丢番图方程
课堂练习
本节小结
习题2.5
编程练习
第三章 关系与偏序集
3.1 关系
3.1.1 关系的域与值域
3.1.2 等价关系
3.1.3 等价类与划分
3.1.4 闭包
课堂练习
本节小结
习题3.1
3.2 偏序集
3.2.1 词典序
3.2.2 偏序集的有向图
3.2.3 哈塞图
3.2.4 极小元与极大元
3.2.5 格
课堂练习
本节小结
习题3.2
3.3 应用：关系型数据库
3.3.1 结构化查询语言
课堂练习
本节小结
习题3.3
编程练习
第四章 矩阵与关系闭包
4.1 矩阵
4.1.1 矩阵转置
4.1.2 对称矩阵
4.1.3 布尔(0-1)矩阵
课堂练习
本节小结
习题4.1
4.2 关系矩阵与闭包
4.2.1 求传递闭包的Warshall算法
课堂练习
本节小结
习题4.2
编程练习
第五章 函数
5.1 函数
5.1.1 单射、满射和一一映射
5.1.2 复合
课堂练习
本节小结
习题5.1
5.2 特殊函数与集合的基数
5.2.1 函数的逆
5.2.2 限制、扩展、映像和预映像
5.2.3 弱取整函数与强取整函数
5.2.4 集合的基数
课堂练习
本节小结
习题5.2
5.3 序列与字符串
5.3.1 特殊数列
5.3.2 求和
5.3.3 索引变量的改变
5.3.4 积
5.3.5 字符串(单词)
5.3.6 在计算机内存中表示字符串
课堂练习
本节小结
习题5.3
5.4 二元运算
课堂练习
本节小结
习题5.4
编程练习
第六章 同余
6.1 同余
6.1.1 整除测试
6.1.2 同余类的加法与乘法
课堂练习
本节小结
习题6.1
6.2 校验位
6.2.1 ISBN
6.2.2 UPC-A与EAN-
6.2.3 信用卡的校验位
课堂练习
本节小结
习题6.2
6.3 线性同余
6.3.1 中国余数定理
6.3.2 整数的模(余)表示
6.3.3 循环赛
6.3.4 散列函数
课堂练习
本节小结
习题6.3
6.4 特殊同余定理
6.4.1 密码学
课堂练习
本节小结
习题6.4
编程练习
第七章 计数原理
7.1 基本计数原理
7.1.1 加法原理
7.1.2 乘法原理
7.1.3 同时使用加法与乘法原理
7.1.4 容斥原理
课堂练习
本节小结
习题7.1
7.2 鸽巢原理
课堂练习
本节小结
习题7.2
7.3 排列
课堂练习
本节小结
习题7.3
7.4 组合
课堂练习
本节小结
习题7.4
7.5 广义排列与组合
课堂练习
本节小结
习题7.5
7.6 二项式系数
7.6.1 计算阶乘与C(n,r)的算法
课堂练习
本节小结
习题7.6
7.7 生成排列与组合
课堂练习
本节小结
习题7.7
7.8 离散概率
7.8.1 公理方法
7.8.2 条件概率
课堂练习
本节小结
习题7.8
编程练习
第八章 递归关系
8.1 数列与递归关系
8.1.1 用迭代(替代)法求解递归关系
课堂练习
本节小结
习题8.1
8.2 线性齐次递归关系
课堂练习
本节小结
习题8.2
8.3 线性非齐次递归关系
课堂练习
本节小结
习题8.3
编程练习
第九章 算法与时间复杂度
9.1 算法分析
课堂练习
本节小结
习题9.1
9.2 各种算法
9.2.1 顺序查找
9.2.2 折半查找
9.2.3 选择排序
9.2.4 插入排序
9.2.5 基于比较的排序算法的下限
9.2.6 合并排序
9.2.7 合并排序算法分析
9.2.8 列表中的最小元素与最大元素
9.2.9 Strassen矩阵乘法
9.2.10 矩阵连乘
9.2.11 chainedMatrixMultipli-cation 函数分析
课堂练习
本节小结
习题9.2
编程练习
第十章 图论
10.1 图的定义与符号
10.1.1 有向图
10.1.2 简单图
10.1.3 子图
课堂练习
本节小结
习题10.1
10.2 通路、路径与圈
10.2.1 匹配
课堂练习
本节小结
习题10.2
10.3 图的矩阵表示
10.3.1 相邻矩阵
10.3.2 关联矩阵
课堂练习
本节小结
习题10.3
10.4 特殊回路
10.4.1 欧拉回路
10.4.2 哈密尔顿圈
课堂练习
本节小结
习题10.4
10.5 同构
课堂练习
本节小结
习题10.5
10.6 图算法
10.6.1 最短路径算法
10.6.2 Dijkstra最短路径算法
10.6.3 拓扑排序
课堂练习
本节小结
习题10.6
10.7 平面图与图着色
10.7.1 平面图
10.7.2 图着色
课堂练习
本节小结
习题10.7
编程练习
第十一章 树与网络
11.1 树
11.1.1 树的同构
课堂练习
本节小结
习题11.1
11.2 有根树
11.2.1 二叉树
11.2.2 二叉树遍历
11.2.3 二叉搜索树
11.2.4 二叉搜索树分析
11.2.5 表达式树
11.2.6 二叉树的同构
课堂练习
本节小结
习题11.2
11.3 生成树
11.3.1 最小生成树
课堂练习
本节小结
习题11.3
11.4 网络
11.4.1 (再谈)匹配
课堂练习
本节小结
习题11.4
编程练习
第十二章 布尔代数与组合电路
12.1 二元布尔代数
课堂练习
本节小结
习题12.1
12.2 布尔代数
课堂练习
本节小结
习题12.2
12.3 逻辑门与组合电路
12.3.1 Karnaugh图与布尔表达式的最小化
12.3.2 涉及三个变量的K-图和布尔表达式的最小化
12.3.3 涉及四个变量的K-图与布尔表达式的最小化
课堂练习
本节小结
习题12.3
编程练习
第十三章 有限自动机与语言
13.1 有限自动机与规则语言
13.1.1 确定有限自动机
13.1.2 源引理的应用
13.1.3 规则语言的代数性质
13.1.4 非确定有限自动机
课堂练习
本节小结
习题13.1
13.2 带输入和输出的有限状态机
课堂练习
本节小结
习题13.2
13.3 文法与语言
课堂练习
本节小结
习题13.3
编程练习
附录
部分习题答案与提示
符号表
参考文献
