離散數(shù)學討論課(群環(huán)格域布爾代數(shù))

離散討論課（常見群、環(huán)、域、格和布爾代數(shù)在計算機中的應(yīng)用）群論半群單元半群群的基本定義交換群有限群循環(huán)群半群：設(shè)有一個代數(shù)系統(tǒng)(S,。)其中“?！笔嵌\算，它滿足結(jié)合律，則稱該代數(shù)系統(tǒng)為半群，對S內(nèi)任意元素a，b，c有(a。b)。c=a。(b。c)如果半群還滿足交換律，則稱其為可換半群。單元半群：設(shè)有一個代數(shù)系統(tǒng)(S,。)其中“。”是二元運算，它滿足結(jié)合律，并且存在單位元素，則此代數(shù)系統(tǒng)叫做單元半群。即對S內(nèi)任意元素a，b，c有(a。b)。c=a。(b。c)且存在1∈S有1.a=a。1=a。如果單元半群還滿足交換律，則稱其為可換單元半群。群論：（1）、滿足結(jié)合律。

（2）、存在單位元素。

（3）、存在逆元素。則稱該代數(shù)系統(tǒng)為群?？蓳Q群也叫阿貝爾群。有限群：群的元素個數(shù)有限，則稱為有限群，反之元素個數(shù)無限，則稱為無限群。循環(huán)群：若群（G，。）中的每一個元素都是它的某一固定元素a的冪，則稱（G，。）為由a生成的循環(huán)群，a稱作（G，。）的生成元素。剩余類加群：（Zm，+m）是一個群，周期為m的循環(huán)群，[0]為其單位元素，[i]+[0]=[i]，[i]m=[0]=１。整數(shù)加群：（Ｚ，+）是一個周期為無限的循環(huán)群。設(shè)有一個由ａ生成的循環(huán)群（Ｇ，。），則有：

（１）、若ａ周期為無限，則（Ｇ，。）與（Ｚ，+）同構(gòu)。

（２）、若ａ周期為ｍ，則（Ｇ，。）與（Ｚｍ，+ｍ）同構(gòu)。群論在計算機領(lǐng)域的應(yīng)用：

（１）、組合群論在密碼學中的應(yīng)用

（２）、用群論的基礎(chǔ)知識理解信號處理中的一些基本概念（如：時域和頻域信號空間的群同構(gòu)關(guān)系）

（３）、橢圓曲線密碼的應(yīng)用等組合群論在密碼學中的應(yīng)用用群論的基礎(chǔ)知識理解信號處理中的一些基本概念(如：時域和頻域信號空間的群同構(gòu)關(guān)系)橢圓曲線密碼的應(yīng)用橢圓曲線密碼的應(yīng)用無線網(wǎng)絡(luò)操作模式由3部分組成:①移動用戶。能從一個代理范圍移動到另一個代理范圍;②地點固定的代理。它如同一個調(diào)停機構(gòu),協(xié)調(diào)移動用戶和服務(wù)器之間的通信服務(wù);③服務(wù)器。當移動用戶從一個地區(qū)到另一個地區(qū)時,它能選擇一個合適的代理,實現(xiàn)與服務(wù)器和其它移動用戶之間的通信。為了保證用戶的合法接入和信息的安全傳輸,一般需要做到如下5點：【1】訪問控制。確保接入用戶合法。此過程可以通過移動用戶的MAC地址和用戶的相關(guān)信息來實現(xiàn)?！?】身份認證。確保對方為其所聲稱的用戶及數(shù)據(jù)的完整性,通過數(shù)字簽名技術(shù)實現(xiàn)?！?】不可否認性。確保其發(fā)出的信息事后無法抵賴,通過數(shù)字簽名實現(xiàn)?！?】數(shù)據(jù)完整性。防止信息被截獲后數(shù)據(jù)被更改重新發(fā)送,通過消息認證碼(MAC)和數(shù)字簽名來實現(xiàn)?！?】保密性。信息在傳輸中即使被截獲,因截獲者無法破解而毫無意義。通過數(shù)據(jù)的加密來實現(xiàn)。密碼應(yīng)用中常使用的兩類橢圓曲線為定義在有限域GF(p)上的素曲線和在有限域GF(2n)上的二元曲線。素曲線計算不需二元曲線所要求的位混淆運算,對軟件應(yīng)用而言,最好使用素曲線;而對硬件應(yīng)用而言,則最好使用二元曲線

