离散数学讨论课(群环格域布尔代数)

离散讨论课（常见群、环、域、格和布尔代数在计算机中的应用）群论半群单元半群群的基本定义交换群有限群循环群半群：设有一个代数系统(S,。)其中“。”是二元运算，它满足结合律，则称该代数系统为半群，对S内任意元素a，b，c有(a。b)。c=a。(b。c)如果半群还满足交换律，则称其为可换半群。单元半群：设有一个代数系统(S,。)其中“。”是二元运算，它满足结合律，并且存在单位元素，则此代数系统叫做单元半群。即对S内任意元素a，b，c有(a。b)。c=a。(b。c)且存在1∈S有1.a=a。1=a。如果单元半群还满足交换律，则称其为可换单元半群。群论：（1）、满足结合律。

（2）、存在单位元素。

（3）、存在逆元素。则称该代数系统为群。可换群也叫阿贝尔群。有限群：群的元素个数有限，则称为有限群，反之元素个数无限，则称为无限群。循环群：若群（G，。）中的每一个元素都是它的某一固定元素a的幂，则称（G，。）为由a生成的循环群，a称作（G，。）的生成元素。剩余类加群：（Zm，+m）是一个群，周期为m的循环群，[0]为其单位元素，[i]+[0]=[i]，[i]m=[0]=１。整数加群：（Ｚ，+）是一个周期为无限的循环群。设有一个由ａ生成的循环群（Ｇ，。），则有：

（１）、若ａ周期为无限，则（Ｇ，。）与（Ｚ，+）同构。

（２）、若ａ周期为ｍ，则（Ｇ，。）与（Ｚｍ，+ｍ）同构。群论在计算机领域的应用：

（１）、组合群论在密码学中的应用

（２）、用群论的基础知识理解信号处理中的一些基本概念（如：时域和频域信号空间的群同构关系）

（３）、椭圆曲线密码的应用等组合群论在密码学中的应用用群论的基础知识理解信号处理中的一些基本概念(如：时域和频域信号空间的群同构关系)椭圆曲线密码的应用椭圆曲线密码的应用无线网络操作模式由3部分组成:①移动用户。能从一个代理范围移动到另一个代理范围;②地点固定的代理。它如同一个调停机构,协调移动用户和服务器之间的通信服务;③服务器。当移动用户从一个地区到另一个地区时,它能选择一个合适的代理,实现与服务器和其它移动用户之间的通信。为了保证用户的合法接入和信息的安全传输,一般需要做到如下5点：【1】访问控制。确保接入用户合法。此过程可以通过移动用户的MAC地址和用户的相关信息来实现。【2】身份认证。确保对方为其所声称的用户及数据的完整性,通过数字签名技术实现。【3】不可否认性。确保其发出的信息事后无法抵赖,通过数字签名实现。【4】数据完整性。防止信息被截获后数据被更改重新发送,通过消息认证码(MAC)和数字签名来实现。【5】保密性。信息在传输中即使被截获,因截获者无法破解而毫无意义。通过数据的加密来实现。密码应用中常使用的两类椭圆曲线为定义在有限域GF(p)上的素曲线和在有限域GF(2n)上的二元曲线。素曲线计算不需二元曲线所要求的位混淆运算,对软件应用而言,最好使用素曲线;而对硬件应用而言,则最好使用二元曲线

,它可用很少的门电路来得到快速且功能强大的密码体制。椭圆曲线的加密和解密在SEC1的椭圆曲线密码标准(草案)中规定,一个椭圆曲线密码由下面的6元组所描述:T=<p,a,b,G,n,h>式中:p为大于3的素数,它确定了有限域GF(p);a和b确定了椭圆曲线;G为循环子群E1的生成元;n为素数且为生成元G的阶,G和n确定了循环子群E1;h为余因子,有h=|E1|/n,h将交换群E和循环子群联系起来。用户的私钥定义为一个随机数dd∈{0,1,2,⋯,n-1}用户的公开密钥定义为Q点： Q=dG设要加密的明文数据为M,将M划分为一些较小的数据块,M=[m1,m2,⋯,mt]。式中:0≤mi<n。用户A将数据mi

加密发送给B,

加密过程如下：【1】用户A查公钥库PKDB,查到用户B的公开密钥QB。【2】用户A选择一个随机数dA

,且dA

∈{0,1,2,⋯,n-1}。【3】用户A计算点X1:(x1,y1)=dAG。【4】用户A计算点X2:(x2,y2)=dAQB,如果分量x2=0,则转【2】。【5】用户A计算C=mi

x2modn。

【6】用户A发送加密数据(X1

,C)给用户B。解密过程：【1】B用自己的私钥dB

