一種尋找有限代數(shù)系統(tǒng)同構(gòu)變換的算法

肖奕鑫+鄭偉珊

【摘 要】同構(gòu)不僅在數(shù)學(xué)上有重要意義，在人工智能與機(jī)器學(xué)習(xí)等應(yīng)用領(lǐng)域也有重要意義，但傳統(tǒng)文獻(xiàn)往往只給出同構(gòu)的定義，故本文將給出一種快速尋找有限代數(shù)系統(tǒng)全部同構(gòu)變換的算法，并且使用匯編語(yǔ)言實(shí)現(xiàn)該算法來(lái)檢測(cè)其速度。

【關(guān)鍵詞】有限代數(shù)系統(tǒng)；同構(gòu)變換；匯編程序

一、引 言

關(guān)于兩個(gè)代數(shù)系統(tǒng)同構(gòu)[1，2]的定義：

二、算法分析

本文通過(guò)先把具有相同特征的元素歸為同類，然后在每個(gè)類中配對(duì)的方法來(lái)降低檢驗(yàn)次數(shù)，如果同類元素個(gè)數(shù)不一致則可直接判定不同構(gòu)。

每個(gè)元素左乘或右乘代數(shù)系統(tǒng)中的所有元素等價(jià)于一個(gè)自變換，而有限的自變換可以用有限個(gè)可能帶分支的循環(huán)來(lái)表示，這樣就可以把循環(huán)結(jié)構(gòu)一樣的元素歸為一類。我們把含有該元素的循環(huán)定義為該元素的主循環(huán)。把主循環(huán)上由該元素乘冪生成的元素稱為主循環(huán)鏈，我們把每個(gè)元素主循環(huán)鏈中包含的元素個(gè)數(shù)稱為該元素的特征，顯然同類元素具有相同的特征（但特征相同不一定是同類元素），我們把各類按特征從大到小進(jìn)行排列，如果每個(gè)類中的元素的對(duì)應(yīng)在逐步排列過(guò)程被確定，則其主循環(huán)鏈的元素的對(duì)應(yīng)也會(huì)被確定，從而可以先配對(duì)而跳過(guò)后邊的排列，最終減少排列的次數(shù)。

（一）本文算法

通過(guò)上邊的分析，我整理得出同構(gòu)檢測(cè)算法如下：

步驟1. 把第一個(gè)代數(shù)系統(tǒng)的乘法表中的元素字符串進(jìn)行二進(jìn)制編號(hào)后寫(xiě)入內(nèi)存。

步驟2. 計(jì)算第一個(gè)代數(shù)系統(tǒng)各元素的特征和循環(huán)結(jié)構(gòu)，并把元素乘法表按特征從大到小進(jìn)行重新排列，特征相同按循環(huán)結(jié)構(gòu)中其他循環(huán)個(gè)數(shù)大小排列，對(duì)具有相同循環(huán)結(jié)構(gòu)的元素進(jìn)行歸類，由于按循環(huán)結(jié)構(gòu)排列，所以同類元素是連續(xù)的，歸類只需記錄類的起始點(diǎn)和終止點(diǎn)，并保存其排列變換于A。

步驟3. 把第二個(gè)代數(shù)系統(tǒng)的乘法表中的元素字符串進(jìn)行二進(jìn)制編號(hào)后寫(xiě)入內(nèi)存。

步驟4. 如果兩個(gè)代數(shù)系統(tǒng)的元素個(gè)數(shù)不一樣則顯示元素個(gè)數(shù)不同而不同構(gòu)然后退出程序。

步驟5. 計(jì)算第二個(gè)代數(shù)系統(tǒng)各元素的特征和循環(huán)結(jié)構(gòu)，把循環(huán)結(jié)構(gòu)和第一個(gè)代數(shù)系統(tǒng)一樣的元素對(duì)應(yīng)起來(lái)，如果有元素對(duì)應(yīng)不上則顯示該元素沒(méi)有對(duì)應(yīng)元而不同構(gòu)然后退出程序。

