离散数学:模型与应用电子书

前言

符号对照表

第1章 二值模型

1.1 命题逻辑

1.1.1 命题

1.1.2 逻辑运算符的优先级

1.1.3 逻辑运算与位运算

1.1.4 习题

1.2 命题等价式

1.2.1 永真式与矛盾式

1.2.2 逻辑等价证明

1.2.3 命题可满足性建模与求解

1.2.4 习题

1.3 谓词与量词

1.3.1 谓词

1.3.2 量词

1.3.3 约束论域的量词

1.3.4 语句到逻辑表达式的翻译

1.3.5 逻辑程序设计

1.3.6 霍尔逻辑

1.3.7 习题

1.4 嵌套量词

1.4.1 嵌套量词到自然语言的翻译

1.4.2 涉及嵌套量词的语句到逻辑表达式的翻译

1.4.3 嵌套量词逻辑表达式的否定

1.4.4 量词的顺序

1.4.5 习题

1.5 推理规则

1.5.1 命题逻辑的推理规则

1.5.2 使用推理规则建立有效论证

1.5.3 量词陈述的推理规则

1.5.4 定理的证明方法

1.5.5 习题

1.6 布尔代数

1.6.1 布尔函数

1.6.2 对偶性

1.6.3 布尔代数的抽象定义

1.6.4 布尔函数的表示

1.6.5 函数完备性、可逆布尔函数和量子逻辑

1.6.6 习题

1.7 本章应用题

1.8 数学建模与应用

1.8.1 软件产品线配置

1.8.2 软件测试

1.8.3 视频烟雾检测

1.8.4 视频人物蒙面检测

1.8.5 视频监控的安全带检测

1.8.6 逻辑门电路设计

1.8.7 知识推理

1.8.8 自动定理证明

1.8.9 智能合约

1.8.10 传染病防控

第2章 集合模型

2.1 集合与集合运算

2.1.1 集合简介

2.1.2 幂集合

2.1.3 基本集合运算

2.1.4 习题

2.2 函数的集合表示及其性质

2.2.1 函数简介

2.2.2 函数类型与运算

2.2.3 取整函数

2.2.4 函数的阶

2.2.5 时间复杂度

2.2.6 算法时间复杂度

2.2.7 习题

2.3 本章应用题

2.4 数学建模与应用

2.4.1 数字图像的生成与表示

2.4.2 点云的表示与配准

2.4.3 哈希表

2.4.4 有限状态机

2.4.5 公钥加密系统

2.4.6 病毒检测的真阳性率

第3章 关系模型

3.1 关系及其性质

3.1.1 集合上的函数与关系

3.1.2 关系的性质

3.1.3 关系的复合

3.1.4 习题

3.2 n元关系及其应用

3.2.1 n元关系与数据库

3.2.2 n元关系的运算

3.2.3 SQL

3.2.4 习题

3.3 关系的表示

3.3.1 用矩阵表示关系

3.3.2 用有向图表示关系

3.3.3 关系的布尔运算

3.3.4 习题

3.4 关系的闭包

3.4.1 闭包

3.4.2 传递闭包的计算

3.4.3 Warshall算法

3.4.4 习题

3.5 等价关系

3.5.1 等价关系的定义

3.5.2 等价类

3.5.3 等价关系与划分

3.5.4 习题

3.6 偏序关系

3.6.1 偏序关系介绍

3.6.2 词典序和哈塞图

3.6.3 极大元与极小元

3.6.4 格与拓扑排序

3.6.5 习题

3.7 本章应用题

3.8 数学建模与应用

3.8.1 关系在数据库中的应用——关系数据库

3.8.2 关系在疫情防控中的应用——隔离管控

3.8.3 关系在销售推荐中的应用——推荐系统

3.8.4 关系在软件测试中的应用——等价类划分

3.8.5 关系在优化问题中的应用——调度问题

3.8.6 关系在静态分析中的应用——数据流分析理论

第4章 图模型

4.1 图模型的介绍

4.1.1 关于图模型

4.1.2 图模型的定义

4.1.3 图模型的案例

4.1.4 习题

4.2 图的术语

4.2.1 基本术语

4.2.2 特殊的简单图

4.2.3 二部图

4.2.4 二部图及其匹配

4.2.5 特殊类型图的应用

4.2.6 习题

4.3 图的表示及图的同构