求出点X2:dBX1=dB(dG)=dA(dBG)=dAQB=X2:(x2,y2)【2】对C解密,得到明文数据mi=Cx2-1modn。与此类似,可以构造其他椭圆曲线密码。环论和格论环的基本定义整环域格的基本定义分配格有界格补格布尔代数环的定义：设有代数系统（Ｒ，+，。），若满足以下条件：（１）、（Ｒ，+）为可换群；（即满足交换律、结合律、存在零元、负元）（２）、（Ｒ，。）为半群；（即满足结合律）（３）、运算。对+满足分配律，即对任意ａ，ｂ，ｃ∈Ｒ，存在ａ。（ｂ+ｃ）＝ａ。ｂ+ａ。ｃ（ｂ+ｃ）。ａ＝ｂ。ａ+ｃ。ａ整环：

（Ｒ，+，。）为环，它有单位元素且是可换环，无零因子，则称（Ｒ，+，。）是一个整环。域：设环（Ｒ，+，。）满足下列条件：（1）、R至少有两个元素（2）、（R，。）有单位元素（3）、（R，。）是可换的（4）、除零元外，其余元素均存在逆元素（a∈R的逆元可记作a-1）环论在计算机领域的应用：

（１）、广义圆环论在可持续发展中的应用

（２）、环论在线性代数中的一些应用

（３）、一个基于广义圆环论的系统管理数字化模型广义圆环论在可持续发展中的应用【摘要】从世界经济全球化、入关和西部大开发出发,以辩证法为指导,数学为工具,用泛系方法研究可持续发展。提出广义圆环论,建立数学模型,给出四种基本类型。以绿化植树造林工程为例。说明它在规划、预决策、管理方面的应用环论在线性代数中的一些应用

【摘要】：把经典环论中的一些重要结论应用到线性代数中矩阵的研究,通过幂等矩阵和可逆矩阵给出方块矩阵新的分解,并讨论一般矩阵的相关性质.一个基于广义圆环论的系统管理数字化模型【摘要】：从一般系统观点出发,利用以闭环系统和圆环论为基础的广义圆环论构建了一个分布式网络考试管理系统模型———中小学教师现代教育技术培训考试信息处理系统一个基于广义圆环论的系统管理数字化模型域在计算机领域的应用：

（１）、近冰梅——类域论

（２）、二次域理想类数生成元的求解及计算机实现

（３）、基于半邻域法的自适应图像边缘提取方法近冰梅——类域论【摘要】：正类域论(ClassFieldTheory)是数学诸理论中,体系最完美的一种——《数学百科全书》如是说。她是现代数论的一门极重要理论,现在已渗透应用到各分枝,几乎无处不涉及。此理论由希尔波特(Hilbert)在1900年左右猜测出,主要由福特汪格勒(Furtwangler),高木贞治(Takagi),阿廷(Artin)至1927年给出证明。但象“类域构作”这样的世纪性大问题,研究还远无尽头,是现代最激烈前沿之一。类域论理论系统深邃,定理异常丰富,初学者短期内不易掌握。二次域理想类数生成元的求解及计算机实现

【摘要】二次域上的理想类数是有限的,文章利用理想类、类群的相关性质,通过计算机编程,求解出二次域Z(D)的类数及理想的代表。基于半邻域法的自适应图像边缘提取方法

【摘要】：图像边缘对图像识别和计算机分析十分重要,至今已经提出了大量的各种类型边缘提取算法.该文在半邻域法的基础上提出了一种基于自适应阈值选择的图像边缘提取算法,在判断某一像素点是否在边缘上时,以该像素点为中心,选取3×3的区域为研究对象,求出该区域的最大、最小、均值像素值及标准差,在选用标准差为其阈值的同时,还考虑人的视觉对于灰度分辨能力的限制.最后,对多幅灰色图像进行了边缘提取,结果证实了该文方法的有效性.半邻域法采用半邻域法检测某一像素点是否在边缘上,是对其周围相邻的8个像素点进行分析,把它们划分为两组,按照顺时针方向,以连续3个像素点为一组,其余的5个像素点为第二组.这样就有8种情况,如图1所示(＊表示被检测像素点,⊕表示第一组像素点,⊙表示第二组像素点).令N为中心点＊的8邻点集合,N为N集的灰度均值,M3

为N中3个连续邻点的集合,M3

为M3集的灰度均值,M5

为N中5个连续邻点的集合,M5

为M5

集的灰度均值.f(i,j)表示第(i,j)个像素点的灰度值,T表示所给的阈值.具体的实现步骤为:(1)首先在这8种情况之中,选取一组,使得M5

-M3

的值最大,这是边界最可能出现的一种组合;(2)选取一个阈值T,按照下面公式判断:f(i,j)=

N,|M5

-M3

|max<T,边界不明显；（1）

M5

,|M5

-M3

|max≥T,边界明显；（2）

另外,在文献[7]中给出了一种简便的算法,先对周围的8像素点的像素值进行大小排序,将像素值大的5个组成M5

集,较小的3个组成M3

