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

离 散 讨 论 课,（常见群、环、域、格和布尔代数在计算机中的应用）,群论,半 群单 元 半 群群 的 基 本 定 义交 换 群有 限 群循 环 群,半 群：设有一个代数系统(S,。)其中“。”是二元运算，它满足结合律，则称该代数系统为半群，对S内任意元素a，b，c有(a。b)。c=a。(b。c)如果半群还满足交换律，则称其为可换半群。,单 元 半 群：设有一个代数系统(S,。)其中“。”是二元运算，它满足结合律，并且存在单位元素，则此代数系统叫做单元半群。即对S内任意元素a，b，c有(a。b)。c=a。(b。c)且存在1S有1.a=a。1=a。如果单元半群还满足交换律，则称其为可换单元半群。,群 论：（1）、满足结合律。（2）、存在单位元素。（3）、存在逆元素。则称该代数系统为群。,可换群也叫阿贝尔群。,有 限 群：群的元素个数有限，则称为有限群，反之元素个数无限，则称为无限群。,循 环 群：若群（G，。）中的每一个元素都是它的某一固定元素a的幂，则称（G，。）为由a生成的循环群，a称作（G，。）的生成元素。,剩余类加群：（Zm，+m）是一个群，周期为m的循环群，0为其单位元素，i+0=i，im=0=。,整数加群：（，+）是一个周期为无限的循环群。,设有一个由生成的循环群（，。），则有：（）、若周期为无限，则（，。）与（，+）同构。（）、若周期为，则（，。）与（，+）同构。,群论在计算机领域的应用：（）、组合群论在密码学中的应用（）、用群论的基础知识理解信号处理中的一些基本概念（如：时域和频域信号空间的群同构关系）（）、椭圆曲线密码的应用等,组合群论在密码学中的应用,用群论的基础知识理解信号处理中的一些基本概念(如：时域和频域信号空间的群同构关系),椭圆曲线密码的应用,椭圆曲线密码的应用,无线网络操作模式由 3 部分组成:移动用户。能从一个代理范围移动到另一个代理范围;地点固定的代理。它如同一个调停机构,协调移动用户和服务器之间的通信服务;服务器。当移动用户从一个地区到另一个地区时,它能选择一个合适的代理,实现与服务器和其它移动用户之间的通信。为了保证用户的合法接入和信息的安全传输,一般需要做到如下 5 点：【1】访问控制。确保接入用户合法。此过程可以通过移动用户的 MAC 地址和用户的相关信息来实现。【2】身份认证。确保对方为其所声称的用户及数据的完整性,通过数字签名技术实现。【3】不可否认性。确保其发出的信息事后无法抵赖,通过数字签名实现。【4】数据完整性。防止信息被截获后数据被更改重新发送,通过消息认证码(MAC)和数字签名来实现。【5】保密性。信息在传输中即使被截获,因截获者无法破解而毫无意义。通过数据的加密来实现。密码应用中常使用的两类椭圆曲线为定义在有限域 GF(p)上的素曲线和在有限域 GF(2n)上的二元曲线。素曲线计算不需二元曲线所要求的位混淆运算,对软件应用而言,最好使用素曲线;而对硬件应用而言,则最好使用二元曲线,它可用很少的门电路来得到快速且功能强大的密码体制。,椭圆曲线的加密和解密在 SEC1 的椭圆曲线密码标准(草案)中规定,一个椭圆曲线密码由下面的 6 元组所描述:T=式中:p 为大于 3 的素数,它确定了 有 限 域GF(p);a 和 b 确定了椭圆曲线;G 为循环子群 E 1的生成元;n 为素数且为生成元 G 的阶,G 和 n 确定了循环子群 E 1;h 为余因子,有 h=|E 1|/n,h将交换群 E 和循环子群联系起来。用户的私钥定义为一个随机数 dd 0,1,2,n-1用户的公开密钥定义为 Q 点：Q=dG设要加密的明文数据为 M,将 M 划分为一些较小的数据块,M=m 1,m 2,m t。式中:0 mi n。用户 A 将数据 mi 加密发送给 B,加密过程如下：【1】用户 A 查公钥库 PKDB,查到用户 B 的公开密钥 QB。【2】用户 A 选择一个随机数 dA,且 dA 0,1,2,n-1。【3】用户 A 计算点 X 1:(x 1,y 1)=dAG。【4】用户 A 计算点 X 2:(x 2,y 2)=dAQB,如果分量 x 2=0,则转【2】。【5】用户 A 计算 C=mi x 2 mod n。【6】用户 A 发送加密数据(X1,C)给用户 B。解密过程：【1】B 用自己的私钥 dB 求出点 X2:dBX 1=dB(dG)=dA(dBG)=dAQB=X2:(x2,y2)【2】对 C 解密,得到明文数据 m i=C x2-1 mod n。与此类似,可以构造其他椭圆曲线密码。,环论和格论,环 的 基 本 定 义整环域,格 的 基 本 定 义分配格有界格补格布尔代数,环 的 定 义：设有代数系统（，+，。），若满足以下条件：（）、（，+）为可换群；（即满足交换律、结合律、存在零元、负元）（）、（，。）为半群；（即满足结合律）（）、运算。对+满足分配律，即对任意，存在。（+）。+。（+）。+。,整 环：（，+，。）为环，它有单位元素且是可换环，无零因子，则称（，+，。）是一个整环。,域：设环（，+，。）满足下列条件：（1）、R至少有两个元素（2）、（R，。）有单位元素（3）、（R，。）是可换的（4）、除零元外，其余元素均存在逆元素（aR的逆元可记作a-1）,环论在计算机领域的应用：（）、广义圆环论在可持续发展中的应用（）、环论在线性代数中的一些应用（）、一个基于广义圆环论的系统管理数字化模型,广义圆环论在可持续发展中的应用【摘要】从世界经济全球化、入关和西部大开发出发,以辩证法为指导,数学为工具,用泛系方法研究可持续发展。提出广义圆环论,建立数学模型,给出四种基本类型。以绿化植树造林工程为例。说明它在规划、预决策、管理方面的应用,环论在线性代数中的一些应用【摘要】：把经典环论中的一些重要结论应用到线性代数中矩阵的研究,通过幂等矩阵和可逆矩阵给出方块矩阵新的分解,并讨论一般矩阵的相关性质.,一个基于广义圆环论的系统管理数字化模型【摘要】：从一般系统观点出发,利用以闭环系统和圆环论为基础的广义圆环论构建了一个分布式网络考试管理系统模型 中小学教师现代教育技术培训考试信息处理系统,一个基于广义圆环论的系统管理数字化模型,域在计算机领域的应用：（）、近冰梅类域论（）、二次域理想类数生成元的求解及计算机实现（）、基于半邻域法的自适应图像边缘提取方法,近冰梅类域论【摘要】：正类域论(Class Field Theory)是数学诸理论中,体系最完美的一种数学百科全书如是说。她是现代数论的一门极重要理论,现在已渗透应用到各分枝,几乎无处不涉及。此理论由希尔波特(Hilbert)在1900年左右猜测出,主要由福特汪格勒(Furtwangler),高木贞治(Takagi),阿廷(Artin)至1927年给出证明。但象“类域构作”这样的世纪性大问题,研究还远无尽头,是现代最激烈前沿之一。类域论理论系统深邃,定理异常丰富,初学者短期内不易掌握。,二次域理想类数生成元的求解及计算机实现【摘要】二次域上的理想类数是有限的,文章利用理想类、类群的相关性质,通过计算机编程,求解出二次域Z(D)的类数及理想的代表。,基于半邻域法的自适应图像边缘提取方法【摘要】：图像边缘对图像识别和计算机分析十分重要,至今已经提出了大量的各种类型边缘提取算法.该文在半邻域法的基础上提出了一种基于自适应阈值选择的图像边缘提取算法,在判断某一像素点是否在边缘上时,以该像素点为中心,选取33的区域为研究对象,求出该区域的最大、最小、均值像素值及标准差,在选用标准差为其阈值的同时,还考虑人的视觉对于灰度分辨能力的限制.最后,对多幅灰色图像进行了边缘提取,结果证实了该文方法的有效性.,半邻域法采用半邻域法检测某一像素点是否在边缘上,是对其周围相邻的 8 个像素点进行分析,把它们划分为两组,按照顺时针方向,以连续 3个像素点为一组,其余的 5 个像素点为第二组.这样就有 8 种情况,如图 1 所示(表示被检测像素点,表示第一组像素点,表示第二组像素点).,令 N 为中心点 的 8 邻点集合,N 为N 集的灰度均值,M3 为 N 中 3个连续邻点的集合,M3 为 M 3集的灰度均值,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 值相关很大,所以受到一定的限制.,本文算法本文算法是在半邻域的基础上,采用一种自适应的阈值选择法,选用 33 的区域为研究对象,计算出其最大、最小的像素值及标准差,选择标准差为阈值 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，即对aL有a+1=a，a。0=a，则称该格为有界格,格论在计算机领域的应用：（）、基于格论的哈希函数在数据查询认证中的 应用方案（）、基于格论的GNSS模糊度解算（）、基于格论和TRIZ技术进化理论的理想化水平表述方式,基于格论的哈希函数在数据查询认证中的应用方案【摘要】：数据查询认证是保证信息安全的关键技术。基于格论的哈希函数解决了传统哈希函数易受到攻击的问题,增强了其抗碰撞性。本文将基于格论的哈希函数应用到数据查询认证过程之中,阐述如何将基于格论的哈希函数和格摘要的思想应用到各实体运行算法之中,阐述其实体构成,描述实体间的通信协议,并对实体的空间和时间复杂度进行详细分析。经对比,该方案明显降低了数据查询认证过程的复杂度。,基于格论的GNSS模糊度解算【摘要】：快速、准确地解算整周模糊度是实现GNSS载波相位实时高精度定位的关键,由于模糊度之间的强相关,基于整数最小二乘估计准则时,需要较长的时间才能搜索出最优的整周模糊度向量。为了提高模糊度的搜索效率,本文在扼要介绍格论的理论框架基础上,引入基于格论的模糊度解算方法,通过格基规约来降低模糊度之间的相关性,从而快速搜索出最优的整数模糊度向量。与此同时,将GNSS领域的主要降相关方法统一到格论框架下,探讨了并建议采用Boot-strapping成功率作为格基规约的性能指标之一。最后试验分析三频多系统长基线相对定位情况下,不同格基规约可获得的性能。,基于格论和TRIZ技术进化理论的理想化水平表述方式【摘要】：现有的技术理想化水平定义公式存在不易测算、难于比较折衷以及无法与TRIZ技术进化理论有效对接的缺陷。为解决上述问题,构造了一种基于格论的新型技术系统理想化水平表述方式,并结合Hasse图对技术进化过程中的理想化水平变化程度进行了分析。研究发现,某些技术系统之间存在理想度不可比性特征以及理想度评判的参考点效应,且新型理想化水平表述方式可较好地表征和解释技术系统迂回进化和理想化水平非连续变化的特征。,基于格论的技术系统理想化水平表述方式评判技术系统状态的理想化水平，本质上就是对技术系统按照有用功能、成本和耗费、有害功能三类指标进行排序。因此，可以构建一个相应的由 n 维变量元素(x1,x2,x n)组成的集合 I 进行排序，以反映其理想化水平高低。然而由于技术系统有用功能是正向指标，而成本和耗费、有害功能是负向指标，因此可以先将二者的所有量值按取相反数的方法正向化，从而得到一个如下 n 维变量元素构造方式：(x1,x2,xn1,xn1+1,xn1+2,xn2)(2)在式(2)中：x i 0，+)，i1，2，n1 x j(-，0，jn1+1，n1+2，n2式(2)表示可以用 n2个指标综合评价技术系统的理想化水平。在这 n2 个指标中，描述技术系统有用功能的指标共有 n 1 个，这些指标的取值范围是非负实数集，当某个指标值取零值时，则表示技术系统暂时未能获得该项有用功能；描述技术系统成本耗费和有害作用的指标共有 n2-n1 个，这些指标的取值范围为非正实数集，某个指标值取负表示技术系统存在该类成本耗费或有害作用，取零则表示该类成本耗费或有害作用不存在或已被有效消除。在实际使用过程中，x i、x j 的参量名称与属性根据不同技术系统的特性决定。,基于格论的技术系统理想化水平表述方式,格论中的布尔代数,布 尔 代 数：代数系统（B，+，。）只要满足交换律、分配律、同一律和互补律，则称它为布尔代数,在布尔代数中，元素a的补元素可以认为对a的一元运算，因此布尔代数（B，+，。）也可以写作（B，+，。，-），表示它是由两个二元运算及一个二元运算所组成的代数系统。,格论中布尔代数在计算机领域的应用：（）、基于布尔代数的木马行为界定及判别（）、泛布尔代数在数字逻辑电路设计中的应用,基于布尔代数的木马行为界定及判别【摘 要】：相比于其他恶意代码,木马具有明显的目的性、针对性及系统协作性,它更像是一款应用程序,传统的识别技术对其无能为力.从一般木马行为特点出发,采用格、布尔代数模型归纳可疑程序的动作点,将木马的行为点对应为代数系统中的元素,依据格、布尔代数的偏序关系量化出木马行为的危险级,由此为木马行为识别找到了系统量化的理论,给出了形式概念格建模的算法以及与布尔代数模型间的转换算法.最后给出基于模型判别的应用实例,并进行了部分样本验证,从而为木马行为监测和判别提供理论支持和具体实施方法.,基于布尔代数的木马行为界定及判别,泛布尔代数在数字逻辑电路设计中的应用(1)数字逻辑电路中的基本单位是与门、或门、非门和D触发器。它们是数字逻辑电路中不可细分的结构。基本单位的提出，使泛布尔代数的概念能在数字逻辑电路中实现。(2)泛布尔代数的重要特点是存在因素和状态变量两个概念，因此如何将这两个概念体现在数字逻辑电路中也是论文的重点。为了解决这个问题，论文定义泛布尔代数信号，它使数字逻辑电路的输入输出符合泛布尔代数的规范。最终设计出一个矩阵式键盘完成将输入数字转变成泛布尔代数信号的任务。(3)真假值表、逻辑图、系统陈述以及逻辑函数式是描述泛布尔代数规律的工具。通过对这些工具的分析发现，真假值表是最容易得到的。所以得出真假值表是设计的第一步。然后，通过真假值表得出逻辑图。用图域化简方法得出化简后的逻辑函数式，通过逻辑函数式则很容易得到基本单位构成的数字逻辑电路。系统陈述可以通过真假值表和逻辑图得出，它主要用于辅助计算机编程实现数字逻辑电路。,泛布尔代数在数字逻辑电路设计中的应用,谢谢！,