基本概念
本章节将简要介绍抽象代数的相关知识。现阶段算法竞赛的主要内容并不直接考察抽象代数的知识,但是在算法的描述或是问题的题解中常常会牵涉一些抽象函数的基本概念,这使得掌握了基础抽象代数概念的读者能够更快速理解一些算法。因此,这部分内容并不是任何选手的必修知识,而仅供那些感兴趣或者可能从中受益的读者参考使用。同时,本章节将避免过全过深的介绍抽象代数的知识1,而会集中在基础概念以及与 OI 其他部分知识联系最为紧密的部分。想系统学习抽象代数知识的读者,应当参考专业的抽象代数教科书学习。
为了更好帮助读者理解阅读本部分内容可能的收获,列举一些算法竞赛中可能牵涉到抽象代数知识的例子:
- 数论和多项式的很多定理是抽象代数中结论的特例;
- 数据结构中,线段树 等结构可以维护幺半群的信息,而很多 DP 问题的递推关系可以抽象成这样的幺半群结构;
- 组合数学中,Pólya 计数原理 的严格表述和证明需要用到群论的相关概念。
基于此,本章节将着重介绍无法跳过的基础知识和与这些应用直接相关的部分。作为开始,本文介绍群、环、域的基本概念。
群
群的定义如下。
群
设
- 结合律(associative property):对于所有
,成立 ; - 有单位元:存在
,使得对于任意 ,都成立 。这里, 称为 的 单位元(identity element),也称幺元; - 存在逆元:对于所有
,都存在相应的 使得 。这里, 称为 的 逆元(inverse element)。
关于定义中的封闭性条件
这里的二元运算就隐含了所谓的封闭性条件,即对于任何
群的基本性质
对于群
- 对于任何有限长的列
,乘积 的运算结果与加括号的方式无关; - 单位元
总是唯一的; - 对于任何元素
,它的逆 也是唯一的; - 消去律(cancellation law):对于
,如果 或 ,那么有 。
群相当常见。通俗地说,所有不损失结构的变换都自动构成群。以常见的几种类型的群为例。
群的例子
- 对称群(symmetric group):集合
上的所有 置换,即自 到 自身的双射,就在映射的复合下构成群 。单位元是恒等变换,逆元是逆映射(双射必然存在逆映射)。如果集合 有限,大小为 ,也常记作 ,称作 次对称群。 - 空间对称群(symmetry group):对于一个几何图形,能够使其与自身重合的变换全体也在映射的复合下构成群。这描述了该几何图形的空间对称性。具体例子可以参考 常见空间对称群。
- 整数的加法群:整数集
在加法 运算下构成群 。单位元是 ,逆元是相反数。 - 整数模
乘法群(multiplicative group of integers modulo ):对于一个模数 ,所有与 互质的整数对应的 同余类,在乘法运算下构成群 。单位元是 ,逆元就是模 的 乘法逆元(对应的同余类),其存在性由 裴蜀定理 保证。具体结构分析参考 整数模 乘法群。 - 一般线性群(general linear group):数域
上的 维的全体可逆方阵在乘法运算下构成群 。单位元是单位矩阵,逆元是逆矩阵。
要更好地理解群的定义,不妨对比着看几个不属于群的例子。
不是群的例子
- 所有
到自身的映射(不一定是双射),并不构成群。因为那些不是双射的映射不存在逆元。 - 整数在乘法下并不构成群,因为
在整数范围内没有乘法逆元。 - 正整数在加法下也不构成群,因为正整数没有加法单位元。
- 模
的所有非零同余类在乘法意义下往往不构成群。比如说 中, 不属于这个集合,这意味着乘法都不是这个集合上良定义的二元运算(或者说,它不满足封闭性)。
有时,也需要讨论这些更不完善的结构的性质。因此,可以定义如下概念,它们比群更宽泛。
半群
对于非空集合
幺半群
对于半群
幺半群和半群的例子
上面的例子中,
最后,很多熟悉的群上的运算除了满足结合律外,还满足交换律。这类群的结构相对简单,它们称作 Abel 群,也称作交换群。
Abel 群
对于群
Abel 群和非 Abel 群的例子
- 整数加法群
就是一个 Abel 群。 - 当
时,对称群 并不是 Abel 群。
这些就是群论相关的基本定义。群论的更多内容,可以参考 群论 或相关书籍。
环
环的定义如下。
环
对于非空集合
构成 Abel 群,其单位元记作 ,元素 在 下的逆元记作 。 构成半群,即 满足结合律。- 分配律(distributive property):对于所有
,成立 和 。
为表述方便,这两个二元运算
关于定义中是否要求乘法单位元
在有的定义中,环必须存在乘法单位元;相对地,不存在乘法单位元的则被称为 伪环(rng 或 pseudo-ring)。遇到的时候需根据上下文加以判断。维基百科采用的就是这种定义2。
环的加法结构相当简单,但是乘法结构十分原始。因而如果类比群,在乘法上做更多要求,可以得到如下相关定义。
幺环
对于环
除环
对于非零幺环
交换环
对于环
这里除环的定义中有趣的一点是,它将
这里的启示是,理解一般的环的乘法结构时,要去除加法单位元的影响,考察
零因子
对于环
可逆元(单位)
对于环
「单位」与「单位元」
请不要混淆这两个概念。为避免混淆,抽象代数部分将使用「可逆元」的名称代替「单位」。
零因子不可能是可逆元,可逆元不可能是零因子。但是,一个非零元素可以既不是零因子,也不是可逆元。
如果一个环没有零因子,就说明所有非零元素的集合在乘法运算下封闭,即
整环
对于非零环
虽然整环中的元素不一定存在逆元,但是没有零因子这一特性已经足够在整环上建立消去律。
整环的消去律
设整环
对于一般的幺环,如果只考虑它的全体可逆元,那么同样可以得到群结构。这称为环的乘法群或是单位群。
乘法群(单位群)
对于幺环
最简单的一些环的例子如下。
环的例子
-
零环(zero ring):集合
在通常意义的加法 和乘法 下构成环,称为零环。它是唯一的只有一个元素的环,也是唯一的加法单位元和乘法单位元相等的环。 -
整数环:整数集
和其上通常定义的加法 和乘法 构成了环 。实际上,这是一个整环,但是它不是除环。 -
多项式环:对于一个环
,可以在上面定义 多项式环 。如果 是整环,则该多项式环必然是整环。 -
四元数(quaternion):类比复数,可以考虑集合
,并且定义其上的加法和乘法,这里, 的乘法运算满足那么可以验证,
构成环,而且,它是一个非交换的除环。 -
整数集的子集
,在通常意义的加法和乘法下构成环,它是交换环,没有零因子,但是并不含幺。 -
整数模
同余类 在同余类的加法和乘法运算下构成环,它是交换环,含幺(即 )。这样的环含有零因子,当且仅当 是合数。所以,当 是素数时,环 是整环;而且,此时它也是除环,所以它实际构成为了一个域。它的乘法群 就是整数模 乘法群。 -
矩阵环:环
上的全体 维方阵在矩阵的加法和乘法下构成一个环 。一般地,这个环有零因子,且不是交换环。 -
对于一个集合
的全体子集 ,如果定义集合的对称差 和交 分别为其加法和乘法运算,则 构成环。一般地,这个环含幺,有零因子,且是交换环。
当然,对于环的结构的讨论远不止这些,要了解更多内容,可以参考 环论 或相关书籍。
域
域是一个比环性质更强的代数结构。具体地,域是交换除环。当然也可以写出它完整的定义。
域
对于非空集合
构成 Abel 群,其单位元记作 ,元素 在 下的逆元记作 。 构成 Abel 群,其单位元记作 ,元素 在 下的逆元记作 。
换句话说,域是对加、减、乘、除四则运算都封闭的代数结构。
常见的域的例子如下。
域的例子
-
数域:有理数集
,实数集 和复数集 在通常意义的加法和乘法下都构成域。 -
有限域(finite field):以质数
为模的整数同余类的集合 在同余类的加法和乘法下构成域。当然,除此之外还有其他的有限域,它们的结构由其大小唯一确定,且大小必然是质数幂的形式。 -
分式域(fraction field):设
为整环,可以考虑形如 的元素构成的集合 。严格地说,在集合 上定义等价关系: 当且仅当 。那么,集合 就是这一关系下的等价类构成的集合 ,其中, 所在等价类就记作 。如果定义它上面的运算为则
构成域,称为 的分式域。例如,有理数域 就是整数环 的分式域。 -
二次域(quadratic field):它是在有理数域
中添加了 而扩张成的,这里 且没有平方因子。相关内容可以参考 二次域。
域相较于环,拥有着非常简单的加法和乘法结构。所以,域本身的结构往往很简单。这使得域的研究和环的研究大不相同,通常会转而研究域的扩张,以及相应的 Galois 理论。在算法竞赛中,有时会需要在有理数域或者有限域的扩域上进行计算。域论的相关内容,可以参考域论或相关书籍。
应用
最后,以下面的题目为例,说明抽象的代数对象是怎样辅助分析具体的问题的。
【模板】"动态 DP"& 动态树分治(加强版)
给定大小为
思路分析
这道题是动态 DP 模板,一种复杂度正确的代码实现需要用到 全局平衡二叉树,具体样例代码也在对应页面。这里仅仅结合该题情景,分析建模的过程。
为了突出重点,这里暂不考虑全局平衡二叉树对于树形结构的处理,转而考虑链上的最大带权独立集的 DP 问题。顺次考虑链
它的初值为
这是一连串
但是,这样的含参变换
基于热带半环
有了这些记号,可以将上述递推关系看作是热带半环上的线性变换,并用矩阵语言写作
由此,只要用线段树维护这一热带半环上的矩阵的乘积就可以回答多次修改的链上的动态 DP 问题。
现在回到该问题的树上版本。对于树上的节点
首先,通过树链剖分将问题转化为链上版本。设
这里,
总结了轻子节点的贡献。根据上文描述,这些变换都可以写作热带半环上的矩阵形式,所以,整个问题也就可以在树剖后的线段树上维护。但是,直接用树剖加线段树的单次修改是
这里提到的热带半环以及上面的矩阵运算其实并不罕见。如果将上文中的
参考资料与注释
- Dummitt, D.S. and Foote, R.M. (2004) Abstract Algebra. 3rd Edition, John Wiley & Sons, Inc.
- Tropical semiring - Wikipedia
-
因为 OI Wiki 不是百科全书。 ↩
-
该式的推导即
,这里,第一个等号和第二个等号是加法单位元的定义,第三个等号是分配律,最后的蕴涵关系是加法的消去律。另一侧的乘法类似。 ↩ -
半环(semiring)是在幺环的定义中放松了加法运算一定存在逆元的要求,即加法结构是交换幺半群、乘法结构是幺半群的代数结构。更多信息参见 Wikipedia。 ↩
本页面最近更新:2024/11/20 19:32:10,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:c-forrest, Tiphereth-A, billchenchina, Enter-tainer, Great-designer, iamtwz, ImpleLee, isdanni, jifbt, Menci, ouuan, warzone-oier, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用