离散数学与算法化思维PDF电子书下载

第1章 引论 1

1.1离散化 1

1.1.1为什么要离散化 1

1.1.2计算机系统本质上是离散的 2

1.2离散数学与计算机的关系 3

1.2.1数学是计算机的基础 3

1.2.2计算机对数学的贡献 5

1.2.3离散数学的作用 6

1.2.4离散数学在计算机学科主干课程中的应用 8

1.3离散数学主题以及算法化思维 9

1.3.1离散数学主题 9

1.3.2算法化思维的重要性 11

1.4如何学习离散数学 12

1.4.1离散数学的特点 12

1.4.2学习离散数学要注意的问题 12

1.5本章小结 13

习题1 15

第2章 基础知识 16

2.1集合论 16

2.1.1集合的基本概念 16

2.1.2集合论的思想渊源 18

2.1.3集合表示 21

2.1.4集合运算及相关算法 23

2.1.5集合证明技巧 30

习题2.1 32

2.2矩阵论 33

2.2.1矩阵的概念及其基本运算 33

2.2.2布尔矩阵及布尔积算法 37

习题2.2 39

2.3初等数论 39

2.3.1数的整除性 39

2.3.2同余 41

习题2.3 41

2.4本章小结 42

自测题2 45

第3章 关系 47

3.1序偶和笛卡儿积 47

习题3.1 50

3.2关系及其表示 50

3.2.1关系的概念 50

3.2.2几种特殊的关系 51

3.2.3关系的表示 52

习题3.2 54

3.3关系的性质及其判定算法 54

3.3.1关系的性质 54

3.3.2关系性质判定算法 55

习题3.3 57

3.4复合关系 58

3.4.1复合关系的定义 58

3.4.2关系的复合运算的性质 59

3.4.3复合关系的矩阵表示及图形表示 60

3.4.4复合关系生成算法 61

习题3.4 62

3.5逆关系 63

3.5.1逆关系的概念及性质 63

3.5.2逆关系生成算法 65

习题3.5 65

3.6关系的闭包运算 66

3.6.1关系传递闭包 66

3.6.2关系传递闭包计算的Warshall算法 68

习题3.6 70

3.7等价关系 70

3.7.1集合的划分和覆盖 70

3.7.2等价关系与等价类 71

3.7.3等价关系相关算法 74

习题3.7 75

3.8相容关系 76

习题3.8 79

3.9偏序关系 79

3.9.1偏序关系的定义 79

3.9.2哈斯图及其构造算法 80

3.9.3偏序集中特殊位置的元素 81

3.9.4拓扑排序算法 83

3.9.5良序 83

习题3.9 84

3.10格 85

习题3.10 91

3.11关系在计算机科学中的应用 92

3.11.1关系在关系数据库中的应用 92

3.11.2关系传递闭包在语法分析中的应用 93

3.12本章小结 95

自测题3 97

第4章 映射 100

4.1映射的基本概念 100

4.1.1映射的概念 100

4.1.2映射的分类 103

习题4.1 105

4.2复合映射和逆映射 106

4.2.1复合映射 106

4.2.2逆映射 108

习题4.2 110

4.3置换函数 111

习题4.3 112

4.4计算机科学中常用的函数 112

4.4.1特征函数 112

4.4.2取整函数 114

4.4.3布尔函数 117

4.4.4哈希函数 118

4.4.5算法复杂性分析的数学基础 120

习题4.4 123

4.5本章小结 124

自测题4 125

第5章 组合分析 126

5.1计数 126

5.1.1基本计数关系式 126

5.1.2相容排斥原理 126

5.1.3加法法则和乘法法则 129

习题5.1 130

5.2排列 131

5.2.1无重复排列 131

5.2.2有重复的排列 131

5.2.3排列生成算法 132

习题5.2 134

5.3组合 135

5.3.1无重复的组合 135

5.3.2有重复的组合 136

5.3.3组合生成算法 138

习题5.3 139

5.4生成函数 139

