BombLab

血淋淋的教训啊 关bash的时候一起关了 直接没保存 全部没了 😫

• 离散有趣知识点

  离散马上要结课了，里面很多还是很有趣的，这里就零散记载一些有趣或者是有用的知识点

• 析取是或者，合取是与。蕴含命题就是条件语句。逆否等价于原来的条件语句。 p仅当q等价于p->q。也就是等价于如果p则q 将命题用于语句翻译可以简化原理。常见的等价式子以及德摩根定律。

• 合取范式，析取范式，可满足问题，数独。极大项，极小项。极大项与极小项的关系就是取反。注意规定的真值不同，极小项是合取，使式子为真，极大项是析取，使得式子为假 主析取范式，主合取范式就是每一项是极大（小）项 求主析取范式 主析取范式和住合取范式下标是互补的

• 谓词就是形容词 函数 量词就是全称存在 唯一性量词

• 量词的否定 嵌套量词的否定就是移动否定就可以了连续移动 条件语句和量词组合 不能分发

• 归谬法似乎是将需要证明的结论的反命题作为前提引入，然后根据所有前提得到一个a^~a 的情况

• 而反证法 是这样 我们要证明 p -> q ,那么我们可以证明其等价的逆否命题， ~q -> ~p 这样来得到原命题成立

• 归谬证明法 就是通过 得到p -> (r^r) 这样的式子为真 然后得到 p 为真，一般就是一个命题 p 而不是条件语句 条件语句的证明需要假设p,q 然后得到 ~p ，p; q,q 两组矛盾式得到其中一组即可

• 直接证明 反正法 归谬证明

• 鸽巢原理 鸽巢原理注意实际应用 找到什么是盒子 什么是物品

• 排列和组合

• 环排列需要除以环中的元素数量

• 很多组合恒等式可以通过建模，运用一种组合场景来进行证明

• 范德蒙德恒等式 挺有用的 也挺好理解 变形

• 重复排列的问题 就是平方 组合就稍微复杂

• 递推关系式 求解 就是一个特解组合上一个伴随解

• 递推关系的寻找 本事是寻找当前问题能不能由子问题或者说是先前状态转换而来。

• 目前我的理解中生成函数的使用图景并不是很多 目前有一个就是求解计数问题。 生成函数还可以求解递推关系

• 容斥原理

• 容斥原理 公式里面的加减是交替的 并且肯定显然从 加法开始

• 容斥原理配合组合数来使用

• 容斥原理求解映上函数 这个其实可以单独抽象成一个标准模型 成为许多问题的解决的原理 而且这种模型如果直接求解很容易出现问题 重复求解

• 限制条件可以考虑求全部情况 然后减去互斥的情况

• 模运算 有同余恒等式 满足加或者乘法的运算律

• 求模运算得到的结果始终是正值 计算被模的数是负数

• 模指数运算 二进制转换指数 然后每算一项都模一次

• gcd 欧几里得算法 裴树算法可以用来证明一些等式

• ab mod m=amod m b mod m

• 求模的逆 运用欧几里得算法 就是求贝祖系数

• 求解线性同余式的方法就是运用欧几里得算法求出逆 而逆其实就是求解 贝祖系数 对了还有一个前提就是 a 与 m要满足互素 但是即使不互素 满足一定条件就可以求解

• 中国剩余定理 求解线性同余方程组的一种方法 原理同上 然后就是类似的一种叫做反向替代的方法

• 费马小定理 用来求解整数模指数运算

• 原根和离散对数 是一些密码学的基础

• 费马小定理的推广 欧拉函数和欧拉定理 勤奋的欧拉哈哈哈哈哈

• RSA 的原理 凯撒加密加三模26移位密码 移位数k就是密钥 仿射密码求解的关键就是求同余方程