,它可用很少的門電路來得到快速且功能強大的密碼體制。橢圓曲線的加密和解密在SEC1的橢圓曲線密碼標準(草案)中規(guī)定,一個橢圓曲線密碼由下面的6元組所描述:T=<p,a,b,G,n,h>式中:p為大于3的素數(shù),它確定了有限域GF(p);a和b確定了橢圓曲線;G為循環(huán)子群E1的生成元;n為素數(shù)且為生成元G的階,G和n確定了循環(huán)子群E1;h為余因子,有h=|E1|/n,h將交換群E和循環(huán)子群聯(lián)系起來。用戶的私鑰定義為一個隨機數(shù)dd∈{0,1,2,?,n-1}用戶的公開密鑰定義為Q點： Q=dG設(shè)要加密的明文數(shù)據(jù)為M,將M劃分為一些較小的數(shù)據(jù)塊,M=[m1,m2,?,mt]。式中:0≤mi<n。用戶A將數(shù)據(jù)mi

加密發(fā)送給B,

加密過程如下：【1】用戶A查公鑰庫PKDB,查到用戶B的公開密鑰QB?！?】用戶A選擇一個隨機數(shù)dA

,且dA

∈{0,1,2,?,n-1}。【3】用戶A計算點X1:(x1,y1)=dAG?！?】用戶A計算點X2:(x2,y2)=dAQB,如果分量x2=0,則轉(zhuǎn)【2】?！?】用戶A計算C=mi

x2modn。

【6】用戶A發(fā)送加密數(shù)據(jù)(X1

,C)給用戶B。解密過程：【1】B用自己的私鑰dB

求出點X2:dBX1=dB(dG)=dA(dBG)=dAQB=X2:(x2,y2)【2】對C解密,得到明文數(shù)據(jù)mi=Cx2-1modn。與此類似,可以構(gòu)造其他橢圓曲線密碼。環(huán)論和格論環(huán)的基本定義整環(huán)域格的基本定義分配格有界格補格布爾代數(shù)環(huán)的定義：設(shè)有代數(shù)系統(tǒng)（Ｒ，+，。），若滿足以下條件：（１）、（Ｒ，+）為可換群；（即滿足交換律、結(jié)合律、存在零元、負元）（２）、（Ｒ，。）為半群；（即滿足結(jié)合律）（３）、運算。對+滿足分配律，即對任意ａ，ｂ，ｃ∈Ｒ，存在ａ。（ｂ+ｃ）＝ａ。ｂ+ａ。ｃ（ｂ+ｃ）。ａ＝ｂ。ａ+ｃ。ａ整環(huán)：

（Ｒ，+，。）為環(huán)，它有單位元素且是可換環(huán)，無零因子，則稱（Ｒ，+，。）是一個整環(huán)。域：設(shè)環(huán)（Ｒ，+，。）滿足下列條件：（1）、R至少有兩個元素（2）、（R，。）有單位元素（3）、（R，。）是可換的（4）、除零元外，其余元素均存在逆元素（a∈R的逆元可記作a-1）環(huán)論在計算機領(lǐng)域的應(yīng)用：

（１）、廣義圓環(huán)論在可持續(xù)發(fā)展中的應(yīng)用

（２）、環(huán)論在線性代數(shù)中的一些應(yīng)用

（３）、一個基于廣義圓環(huán)論的系統(tǒng)管理數(shù)字化模型廣義圓環(huán)論在可持續(xù)發(fā)展中的應(yīng)用【摘要】從世界經(jīng)濟全球化、入關(guān)和西部大開發(fā)出發(fā),以辯證法為指導(dǎo),數(shù)學為工具,用泛系方法研究可持續(xù)發(fā)展。提出廣義圓環(huán)論,建立數(shù)學模型,給出四種基本類型。以綠化植樹造林工程為例。說明它在規(guī)劃、預(yù)決策、管理方面的應(yīng)用環(huán)論在線性代數(shù)中的一些應(yīng)用

【摘要】：把經(jīng)典環(huán)論中的一些重要結(jié)論應(yīng)用到線性代數(shù)中矩陣的研究,通過冪等矩陣和可逆矩陣給出方塊矩陣新的分解,并討論一般矩陣的相關(guān)性質(zhì).一個基于廣義圓環(huán)論的系統(tǒng)管理數(shù)字化模型【摘要】：從一般系統(tǒng)觀點出發(fā),利用以閉環(huán)系統(tǒng)和圓環(huán)論為基礎(chǔ)的廣義圓環(huán)論構(gòu)建了一個分布式網(wǎng)絡(luò)考試管理系統(tǒng)模型———中小學教師現(xiàn)代教育技術(shù)培訓(xùn)考試信息處理系統(tǒng)一個基于廣義圓環(huán)論的系統(tǒng)管理數(shù)字化模型域在計算機領(lǐng)域的應(yīng)用：

