离散数学与算法化思维

第1章引论
1.1离散化
1.1.1为什么要离散化
1.1.2计算机系统本质上是离散的
1.2离散数学与计算机的关系
1.2.1数学是计算机的基础
1.2.2计算机对数学的贡献
1.2.3离散数学的作用
1.2.4离散数学在计算机学科主干课程中的应用
1.3离散数学主题以及算法化思维
1.3.1离散数学主题
1.3.2算法化思维的重要性
1.4如何学习离散数学
1.4.1离散数学的特点
1.4.2学习离散数学要注意的问题
1.5本章小结
习题1
第2章基础知识
2.1集合论
2.1.1集合的基本概念
2.1.2集合论的思想渊源
2.1.3集合表示
2.1.4集合运算及相关算法
2.1.5集合证明技巧
习题2.1
2.2矩阵论
2.2.1矩阵的概念及其基本运算
2.2.2布尔矩阵及布尔积算法
习题2.2
2.3初等数论
2.3.1数的整除性
2.3.2同余
习题2.3
2.4本章小结
自测题2
第3章关系
3.1序偶和笛卡儿积
习题3.1
3.2关系及其表示
3.2.1关系的概念
3.2.2几种特殊的关系
3.2.3关系的表示
习题3.2
3.3关系的性质及其判定算法
3.3.1关系的性质
3.3.2关系性质判定算法
习题3.3
3.4复合关系
3.4.1复合关系的定义
3.4.2关系的复合运算的性质
3.4.3复合关系的矩阵表示及图形表示
3.4.4复合关系生成算法
习题3.4
3.5逆关系
3.5.1逆关系的概念及性质
3.5.2逆关系生成算法
习题3.5
3.6关系的闭包运算
3.6.1关系传递闭包
3.6.2关系传递闭包计算的Warshall算法
习题3.6
3.7等价关系
3.7.1集合的划分和覆盖
3.7.2等价关系与等价类
3.7.3等价关系相关算法
习题3.7
3.8相容关系
习题3.8
3.9偏序关系
3.9.1偏序关系的定义
3.9.2哈斯图及其构造算法
3.9.3偏序集中特殊位置的元素
3.9.4拓扑排序算法
3.9.5良序
习题3.9
3.10格
习题3.10
3.11关系在计算机科学中的应用
3.11.1关系在关系数据库中的应用
3.11.2关系传递闭包在语法分析中的应用
3.12本章小结
自测题3
第4章映射
4.1映射的基本概念
4.1.1映射的概念
4.1.2映射的分类
习题4.1
4.2复合映射和逆映射
4.2.1复合映射
4.2.2逆映射
习题4.2
4.3置换函数
习题4.3
4.4计算机科学中常用的函数
4.4.1特征函数
4.4.2取整函数
4.4.3布尔函数
4.4.4哈希函数
4.4.5算法复杂性分析的数学基础
习题4.4
4.5本章小结
自测题4
第5章组合分析
5.1计数
5.1.1基本计数关系式
5.1.2相容排斥原理
5.1.3加法法则和乘法法则
习题5.1
5.2排列
5.2.1无重复排列
5.2.2有重复的排列
5.2.3排列生成算法
习题5.2
5.3组合
5.3.1无重复的组合
5.3.2有重复的组合
5.3.3组合生成算法
习题5.3
5.4生成函数
习题5.4
5.5鸽巢原理
5.5.1一般的鸽巢原理
5.5.2推广的鸽巢原理
习题5.5
5.6组合分析在计算机中的应用
5.7本章小结
自测题5
第6章代数系统
6.1代数系统发展史
6.2运算与代数系统
6.2.1运算的概念
6.2.2代数系统的概念
6.2.3运算的性质及性质判定算法
6.2.4单位元、零元和逆元
习题6.2
6.3半群
6.3.1半群及其性质
6.3.2单位半群
习题6.3
6.4群
6.4.1群的基本概念
6.4.2群的性质
6.4.3子群
习题6.4
6.5特殊的群
6.5.1交换群
6.5.2循环群
6.5.3置换群
习题6.5
6.6代数系统的同态与同构
习题6.6
6.7代数系统在计算机中的应用
6.7.1布尔代数及其在电路设计中的应用
6.7.2群论在计算机编码纠错中的应用
6.7.3半群与文法及形式语言
习题6.7
6.8本章小结
自测题6
第7章图论
7.1图的基本概念
7.1.1图的定义与分类
7.1.2补图与生成子图
7.1.3握手定理
7.1.4同构图
习题7.1
7.2图的连通性
7.2.1基本路与基本回路
7.2.2图的连通性
习题7.2
7.3图的矩阵表示
7.3.1邻接矩阵
7.3.2可达性矩阵
7.3.3完全关联矩阵
7.3.4与图有关的算法
习题7.3
7.4欧拉图与汉密尔顿图
7.4.1欧拉图
7.4.2汉密尔顿图
习题7.4
7.5二部图及匹配
7.5.1二部图
7.5.2匹配及最大匹配算法
习题7.5
7.6平面图
7.6.1平面图的定义
7.6.2欧拉公式
习题7.6
7.7最短路Dijkstra算法
7.7.1问题的提出
7.7.2Dijkstra算法
习题7.7
7.8树
7.8.1树的基本概念
7.8.2最小生成树Kruskal算法
7.8.3二叉树
7.8.4最优二叉树哈夫曼算法
习题7.8
7.9图论在计算机中的应用
7.9.1二叉树的遍历算法及表达式表示
7.9.2前缀码的设计
7.9.3有限状态机的图表示
7.10本章小结
自测题7
第8章数理逻辑
8.1命题演算
8.1.1命题与命题联结词
8.1.2命题公式
8.1.3真值表及其真值计算算法
8.1.4命题等值式
8.1.5重言式、矛盾式和可满足式
8.1.6蕴涵式
习题8.1
8.2范式
8.2.1对偶原理
8.2.2范式转换算法
8.2.3主范式形成算法
习题8.2
8.3命题推理
8.3.1直接推理法
8.3.2间接推理法
习题8.3
8.4谓词演算
8.4.1个体、谓词和量词
8.4.2谓词公式和辖域
8.4.3谓词公式的解释及逻辑有效式
习题8.4
8.5谓词等值式和置换规则
习题8.5
8.6谓词推理
8.6.1逻辑有效蕴涵式
8.6.2推理定律
8.6.3推理实例
习题8.6
8.7数理逻辑在计算机中的应用
8.7.1逻辑推理在人工智能中的应用
8.7.2人工智能语言Prolog简介
习题8.7
8.8本章小结
自测题8
后记
参考文献