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

肖奕鑫+鄭偉珊

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

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

一、引 言

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

二、算法分析

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

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

（一）本文算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（二）實例驗證

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

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

（三）算法評價

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

作者簡介：

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

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

參考文獻(xiàn)：

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

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