（１）、近冰梅——類域論

（２）、二次域理想類數(shù)生成元的求解及計算機實現(xiàn)

（３）、基于半鄰域法的自適應(yīng)圖像邊緣提取方法近冰梅——類域論【摘要】：正類域論(ClassFieldTheory)是數(shù)學諸理論中,體系最完美的一種——《數(shù)學百科全書》如是說。她是現(xiàn)代數(shù)論的一門極重要理論,現(xiàn)在已滲透應(yīng)用到各分枝,幾乎無處不涉及。此理論由希爾波特(Hilbert)在1900年左右猜測出,主要由福特汪格勒(Furtwangler),高木貞治(Takagi),阿廷(Artin)至1927年給出證明。但象“類域構(gòu)作”這樣的世紀性大問題,研究還遠無盡頭,是現(xiàn)代最激烈前沿之一。類域論理論系統(tǒng)深邃,定理異常豐富,初學者短期內(nèi)不易掌握。二次域理想類數(shù)生成元的求解及計算機實現(xiàn)

【摘要】二次域上的理想類數(shù)是有限的,文章利用理想類、類群的相關(guān)性質(zhì),通過計算機編程,求解出二次域Z(D)的類數(shù)及理想的代表?；诎豚徲蚍ǖ淖赃m應(yīng)圖像邊緣提取方法

【摘要】：圖像邊緣對圖像識別和計算機分析十分重要,至今已經(jīng)提出了大量的各種類型邊緣提取算法.該文在半鄰域法的基礎(chǔ)上提出了一種基于自適應(yīng)閾值選擇的圖像邊緣提取算法,在判斷某一像素點是否在邊緣上時,以該像素點為中心,選取3×3的區(qū)域為研究對象,求出該區(qū)域的最大、最小、均值像素值及標準差,在選用標準差為其閾值的同時,還考慮人的視覺對于灰度分辨能力的限制.最后,對多幅灰色圖像進行了邊緣提取,結(jié)果證實了該文方法的有效性.半鄰域法采用半鄰域法檢測某一像素點是否在邊緣上,是對其周圍相鄰的8個像素點進行分析,把它們劃分為兩組,按照順時針方向,以連續(xù)3個像素點為一組,其余的5個像素點為第二組.這樣就有8種情況,如圖1所示(＊表示被檢測像素點,⊕表示第一組像素點,⊙表示第二組像素點).令N為中心點＊的8鄰點集合,N為N集的灰度均值,M3

為N中3個連續(xù)鄰點的集合,M3

為M3集的灰度均值,M5

為N中5個連續(xù)鄰點的集合,M5

為M5

集的灰度均值.f(i,j)表示第(i,j)個像素點的灰度值,T表示所給的閾值.具體的實現(xiàn)步驟為:(1)首先在這8種情況之中,選取一組,使得M5

-M3