步驟6. 保存第二個(gè)代數(shù)系統(tǒng)各元素的對(duì)應(yīng)排列于B。

步驟7. 定義配對(duì)鎖變量，并初始化為0。

步驟8. 如果存在只有一個(gè)元素的類，則將這些類的元素先固定對(duì)應(yīng)（同時(shí)把各配對(duì)元素配對(duì)鎖設(shè)為0），并把各元素主循環(huán)鏈中由該元素乘冪形成的元素固定對(duì)應(yīng)（同時(shí)把各配對(duì)元素配對(duì)鎖設(shè)為0），如果對(duì)應(yīng)過(guò)程發(fā)現(xiàn)對(duì)應(yīng)元素已配對(duì)且與先前配對(duì)不一致則顯示固定配對(duì)沖突而不同構(gòu)，然后退出程序。如果發(fā)現(xiàn)對(duì)應(yīng)元素配對(duì)不同類則顯示固定配對(duì)不同類而不同構(gòu)，然后退出程序。

步驟9. 判斷是不是所有元素都配對(duì)完畢，如果配對(duì)完畢則跳到步驟13，否則，鎖變量加1，對(duì)下一類元素中從該類起始點(diǎn)開(kāi)始尋找未被選取的元素。

步驟10. 配對(duì)并上鎖（即記下鎖變量），并把該元素主循環(huán)鏈中由該元素乘冪形成的元素固定對(duì)應(yīng)，如果對(duì)應(yīng)過(guò)程發(fā)現(xiàn)對(duì)應(yīng)元素已配對(duì)且與先前配對(duì)不一致，則跳到步驟11，如果全部一致則跳到步驟9。

步驟11. 清除鎖變量下對(duì)位的對(duì)應(yīng)，并從選擇同類中的下一元素，如果本類元素已選完（已到達(dá)終止點(diǎn)）則跳到步驟12，否則，跳到步驟10。

步驟12. 鎖變量減1，如果鎖變量為0則顯示已不存在同構(gòu)映射并退出程序，否則跳轉(zhuǎn)到步驟11。

步驟13. 按照配對(duì)法則對(duì)全部元素的乘積進(jìn)行同構(gòu)檢測(cè)，如果檢測(cè)不一致則跳到步驟14，否則跳到步驟15。

步驟14. 判斷鎖變量是否為0，若是則顯示已不存在同構(gòu)映射并退出程序，否則跳到步驟11。

步驟15. 顯示存在同構(gòu)映射并根據(jù)配對(duì)法則和排列A，B把同構(gòu)變換記錄在變換文件中，并提示是否尋找下一個(gè)同構(gòu)變換，如果用戶點(diǎn)擊是則跳到步驟11繼續(xù)判斷，否則退出程序。

（二）實(shí)例驗(yàn)證

26階循環(huán)群自同構(gòu)程序運(yùn)行輸出如下圖：

第一列第二行到第十二行可以看到的元素都是與26互質(zhì)的數(shù)，這些結(jié)果與數(shù)學(xué)上循環(huán)群的性質(zhì)是完全一致的。

（三）算法評(píng)價(jià)

本文的算法對(duì)全部元素都是單一元或者單一元的冪元覆蓋全部元素的代數(shù)系統(tǒng)只需要進(jìn)行一次檢驗(yàn)就可以知道是否同構(gòu)，但對(duì)于只有一類元素且全部元素都是一階元的代數(shù)系統(tǒng)這種極端情況就只能使用全排列檢驗(yàn)。

作者簡(jiǎn)介：

肖奕鑫，講師，理學(xué)碩士，應(yīng)用數(shù)學(xué)。

鄭偉珊，講師，理學(xué)博士，應(yīng)用數(shù)學(xué)。

參考文獻(xiàn)：

[1]楊子胥.近世代數(shù)[M].北京：高等教育出版社，2000：22.

[2]熊全淹.近世代數(shù)[M].武昌：武漢大學(xué)出版社，1995：46-47.