第1章 导论 1
1.0 实例引入 1
1.1 计算机数学的概念 3
1.1.1 数学发展与人类文明演进 4
1.1.2 计算机发展与社会经济创新 5
1.1.3 从数学和计算机发展看科学与工程的关系 8
1.1.4 计算机数学的定义 9
1.1.5 皮亚诺公理与算法 10
1.2 计算机数学的内涵 13
1.2.1 计算机数学的内容 13
1.2.2 计算机数学的特征 13
1.2.3 计算机数学与传统数学的区别 15
1.2.4 从离散数学到计算机数学 16
1.2.5 程序设计竞赛涉及的计算机数学 17
1.3 计算机数学学习的方法论 18
习题1 21
参考文献 22
专业名词列表 23
第2章 数理逻辑 24
2.0 体验逻辑 24
2.1 数理逻辑简介 25
2.2 命题演算系统 25
2.2.1 命题与命题联结词 25
2.2.2 命题公式与真值表 28
2.2.3 波兰表示法及其转换 32
2.2.4 命题公式的等价 34
2.2.5 命题公式的范式 38
2.2.6 命题演算的推理理论 41
2.3 谓词演算系统 46
2.3.1 个体词与谓词 46
2.3.2 量词 48
2.3.3 谓词公式 49
2.3.4 自由变元与约束变元 51
2.3.5 谓词公式的解释与分类 52
2.3.6 谓词公式的等价 53
2.3.7 谓词演算的推理规则 55
习题2 58
参考文献 61
专业名词列表 61
第3章 集合论 64
3.0 实例引入 64
3.1 集合 66
3.1.1 集合的概念 66
3.1.2 集合的运算 69
3.1.3 集合运算的性质 71
3.2 二元关系 73
3.2.1 笛卡儿积 73
3.2.2 二元关系概念 75
3.2.3 二元关系的运算 78
3.2.4 二元关系的性质 82
3.2.5 等价关系 85
3.2.6 半序关系 87
3.3 函数 91
3.3.1 函数的概念 91
3.3.2 集合的基数 93
3.4 集合的应用与推广 97
3.4.1 形式语言与字符编码 97
3.4.2 关系数据模型 99
3.4.3 模糊集和可拓集 100
3.4.4 齐次关系与坐标变换 101
习题3 103
参考文献 106
专业名词列表 107
第4章 组合论 109
4.0 实例引入 109
4.1 基本计数原则 110
4.1.1 加法原则 110
4.1.2 乘法原则 110
4.2 排列组合 111
4.2.1 无重复元的排列组合 112
4.2.2 有重复元的排列组合 113
4.3 鸽洞原理 115
4.4 生成函数与排列组合 116
4.4.1 生成函数 116
4.4.2 组合问题的生成函数 118
4.4.3 排列问题的生成函数 120
4.5 排列组合的生成 121
4.5.1 排列生成算法 121
4.5.2 组合生成算法 123
习题4 124
参考文献 125
专业名词列表 125
第5章 数论 126
5.0 实例引入 126
5.1 整数的因子分解 127
5.2 同余关系 129
5.3 密码学基础 131
5.4 数制 134
5.4.1 基数及其转换 134
5.4.2 格雷码及其递归应用 137
习题5 139
参考文献 140
专业名词列表 141
第6章 图结构 142
6.0 实例引入 142
6.1 图论的概念 145
6.1.1 图的定义 145
6.1.2 图的表示方法 147
6.2 图论中的几个经典问题及其算法 150
6.2.1 最短路径算法 150
6.2.2 Euler环游问题 153
6.2.3 Hamilton圈 156
6.2.4 着色问题 157
6.3 图论的应用 158
6.3.1 流程图 158
6.3.2 环和程序复杂度 162
6.3.3 路径覆盖和白盒动态测试 163
6.3.4 FSM和系统测试 165
习题6 167
参考文献 171
专业名词列表 171
第7章 树结构 173
7.0 实例引入 173
7.1 树的概念 174
7.1.1 自由树 174
7.1.2 有根树 175
7.2 二叉树 176
7.2.1 二叉树的概念 176
7.2.2 二叉树的计算机表示 178
7.2.3 二叉树的遍历 180
7.2.4 前缀编码与Huffman树 182
7.2.5 二叉查找树 186
7.2.6 二叉排序树 195
7.3 生成树 201
7.3.1 生成树及其构造 201
7.3.2 最小生成树 201
习题7 203
参考文献 204
专业名词列表 205
第8章 表结构 206
8.0 实例引入 206
8.1 线性表 207
8.1.1 线性表的计算机表示 208
8.1.2 堆栈 209
8.1.3 队列 210
8.1.4 字符串 212
8.1.5 基于关键字比较的线性查找表 213
8.1.6 基于关键字比较的线性排序表 214
8.2 广义表 219
8.2.1 多维表 219
8.2.2 混合表 223
8.3 索引表 224
8.3.1 分块索引与查找 225
8.3.2 多关键字与重排索引表 225
8.3.3 基于关键字基数的排序 226
8.3.4 Hash表 228
习题8 229
参考文献 230
专业名词列表 231
第9章 计算模型 233
9.0 实例引入 233
9.1 形式文法 234
9.1.1 文法的定义 234
9.1.2 文法的分类 236
9.1.3 正则文法和正则表达式 236
9.1.4 语法树 239
9.2 有限自动机 240
9.2.1 有限自动机的定义 240
9.2.2 有限自动机和正则文法 241
9.3 图灵机 243
习题9 247
参考文献 248
专业名词列表 249