的值最大,這是邊界最可能出現(xiàn)的一種組合;(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值相關(guān)很大,所以受到一定的限制.本文算法本文算法是在半鄰域的基礎(chǔ)上,采用一種自適應(yīng)的閾值選擇法,選用3×3的區(qū)域為研究對象,計算出其最大、最小的像素值及標準差,選擇標準差為閾值T的同時,還考慮人眼對灰度分辯能力的限制.這樣既克服了半鄰域法選擇閾值T的困難,又可以避免一些虛假邊緣的檢測,從而能有效地提取圖像的邊緣.算法見pdf文件格論：L為非空集合，+和。是L上的兩個二院運算，如果他們滿足交換律、結(jié)合律、吸收律，則代數(shù)系統(tǒng)（L,+,。）為格，也稱作代數(shù)格。

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

結(jié)合律：(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，+，。）是分配格。有界格：設(shè)格（L，+，。）中的+有單位元素1及。有單位元素0，即對a∈L有a+1=a，a。0=a，則稱該格為有界格格論在計算機領(lǐng)域的應(yīng)用：（１）、基于格論的哈希函數(shù)在數(shù)據(jù)查詢認證中的

應(yīng)用方案（２）、基于格論的GNSS模糊度解算（３）、基于格論和TRIZ技術(shù)進化理論的理想化

水平表述方式基于格論的哈希函數(shù)在數(shù)據(jù)查詢認證中的應(yīng)用方案【摘要】：數(shù)據(jù)查詢認證是保證信息安全的關(guān)鍵技術(shù)?；诟裾摰墓：瘮?shù)解決了傳統(tǒng)哈希函數(shù)易受到攻擊的問題,增強了其抗碰撞性。本文將基于格論的哈希函數(shù)應(yīng)用到數(shù)據(jù)查詢認證過程之中,闡述如何將基于格論的哈希函數(shù)和格摘要的思想應(yīng)用到各實體運行算法之中,闡述其實體構(gòu)成,描述實體間的通信協(xié)議,并對實體的空間和時間復(fù)雜度進行詳細分析。經(jīng)對比,該方案明顯降低了數(shù)據(jù)查詢認證過程的復(fù)雜度?；诟裾摰腉NSS模糊度解算【摘要】：快速、準確地解算整周模糊度是實現(xiàn)GNSS載波相位實時高精度定位的關(guān)鍵,由于模糊度之間的強相關(guān),基于整數(shù)最小二乘估計準則時,需要較長的時間才能搜索出最優(yōu)的整周模糊度向量。為了提高模糊度的搜索效率,本文在扼要介紹格論的理論框架基礎(chǔ)上,引入基于格論的模糊度解算方法,通過格基規(guī)約來降低模糊度之間的相關(guān)性,從而快速搜索出最優(yōu)的整數(shù)模糊度向量。與此同時,將GNSS領(lǐng)域的主要降相關(guān)方法統(tǒng)一到格論框架下,探討了并建議采用Boot-strapping成功率作為格基規(guī)約的性能指標之一。最后試驗分析三頻多系統(tǒng)長基線相對定位情況下,不同格基規(guī)約可獲得的性能。基于格論和TRIZ技術(shù)進化理論的理想化水平表述方式【摘要】：現(xiàn)有的技術(shù)理想化水平定義公式存在不易測算、難于比較折衷以及無法與TRIZ技術(shù)進化理論有效對接的缺陷。為解決上述問題,構(gòu)造了一種基于格論的新型技術(shù)系統(tǒng)理想化水平表述方式,并結(jié)合Hasse圖對技術(shù)進化過程中的理想化水平變化程度進行了分析。研究發(fā)現(xiàn),某些技術(shù)系統(tǒng)之間存在理想度不可比性特征以及理想度評判的參考點效應(yīng),且新型理想化水平表述方式可較好地表征和解釋技術(shù)系統(tǒng)"迂回"進化和理想化水平非連續(xù)變化的特征?；诟裾摰募夹g(shù)系統(tǒng)理想化水平表述方式評判技術(shù)系統(tǒng)狀態(tài)的理想化水平，本質(zhì)上就是對技術(shù)系統(tǒng)按照有用功能、成本和耗費、有害功能三類指標進行排序。因此，可以構(gòu)建一個相應(yīng)的由n維變量元素(x1,x2,……xn)組成的集合I進行排序，以反映其理想化水平高低。然而由于技術(shù)系統(tǒng)有用功能是正向指標，而成本和耗費、有害功能是負向指標，因此可以先將二者的所有量值按取相反數(shù)的方法正向化，從而得到一個如下n維變量元素構(gòu)造方式：(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個指標綜合評價技術(shù)系統(tǒng)的理想化水平。在這n2個指標中，描述技術(shù)系統(tǒng)有用功能的指標共有n1個，這些指標的取值范圍是非負實數(shù)集，當某個指標值取零值時，則表示技術(shù)系統(tǒng)暫時未能獲得該項有用功能；描述技術(shù)系統(tǒng)成本耗費和有害作用的指標共有n2-n1個，這些指標的取值范圍為非正實數(shù)集，某個指標值取負表示技術(shù)系統(tǒng)存在該類成本耗費或有害作用，取零則表示該類成本耗費或有害作用不存在或已被有效消除。在實際使用過程中，xi

、xj的參量名稱與屬性根據(jù)不同技術(shù)系統(tǒng)的特性決定?；诟裾摰募夹g(shù)系統(tǒng)理想化水平表述方式格論中的布爾代數(shù)布爾代數(shù)：代數(shù)系統(tǒng)（B，+，。）只要滿足交換律、分配律、同一律和互補律，則稱它為布爾代數(shù)在布爾代數(shù)中，元素a的補元素ā可以認為對a的一元運算，因此布爾代數(shù)（B，+，。）也可以寫作（B，+，。，-），表示它是由兩個二元運算及一個二元運算所組成的