离散数学大全

  |  

摘要: 《离散数学及其应用》

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:潮汐朝夕
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


本书系统地介绍了组合数学的议题,主要包括:逻辑和证明,集合、函数、序列、求和与矩阵,算法,数论和密码学,归纳与递归,计数,离散概率,关系,图,树,布尔代数,计算模型。全书取材广泛,除包括定义、定理的严格陈述外,还配备大量的例题、图表、应用实例和练习。

但注意本书不包括代数系统的内容,这部分可以参考 《离散数学》


基础:逻辑和证明

命题逻辑

  • 命题
  • 条件语句
  • 复合命题的真值表
  • 逻辑运算符的优先级
  • 逻辑运算和比特运算

命题逻辑的应用

  • 语句翻译
  • 系统规范说明
  • 布尔搜索
  • 逻辑谜题
  • 逻辑电路

命题等价式

  • 逻辑等价式
  • 德·摩根律的运用
  • 构造新的逻辑等价式
  • 可满足性
  • 可满足性的应用
  • 可满足性问题求解

谓词和量词

  • 谓词
  • 量词
  • 有限域上的量词
  • 受限域的量词
  • 量词的优先级
  • 变量绑定
  • 涉及量词的逻辑等价式
  • 量化表达式的否定
  • 语句到逻辑表达式的翻译
  • 系统规范说明中量词的使用
  • 选自路易斯·卡罗尔的例子
  • 逻辑程序设计

嵌套量词

  • 理解涉及嵌套量词的语句
  • 量词的顺序
  • 数学语句到嵌套量词语句的翻译
  • 嵌套量词到自然语言的翻译
  • 汉语语句到逻辑表达式的翻译
  • 嵌套量词的否定

推理规则

  • 命题逻辑的有效论证
  • 命题逻辑的推理规则
  • 使用推理规则建立论证
  • 消解律
  • 谬误
  • 量化命题的推理规则
  • 命题和量化命题推理规则的组合使用

证明导论

  • 一些专用术语
  • 理解定理是如何陈述的
  • 证明定理的方法
  • 直接证明法
  • 反证法
  • 归谬证明法
  • 证明中的错误
  • 良好的开端

证明的方法和策略

  • 穷举证明法和分情形证明法
  • 存在性证明
  • 唯一性证明
  • 证明策略
  • 寻找反例
  • 证明策略实践
  • 拼接
  • 开放问题的作用
  • 其他证明方法

基本结构:集合、函数、序列、求和与矩阵

集合

  • 文氏图
  • 子集
  • 集合的大小
  • 幂集
  • 笛卡儿积
  • 使用带量词的集合符号
  • 真值集和量词

集合运算

  • 集合恒等式
  • 扩展的并集和交集
  • 集合的计算机表示
  • 多重集

函数

  • 一对一函数和映上函数
  • 反函数和函数合成
  • 函数的图
  • 一些重要的函数
  • 部分函数

序列与求和

  • 序列
  • 递推关系
  • 特殊的整数序列
  • 求和

集合的基数

  • 可数集合
  • 不可数集合

矩阵

  • 矩阵算术
  • 矩阵的转置和幂
  • 0-1矩阵

算法

算法

  • 搜索算法
  • 排序
  • 字符串匹配
  • 贪婪算法
  • 停机问题

函数的增长

  • 大O记号
  • 一些重要函数的大O估算
  • 函数组合的增长
  • 大Ω与大Θ记号

算法的复杂度

  • 时间复杂度
  • 矩阵乘法的复杂度
  • 算法范型
  • 理解算法的复杂度

数论和密码学

整除性和模算术

  • 除法
  • 除法算法
  • 模算术
  • 模m算术

整数表示和算法

  • 整数表示
  • 整数运算算法
  • 模指数运算

素数和最大公约数

  • 素数
  • 试除法
  • 埃拉托斯特尼筛法
  • 关于素数的猜想和开放问题
  • 最大公约数和最小公倍数
  • 欧几里得算法
  • gcd的线性组合表示

求解同余方程

  • 线性同余方程
  • 中国剩余定理
  • 大整数的计算机算术
  • 费马小定理
  • 伪素数
  • 原根和离散对数

同余的应用

  • 散列函数
  • 伪随机数
  • 校验码

密码学

  • 古典密码学
  • 公钥密码学
  • RSA密码系统
  • RSA加密
  • RSA解密
  • 用RSA作为公钥系统
  • 密码协议
  • 同态加密

归纳与递归

数学归纳法

  • 数学归纳法
  • 为什么数学归纳法是有
  • 选择正确的基础步骤
  • 运用数学归纳法进行证明的原则
  • 数学归纳法的优点与缺点
  • 利用数学归纳法证明的例子
  • 使用数学归纳法时犯的错误

强归纳法与良序性

  • 强归纳法
  • 利用强归纳法证明的例子
  • 计算几何学中使用强归纳法
  • 利用良序性证明

递归定义与结构归纳法

  • 递归地定义函数
  • 递归地定义集合与结构
  • 结构归纳法
  • 广义归纳法

递归算法

  • 证明递归算法的正确性
  • 递归与迭代
  • 归并排序

程序正确性

  • 程序验证 329
  • 推理规则 330
  • 条件语句 330
  • 循环不变量 332

