命题逻辑与证明方法
命题逻辑与证明方法 本章主线：命题与逻辑联结词 → 量词与逻辑等价 → 基本证明方法 → 算法正确性与不变量。 1 命题 能够明确判断真假的陈述句称为命题。 例如： 2+3=52+3=52+3=5 是真命题； 777 是偶数是假命题； “请关闭窗口”不是命题； “这个算法很优秀”通常不是严格命题，因为“优秀”的标准不明确。 命题通常用字母 P,Q,RP,Q,RP,Q,R 表示。 命题只有两
MiQiu
关系
关系 本章主线：二元关系 → 关系的性质与运算 → 等价关系与集合划分 → 偏序关系 → 图与算法中的关系结构。 1 从笛卡尔积到关系 设有两个集合 A,BA,BA,B，它们的笛卡尔积为 A×B={(a,b)∣a∈A, b∈B}A\times B=\{(a,b)\mid a\in A,\ b\in B\}A×B={(a,b)∣a∈A, b∈B}。 笛卡尔积列出了所有可能的有序对。例如，若 A=
离散结构
离散结构 离散结构研究在集合上加入关系、运算或连接方式后形成的具体数学对象。 1 整体主线 图论结构 → 代数运算结构。 本部分建立在 数学语言与证明 之上。 图论结构研究对象之间的连接、路径与可达性； 代数运算结构研究对象如何组合，以及运算满足哪些性质。 2 图论的基本数学结构 图论的基本数学结构 研究： 图、边与顶点； 游走、迹、路径与环； 连通与可达； 树、森林与生成树； 桥
映射
映射 本章主线：关系中的唯一对应 → 映射 → 单射、满射与双射 → 复合与逆映射 → 算法中的状态映射。 1 从关系到映射 设 A,BA,BA,B 是两个集合，关系 R⊆A×BR\subseteq A\times BR⊆A×B 可以把 AAA 中的元素与 BBB 中的元素联系起来。 一般的关系没有限制： 一个元素可以不与任何元素相关； 一个元素可以与多个元素相关。 例如，设 A={1,2
代数运算结构
代数运算结构 本章主线：二元运算 → 结合律、单位元与逆元 → 半群、幺半群与群 → 同态 → 算法中的可合并信息。 1 为什么研究运算结构 许多算法表面上处理的对象不同： 区间和处理数字； 区间最小值处理大小关系； 矩阵快速幂处理矩阵； 函数复合处理映射； 字符串拼接处理字符串。 它们能够使用相似算法，往往不是因为对象相同，而是因为所使用的运算具有相同性质。 因此，应当区分： 运算作用
数论知识体系
数论知识体系 数论研究整数的乘法结构、同余结构与数论函数； 算法竞赛中的数论，则进一步关心这些结构如何被高效计算。 1 数论在数学体系中的位置 数论建立在集合、关系、映射与代数运算结构之上。 其中： 整除关系把正整数组织成偏序结构； 同余关系把整数划分为剩余类； 模乘法群描述可逆剩余类的乘法结构； 数论函数把整数的结构映射为可计算的数值； 狄利克雷卷积在因数分解上定义数论函数之间的乘法； 数
图论的基本数学结构
图论的基本数学结构 本章主线：图与路径 → 连通与可达 → 树与生成树 → 割结构 → DAG、偏序与商结构。 1 图是什么 图用来描述对象之间的联系。 一张图记作 G=(V,E)G=(V,E)G=(V,E)，其中： VVV 是顶点集合； EEE 是边集合。 无向图中的边写作 {u,v}\{u,v\}{u,v}，表示 uuu 与 vvv 之间存在无方向的联系。 有向图中的边写作 (u,v)
整数分解与筛法
整数分解与筛法 整数分解把一个整数还原为若干个素数幂的乘积； 筛法则在一个整数区间内批量找出这些最基本的组成单位。 1 整数的乘法结构 正整数的乘法结构可以沿着以下主线展开： 本章主线：整除 → 质数与合数 → 算术基本定理 → 因数结构 → 单个整数的判定与分解 → 区间内质数的批量筛选。 这些内容是数论函数、积性函数、模数分解和大整数分解的共同基础。 2 整除、因数与倍数 2.1 整