规范形

来自testwiki
跳转到导航 跳转到搜索
多重集为规范形进行算法易位构词游戏测试:以C语言数组形式给出字符串“madam curie”“radium came”。通过排序,将每个字符串窜转为规范形。由于两个字符串排序后完全相同,因此原字符串实为彼此的变形。

数学计算机科学中,数学对象标准形规范形是将该对象作为表达式呈现的标准方式。通常来说,它提供了对象的最简单的表示,并允许以独特的方式识别。“规范(canonical)”与“标准(normal)”的区别因领域而异,大多数时候规范形都规定了对象的唯一表示形式,而标准形则不要求唯一性。[1]

小数表示,自然数的规范形是不以0开头的有限数字序列。更一般地说,对于定义了等价关系的一类对象,规范形包括每类中的特定对象。例如

在计算机科学与计算机代数中,在计算机中有很多方法表示同一个数学对象。这时,规范形是对每个对象都有唯一表示的表示法(典型化是将某种表示转换为规范形的过程。因此,测试两个对象的规范形是否相等,便可轻松地验证它们是否等价。 规范形经常依赖于任意选择(如变量排序),给测试两个对象是否等价的独立计算带来困难。因此,在计算机代数中,标准形是很弱的概念:标准形中,0的表示是唯一的,因此可以通过对两个对象作差、置于标准形中,来检验它们是否相等。

规范形也可以指以自然(规范)方式定义的微分形式

定义

给定对象集合S以及其上的等价关系R ,则指定S中的一些对象为“规范形”,这样所考虑的每个对象都等价于规范形的某个对象。换句话说S中的规范形代表一类等价类。要检验两个对象是否等价,只需检验其规范形是否等价。 因此,规范形提供了分类定理,还为类中的对象提供了代表形式。

形式上,集合S上等价关系R的规范化是一个映射c:SS,对所有ss1s2S

  1. c(s) = c(c(s))   (幂等性);
  2. s1 R s2,当且仅当c(s1) = c(s2)   (决定性);
  3. s R c(s)  (代表性)。

性质3是冗余的:将性质2应用于性质1即可得出。

在实际应用中,能识别规范形往往是有利的。还有一个实际的算法问题需要考虑:如何将S中的给定对象s转换为规范形式s*?规范形一般用于更有效地运算等价类。例如,模算术中,同余类的规范形通常是其中的最小非负整数。类运算可以组合这些代表形,并将结果还原为最小非负余数。 唯一性要求有时会被放宽,允许形式在更精细的等价关系下是唯一的。

规范形可能只是惯例,也可能来自定理。例如,多项式在书写时通常按幂次递减:如x2 + x + 30,而非x + 30 + x2。相对地,矩阵的若尔当标准形来自定理。

示例

大数记号

标准形用于书写极大的数字,其中最知名的是科学计数法[2]

数论

  • 正整数的规范表示
  • 连分数的标准形

线性代数

对象 A等价于B的条件 规范形 注释
复数正规矩阵 A=U*BU酉矩阵U 对角矩阵(重排序) 谱定理
复数矩阵 A=UBV*,酉矩阵U、V 元素为正实数的对角阵(降序) 奇异值分解
代数闭域矩阵 A=P1BP非奇异方阵P 若尔当标准形(块重排序)
代数闭域矩阵 A=P1BP,非奇异方阵P 韦尔规范形(块重排序)
域矩阵 A=P1BP,非奇异方阵P 弗罗贝尼乌斯标准形
主理想域矩阵 A=P1BQ,非奇异方阵P、Q 史密斯标准形 可逆的基本行列变换不影响等价性
整数矩阵 A=UB幺模矩阵U 埃尔米特标准形
整数模n矩阵 豪厄尔标准形
K上的有限维向量空间 A、B作为向量空间同构 Knn为非负整数

代数

对象 A等价于B的条件 标准形
有限生成R-模,R主理想域 A、B作为R-模同构 初等分解(重排序)或不变因子分解

几何

解析几何中:

  • 直线方程:Ax + By = C,而 A2 + B2 = 1(C ≥ 0)
  • 圆方程:(xh)2+(yk)2=r2

方程还有其他书写形式。例如,直线方程可以写作点斜式和斜截式的一次方程

凸多胞形可以表示为标准形:

  • 所有面都是平的;
  • 所有边都与单位球面相切;
  • 多面体的中心店位于原点。[3]

可积系统

所有可微流形都有余切丛,总可以被赋予某种微分形式,称为重言1形式。这种形式使余切丛具有辛流形的结构,并允许流形上的向量场通过欧拉-拉格朗日方程哈密顿力学进行积分,这种可积的微分方程系统称为可积系统

动力系统

动力系统研究与可积系统有所重合;在动力系统研究中,我们也有标准形的概念。

三维几何

三维流形研究中,有第一基本形式第二基本形式第三基本形式

函数分析

对象 A、B等价的条件 标准形
希尔伯特空间 A、B均为有限维希尔伯特空间,则A、B保距同构。 2(I)数列空间(将索引集I换为另一个等索引集的意义上)
有单位(unit)的可交换C*-代数 A、B作为C*-代数同构 豪斯多夫空间上的连续函数代数C(X),与基空间同胚的意义上。

经典逻辑

Template:Main article

集合论

改写系统

改变公式的形式的符号操作称为公式的“改写”(rewriting)。可以研究可对公式进行有效操作的规则集合,以研究公式改写的抽象性质,也就是“改写规则”——抽象改写系统的一个部分。常见问题是,有没有可能将某些通用表达式变为一种单一的、通用的形式,即标准形。若不同的改写序列仍能得到相同的形式,则这种形式就可称为标准形,改写则称为汇合(confluent)。标准形不总可得。

λ演算

  • 若不能进行beta还原,则lambda项就是Beta范式λ演算是抽象改写系统的一种特殊情况。例如,在无类型的lambda演算中,(λx.(xx)λx.(xx))项没有标准形。在有类型的lambda演算中,每个形式良好的项都可改写为标准形。

图论

Template:Main article 图论中,图规范化是找到给定图G的规范形的过程。图的规范形是与G图同构有标号图Canon(G),这样,与G同构的图都具有与G相同的规范图,也就实现了图同构的判断。

计算 (计算机科学)

计算中,将数据还原为任一种规范形通常称为“数据规范化”(data normalization)。

例如,数据库规范化是对关系数据库字段数据库表进行调整,以尽量减少数据冗余与依赖的过程。[4]软件安全领域,常见的漏洞是未经检查的恶意输入(参见代码注入),解决方法是进行适当的数据确认。在进行输入验证之前,通常会通过消除编码(如HTML字符编码)和将其化为单一通用字符编码的方式进行正规化处理。 其他形式的数据(通常与信号处理,包括音频图像,以及机器学习)也可以进行规范化处理,以将数值范围框定得有限。

内容管理中适用单一信源(SSOT)的概念,与数据库规范化软件开发相仿。功能强大的内容管理系统可以提供获取单一信源的合理方法,例如嵌入

另见

注释

  1. 有时“规范”与“标准”可以互换,如若尔当规范形与若尔当标准形(见MathWorks上的若尔当标准形 Template:Wayback)。
  2. Template:Cite web
  3. Template:Citation
  4. Template:Cite web

参考文献