计数

计数的基础

  • 基本的计数原则
  • 比较复杂的计数问题
  • 减法法则(两个集合的容斥原理)
  • 除法法则
  • 树图

鸽巢原理

  • 广义鸽巢原理
  • 鸽巢原理的几个简单应用

排列与组合

  • 排列
  • 组合

二项式系数和恒等式

  • 二项式定理
  • 帕斯卡恒等式和三角形
  • 其他的二项式系数
  • 恒等式

排列与组合的推广

  • 有重复的排列
  • 有重复的组合
  • 具有不可区别物体的集合的排列
  • 把物体放入盒子

生成排列和组合

  • 生成排列
  • 生成组合

离散概率

离散概率引论

  • 有限概率
  • 事件组合的概率
  • 概率的推理

概率论

  • 概率指派
  • 事件的组合
  • 条件概率
  • 独立性
  • 伯努利试验与二项分布
  • 随机变量
  • 生日问题
  • 蒙特卡罗算法
  • 概率方法

贝叶斯定理

  • 贝叶斯定理
  • 贝叶斯垃圾邮件过滤器

期望值和方差

  • 期望值
  • 期望的线性性质
  • 平均情形下的计算复杂度
  • 几何分布
  • 独立随机变量
  • 方差
  • 切比雪夫不等式

高级计数技术

递推关系的应用

  • 用递推关系构造模型
  • 算法与递推关系

求解线性递推关系

  • 求解常系数线性齐次递推关系
  • 求解常系数线性非齐次递推关系

分治算法和递推关系

  • 分治递推关系

生成函数

  • 关于幂级数的有用事实
  • 计数问题与生成函数
  • 使用生成函数求解递推关系
  • 使用生成函数证明恒等式

容斥

  • 容斥原理

容斥原理的应用

  • 容斥原理的另一种形式
  • 埃拉托色尼筛
  • 映上函数的个数
  • 错位排列

关系

关系及其性质

  • 函数作为关系
  • 集合的关系
  • 关系的性质
  • 关系的组合

n元关系及其应用

  • n元关系
  • 数据库和关系
  • n元关系的运算
  • SQL
  • 数据挖掘中的关联规则

关系的表示

  • 用矩阵表示关系
  • 用图表示关系

关系的闭包

  • 不同类型的闭包
  • 有向图中的路径
  • 传递闭包
  • 沃舍尔算法

等价关系

  • 等价关系
  • 等价类
  • 等价类与划分

偏序

  • 字典顺序
  • 哈塞图
  • 极大元与极小元
  • 拓扑排序

  • 图和图模型
  • 图模型

图的术语和几种特殊的图

  • 基本术语 573
  • 一些特殊的简单图 575
  • 二分图 576
  • 二分图和匹配 577
  • 特殊类型图的一些应用 580
  • 从旧图构造新图 582

图的表示和图的同构

  • 图的表示
  • 邻接矩阵
  • 关联矩阵
  • 图的同构
  • 判定两个简单图是否同构

连通性

  • 通路 598
  • 无向图的连通性 600
  • 图是如何连通的 601
  • 有向图的连通性 603
  • 通路与同构 604
  • 计算顶点之间的通路数 605

欧拉通路与哈密顿通路

  • 欧拉通路与欧拉回路
  • 哈密顿通路与哈密顿回路
  • 哈密顿回路的应用

最短通路问题

  • 最短通路算法
  • 旅行商问题

平面图

  • 欧拉公式
  • 库拉图斯基定理

图着色

  • 图着色的应用

树的概述

  • 有根树
  • 树作为模型
  • 树的性质

树的应用

  • 二叉搜索树
  • 决策树
  • 前缀码
  • 博弈树

树的遍历

  • 通用地址系统
  • 遍历算法
  • 中缀、前缀和后缀记法

生成树

  • 深度优先搜索
  • 宽度优先搜索
  • 回溯的应用
  • 有向图中的深度优先搜索

最小生成树

  • 最小生成树算法

布尔代数

布尔函数

  • 布尔表达式和布尔函数
  • 布尔代数恒等式
  • 对偶性
  • 布尔代数的抽象定义

布尔函数的表示

  • 积之和展开式
  • 函数完备性

逻辑门电路

  • 门的组合
  • 电路的例子
  • 加法器

电路的极小化

  • 卡诺图
  • 无须在意的条件
  • 奎因-莫可拉斯基方法

计算模型

语言和文法

  • 短语结构文法
  • 短语结构文法的类型
  • 派生树
  • 巴克斯-诺尔范式

带输出的有限状态机

  • 带输出的有限状态机

不带输出的有限状态机

  • 串的集合
  • 有限状态自动机
  • 有限状态机的语言识别
  • 非确定性的有限状态自动机

语言的识别

  • 克莱因定理
  • 正则集合和正则文法
  • 一个不能由有限状态自动机识别的集合
  • 一些更强大的机器

图灵机

  • 图灵机的定义
  • 用图灵机识别集合
  • 用图灵机计算函数
  • 不同类型的图灵机
  • 丘奇-图灵论题
  • 计算复杂度、可计算性和可判定性

补充内容,参考 《离散数学》

代数系统

运算

半群

子群、正规子群、同态

环、整环、域

域上的多项式


Share