4.3.1 图的表示

4.3.2 邻接矩阵

4.3.3 关联矩阵

4.3.4 图的同构

4.3.5 简单图同构的判断

4.3.6 习题

4.4 图的连通性

4.4.1 通路

4.4.2 无向图的连通性

4.4.3 图是如何连通的

4.4.4 有向图的连通性

4.4.5 通路与同构

4.4.6 图顶点之间通路数的计算问题

4.4.7 习题

4.5 欧拉路与哈密顿路

4.5.1 欧拉通路与欧拉回路

4.5.2 哈密顿通路与哈密顿回路

4.5.3 习题

4.6 最短通路

4.6.1 最短通路算法

4.6.2 最小哈密顿回路问题

4.6.3 习题

4.7 平面图

4.7.1 欧拉公式

4.7.2 库拉图斯基定理

4.7.3 习题

4.8 图着色

4.8.1 图着色问题的介绍

4.8.2 简单图着色

4.8.3 图着色的应用

4.8.4 习题

4.9 本章应用题

4.10 数学建模与应用

4.10.1 CPU多核连接拓扑

4.10.2 计算机网络路由算法

4.10.3 物流运输——双层次车辆路径问题

4.10.4 电路板布线问题

4.10.5 期末考试安排

4.10.6 频率分配

4.10.7 变址寄存器

4.10.8 高效并行计算任务分配

第5章 树模型

5.1 关于树模型

5.1.1 树的定义

5.1.2 树模型的应用举例

5.1.3 树的性质

5.1.4 习题

5.2 树的应用

5.2.1 二分搜索树

5.2.2 决策树

5.2.3 博弈树

5.2.4 习题

5.3 树的遍历

5.3.1 有序有根树

5.3.2 树的遍历算法

5.3.3 树的中缀、前缀和后缀表示法

5.3.4 孩子兄弟法

5.3.5 习题

5.4 生成树

5.4.1 生成树的定义

5.4.2 构建生成树的深度优先搜索方法

5.4.3 构建生成树的广度优先搜索方法

5.4.4 生成树中回溯法的应用

5.4.5 习题

5.5 最小生成树

5.5.1 最小生成树的定义

5.5.2 Prim算法

5.5.3 Kruskal算法

5.5.4 最小生成树的应用

5.5.5 习题

5.6 本章应用题

5.7 数学建模与应用

5.7.1 树在疫情防控中的作用——病毒变异演化树

5.7.2 树在机器学习中的应用——决策树

5.7.3 树的遍历与编码应用——区块链智能合约脚本

5.7.4 树在数据库索引中的应用——使用B+树实现高效搜索

5.7.5 树在动作游戏AI中的应用——行为树

5.7.6 树在编译器中的应用——语法分析树

5.7.7 最小生成树在计算机网络中的应用——路由选择

5.7.8 博弈树在围棋AI中的应用——蒙特卡罗树

5.7.9 树在数据压缩中的应用——哈夫曼树

5.7.10 树在网页设计中的应用——HTML网页的DOM树

第6章 有限状态机模型

6.1 关于有限状态机模型

6.1.1 有限状态机的组成

6.1.2 有限状态机的定义

6.1.3 有限状态机的案例

6.1.4 习题

6.2 图灵机

6.2.1 图灵机的原理

6.2.2 图灵机的组成

6.2.3 图灵机的抽象模型

6.2.4 图灵机的问题举例

6.2.5 习题

6.3 图灵命题

6.3.1 图灵命题及其意义

6.3.2 不可解问题

6.3.3 图灵命题的影响

6.3.4 习题

6.4 NP、NPC与NP-hard

6.4.1 归约与问题求解难度

6.4.2 NP问题

6.4.3 NPC与NP-hard问题

6.4.4 P与NP问题的未解之谜

6.4.5 习题

6.5 本章应用题

6.6 数学建模与应用

6.6.1 有限状态机在自动售货机中的应用

6.6.2 有限状态机在文本处理中的应用

6.6.3 图灵机在算法分析中的应用

6.6.4 图灵机在不可解问题中的应用

6.6.5 图灵命题在停机问题中的应用

6.6.6 NP问题的数学建模与应用——最大流问题

6.6.7 NP完全问题的数学建模与应用——最大团问题

6.6.8 NP-hard问题的数学建模与应用——旅行商问题

参考文献