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

離散討論課（常見群、環(huán)、域、格和布爾代數(shù)在計(jì)算機(jī)中的應(yīng)用）群論半群?jiǎn)卧肴喝旱幕径x交換群有限群循環(huán)群半群：設(shè)有一個(gè)代數(shù)系統(tǒng)(S,。)其中“。”是二元運(yùn)算，它滿足結(jié)合律，則稱該代數(shù)系統(tǒng)為半群，對(duì)S內(nèi)任意元素a，b，c有(a。b)。c=a。(b。c)如果半群還滿足交換律，則稱其為可換半群。單元半群：設(shè)有一個(gè)代數(shù)系統(tǒng)(S,。)其中“。”是二元運(yùn)算，它滿足結(jié)合律，并且存在單位元素，則此代數(shù)系統(tǒng)叫做單元半群。即對(duì)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)為群。可換群也叫阿貝爾群。有限群：群的元素個(gè)數(shù)有限，則稱為有限群，反之元素個(gè)數(shù)無(wú)限，則稱為無(wú)限群。循環(huán)群：若群（G，。）中的每一個(gè)元素都是它的某一固定元素a的冪，則稱（G，。）為由a生成的循環(huán)群，a稱作（G，。）的生成元素。剩余類加群：（Zm，+m）是一個(gè)群，周期為m的循環(huán)群，[0]為其單位元素，[i]+[0]=[i]，[i]m=[0]=１。整數(shù)加群：（Ｚ，+）是一個(gè)周期為無(wú)限的循環(huán)群。設(shè)有一個(gè)由ａ生成的循環(huán)群（Ｇ，。），則有：

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

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

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

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

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

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

加密發(fā)送給B,

加密過(guò)程如下：【1】用戶A查公鑰庫(kù)PKDB,查到用戶B的公開密鑰QB。【2】用戶A選擇一個(gè)隨機(jī)數(shù)dA

,且dA

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

x2modn。

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

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

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

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

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

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

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

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

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

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

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

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

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

為N中3個(gè)連續(xù)鄰點(diǎn)的集合,M3

為M3集的灰度均值,M5

為N中5個(gè)連續(xù)鄰點(diǎn)的集合,M5

為M5

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

-M3

的值最大,這是邊界最可能出現(xiàn)的一種組合;(2)選取一個(gè)閾值T,按照下面公式判斷:f(i,j)=

N,|M5

-M3

|max<T,邊界不明顯；（1）

M5

,|M5

-M3

|max≥T,邊界明顯；（2）

另外,在文獻(xiàn)[7]中給出了一種簡(jiǎn)便的算法,先對(duì)周圍的8像素點(diǎn)的像素值進(jìn)行大小排序,將像素值大的5個(gè)組成M5

集,較小的3個(gè)組成M3

集,求出這兩組的均值,再用均值差和給定的閾值T作比較,如果大于T,則判為邊緣上的點(diǎn),反之不是邊緣點(diǎn).半鄰域算法雖能夠保護(hù)邊界,但提取的好壞跟給定的T值相關(guān)很大,所以受到一定的限制.本文算法本文算法是在半鄰域的基礎(chǔ)上,采用一種自適應(yīng)的閾值選擇法,選用3×3的區(qū)域?yàn)檠芯繉?duì)象,計(jì)算出其最大、最小的像素值及標(biāo)準(zhǔn)差,選擇標(biāo)準(zhǔn)差為閾值T的同時(shí),還考慮人眼對(duì)灰度分辯能力的限制.這樣既克服了半鄰域法選擇閾值T的困難,又可以避免一些虛假邊緣的檢測(cè),從而能有效地提取圖像的邊緣.算法見pdf文件格論：L為非空集合，+和。是L上的兩個(gè)二院運(yùn)算，如果他們滿足交換律、結(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，+，。）滿足分配律，即對(duì)任意a,b,c,∈L，有：

a+(b。c)=(a+b)。(a+c) a。(b+c)=(a+b)。(a+c)則稱（L，+，。）是分配格。有界格：設(shè)格（L，+，。）中的+有單位元素1及。有單位元素0，即對(duì)a∈L有a+1=a，a。0=a，則稱該格為有界格格論在計(jì)算機(jī)領(lǐng)域的應(yīng)用：（１）、基于格論的哈希函數(shù)在數(shù)據(jù)查詢認(rèn)證中的

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

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

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