集,求出这两组的均值,再用均值差和给定的阈值T作比较,如果大于T,则判为边缘上的点,反之不是边缘点.半邻域算法虽能够保护边界,但提取的好坏跟给定的T值相关很大,所以受到一定的限制.本文算法本文算法是在半邻域的基础上,采用一种自适应的阈值选择法,选用3×3的区域为研究对象,计算出其最大、最小的像素值及标准差,选择标准差为阈值T的同时,还考虑人眼对灰度分辩能力的限制.这样既克服了半邻域法选择阈值T的困难,又可以避免一些虚假边缘的检测,从而能有效地提取图像的边缘.算法见pdf文件格论：L为非空集合，+和。是L上的两个二院运算，如果他们满足交换律、结合律、吸收律，则代数系统（L,+,。）为格，也称作代数格。

交换律：a+b=b+a，a。b=b。a

结合律：(a+b)+c=a+(b+c)，(a。b)。c=a。(b。c)

吸收律：a+(a。b)=a，a。(a+b)=a分配格：如果格（L，+，。）满足分配律，即对任意a,b,c,∈L，有：

a+(b。c)=(a+b)。(a+c) a。(b+c)=(a+b)。(a+c)则称（L，+，。）是分配格。有界格：设格（L，+，。）中的+有单位元素1及。有单位元素0，即对a∈L有a+1=a，a。0=a，则称该格为有界格格论在计算机领域的应用：（１）、基于格论的哈希函数在数据查询认证中的

应用方案（２）、基于格论的GNSS模糊度解算（３）、基于格论和TRIZ技术进化理论的理想化

水平表述方式基于格论的哈希函数在数据查询认证中的应用方案【摘要】：数据查询认证是保证信息安全的关键技术。基于格论的哈希函数解决了传统哈希函数易受到攻击的问题,增强了其抗碰撞性。本文将基于格论的哈希函数应用到数据查询认证过程之中,阐述如何将基于格论的哈希函数和格摘要的思想应用到各实体运行算法之中,阐述其实体构成,描述实体间的通信协议,并对实体的空间和时间复杂度进行详细分析。经对比,该方案明显降低了数据查询认证过程的复杂度。基于格论的GNSS模糊度解算【摘要】：快速、准确地解算整周模糊度是实现GNSS载波相位实时高精度定位的关键,由于模糊度之间的强相关,基于整数最小二乘估计准则时,需要较长的时间才能搜索出最优的整周模糊度向量。为了提高模糊度的搜索效率,本文在扼要介绍格论的理论框架基础上,引入基于格论的模糊度解算方法,通过格基规约来降低模糊度之间的相关性,从而快速搜索出最优的整数模糊度向量。与此同时,将GNSS领域的主要降相关方法统一到格论框架下,探讨了并建议采用Boot-strapping成功率作为格基规约的性能指标之一。最后试验分析三频多系统长基线相对定位情况下,不同格基规约可获得的性能。基于格论和TRIZ技术进化理论的理想化水平表述方式【摘要】：现有的技术理想化水平定义公式存在不易测算、难于比较折衷以及无法与TRIZ技术进化理论有效对接的缺陷。为解决上述问题,构造了一种基于格论的新型技术系统理想化水平表述方式,并结合Hasse图对技术进化过程中的理想化水平变化程度进行了分析。研究发现,某些技术系统之间存在理想度不可比性特征以及理想度评判的参考点效应,且新型理想化水平表述方式可较好地表征和解释技术系统"迂回"进化和理想化水平非连续变化的特征。基于格论的技术系统理想化水平表述方式评判技术系统状态的理想化水平，本质上就是对技术系统按照有用功能、成本和耗费、有害功能三类指标进行排序。因此，可以构建一个相应的由n维变量元素(x1,x2,……xn)组成的集合I进行排序，以反映其理想化水平高低。然而由于技术系统有用功能是正向指标，而成本和耗费、有害功能是负向指标，因此可以先将二者的所有量值按取相反数的方法正向化，从而得到一个如下n维变量元素构造方式：(x1,x2,……

,xn1,xn1+1,xn1+2,……,xn2) (2)在式(2)中：xi∈［0，+∞)，i∈{1，2，……，n1} xj∈(-∞，0］，j∈{n1+1，n1+2，……，n2}式(2)表示可以用n2个指标综合评价技术系统的理想化水平。在这n2个指标中，描述技术系统有用功能的指标共有n1个，这些指标的取值范围是非负实数集，当某个指标值取零值时，则表示技术系统暂时未能获得该项有用功能；描述技术系统成本耗费和有害作用的指标共有n2-n1个，这些指标的取值范围为非正实数集，某个指标值取负表示技术系统存在该类成本耗费或有害作用，取零则表示该类成本耗费或有害作用不存在或已被有效消除。在实际使用过程中，xi

、xj的参量名称与属性根据不同技术系统的特性决定。基于格论的技术系统理想化水平表述方式格论中的布尔代数布尔代数：代数系统（B，+，。）只要满足交换律、分配律、同一律和互补律，则称它为布尔代数在布尔代数中，元素a的补元素ā可以认为对a的一元运算，因此布尔代数（B，+，。）也可以写作（B，+，。，-），表示它是由两个二元运算及一个二元运算所组成的