习题5.4 141

5.5鸽巢原理 142

5.5.1一般的鸽巢原理 142

5.5.2推广的鸽巢原理 142

习题5.5 143

5.6组合分析在计算机中的应用 144

5.7本章小结 145

自测题5 146

第6章 代数系统 148

6.1代数系统发展史 148

6.2运算与代数系统 150

6.2.1运算的概念 150

6.2.2代数系统的概念 151

6.2.3运算的性质及性质判定算法 151

6.2.4单位元、零元和逆元 153

习题6.2 156

6.3半群 157

6.3.1半群及其性质 157

6.3.2单位半群 159

习题6.3 160

6.4群 161

6.4.1群的基本概念 161

6.4.2群的性质 162

6.4.3子群 163

习题6.4 165

6.5特殊的群 166

6.5.1交换群 166

6.5.2循环群 167

6.5.3置换群 168

习题6.5 169

6.6代数系统的同态与同构 170

习题6.6 175

6.7代数系统在计算机中的应用 176

6.7.1布尔代数及其在电路设计中的应用 176

6.7.2群论在计算机编码纠错中的应用 177

6.7.3半群与文法及形式语言 180

习题6.7 181

6.8本章小结 182

自测题6 183

第7章 图论 186

7.1图的基本概念 186

7.1.1图的定义与分类 186

7.1.2补图与生成子图 188

7.1.3握手定理 189

7.1.4同构图 190

习题7.1 192

7.2图的连通性 193

7.2.1基本路与基本回路 193

7.2.2图的连通性 195

习题7.2 196

7.3图的矩阵表示 197

7.3.1邻接矩阵 197

7.3.2可达性矩阵 199

7.3.3完全关联矩阵 201

7.3.4与图有关的算法 202

习题7.3 203

7.4欧拉图与汉密尔顿图 203

7.4.1欧拉图 203

7.4.2汉密尔顿图 206

习题7.4 208

7.5二部图及匹配 210

7.5.1二部图 210

7.5.2匹配及最大匹配算法 211

习题7.5 214

7.6平面图 215

7.6.1平面图的定义 215

7.6.2欧拉公式 217

习题7.6 220

7.7最短路Dij kstra算法 220

7.7.1问题的提出 220

7.7.2 Dij kstra算法 221

习题7.7 221

7.8树 222

7.8.1树的基本概念 222

7.8.2最小生成树Kruskal算法 224

7.8.3二叉树 226

7.8.4最优二叉树哈夫曼算法 229

习题7.8 231

7.9图论在计算机中的应用 232

7.9.1二叉树的遍历算法及表达式表示 232

7.9.2前缀码的设计 233

7.9.3有限状态机的图表示 235

7.10本章小结 236

自测题7 240

第8章 数理逻辑 243

8.1命题演算 243

8.1.1命题与命题联结词 243

8.1.2命题公式 248

8.1.3真值表及其真值计算算法 250

8.1.4命题等值式 252

8.1.5重言式、矛盾式和可满足式 256

8.1.6蕴涵式 257

习题8.1 259

8.2范式 261

8.2.1对偶原理 261

8.2.2范式转换算法 262

8.2.3主范式形成算法 264

习题8.2 272

8.3命题推理 273

8.3.1直接推理法 274

8.3.2间接推理法 275

习题8.3 276

8.4谓词演算 278

8.4.1个体、谓词和量词 278

8.4.2谓词公式和辖域 281

8.4.3谓词公式的解释及逻辑有效式 283

习题8.4 284

8.5谓词等值式和置换规则 286

习题8.5 288

8.6谓词推理 289

8.6.1逻辑有效蕴涵式 289

8.6.2推理定律 289

8.6.3推理实例 291

习题8.6 292

8.7数理逻辑在计算机中的应用 293

8.7.1逻辑推理在人工智能中的应用 293

8.7.2人工智能语言Prolog简介 294

习题8.7 295

8.8本章小结 295

自测题8 298

后记 301

参考文献 302