算法Tile自組裝系統(tǒng)的設(shè)計與應(yīng)用研究.pdf

1、Tile自組裝系統(tǒng)作為一種分布式并行計算模型，在計算能力上具有圖靈通用性（Turing-universal），即Tile自組裝系統(tǒng)具有計算通用性，可以計算一切可計算函數(shù)。然而到目前為止，并沒有找到一個實用的方法，使得對于任何問題都能直接通過這種標準方法來解決。即對于一個具體的問題，我們并不能從自組裝系統(tǒng)的這種計算通用性得到可以直接解決該問題的任何啟示?；谝陨峡紤]，本文將Tile自組裝系統(tǒng)與四類重要的問題建立了對應(yīng)關(guān)系，這四類問題分別是

2、排序問題、布爾邏輯計算問題、NP完全問題中的最大團問題以及RSA公鑰密碼學分析中的整數(shù)分解問題。從算法層面上給出可以有效解決以上問題的具體方法，為Tile自組裝分子計算機的研制提供有力的理論依據(jù)。
　　 排序問題不僅存在于數(shù)據(jù)檢索，而且它也是求解離散對數(shù)問題的小步-大步算法中很關(guān)鍵的一步。本文提出用于排序運算的Tile自組裝系統(tǒng)，利用自組裝過程的并行計算能力，設(shè)計相應(yīng)的tile自組裝算法，將問題的已知條件以及排序規(guī)則嵌入到til

3、e集合中，構(gòu)建求解排序問題的自組裝系統(tǒng)。該方法引入了“模塊化”思想，從理論上可以實現(xiàn)多個子系統(tǒng)同時處理至少兩對或更多數(shù)對的排序操作，從而減少整個自組裝過程的自組裝步數(shù)。最后，討論了該系統(tǒng)的復(fù)雜度，結(jié)果表明所需的tile種類數(shù)為常數(shù)，自組裝步數(shù)為Θ(mn)。
　　 針對數(shù)學計算中的重要基本運算——布爾邏輯計算，構(gòu)造Tile自組裝系統(tǒng)，用于實現(xiàn)對任意布爾邏輯表達式的計算。該方法引入了“分層”的思想，根據(jù)布爾邏輯表達式子句的個數(shù)，以及

4、計算過程的先后性，將整個Tile自組裝計算過程分為若干級子系統(tǒng)。本方法可以最大限度的利用Tile自組裝系統(tǒng)的并行性，實現(xiàn)對布爾邏輯表達式的同步計算，該方法對于求解可滿足性問題以及DES密碼體制中的S-盒子分析具有可行性。
　　 針對NP完全問題中的最大團問題，在二維自組裝平臺上，構(gòu)建非確定性Tile自組裝系統(tǒng)。本系統(tǒng)構(gòu)造性的設(shè)計一組算子tile，將圖的已知信息融入到種子框架，設(shè)計隨機生成圖的tile，用以生成隨機子圖。理論上，通

5、過合理的自組裝判斷運算子系統(tǒng)，判斷隨機生成的圖是否滿足團的條件。最后結(jié)合凝膠電泳技術(shù)從以上得到的團中分離出代表著最大團的解。該方法采用了“逐步刪除非解”的思路，大大降低了求解問題的復(fù)雜度，使得所需的tile種類數(shù)為Θ(mn)，自組裝時間與問題規(guī)模呈線性關(guān)系，從而降低了Tile自組裝實驗的難度，提高了算法的可靠性。
　　 RSA公鑰密碼體制被廣泛應(yīng)用于電子商務(wù)以及密鑰分配等領(lǐng)域，其安全性建立在分解大整數(shù)的困難性上。針對破譯RSA密

6、碼中存在的大數(shù)分解問題，充分利用算法自組裝的并行處理能力，提出兩類分解整數(shù)的自組裝系統(tǒng)。大數(shù)分解的Tile自組裝系統(tǒng)I通過在種子框架上以“逐比特”的方式隨機生成兩個整數(shù)，邊生成數(shù)對邊計算其乘積，并將所得乘積與待分解整數(shù)的相應(yīng)位置的比特信息作比較，用于判斷生成數(shù)對的正確性。該系統(tǒng)只需常數(shù)種tile，便可在與問題規(guī)模呈線性關(guān)系的自組裝步數(shù)中完成對任意整數(shù)的分解。該系統(tǒng)較之同領(lǐng)域其他的算法模型，能在自組裝過程中逐步刪除非解，降低了整個系統(tǒng)的t

7、ile分子數(shù)的消耗，提高了算法的有效性。對于大數(shù)分解的Tile自組裝系統(tǒng)II則是基于歐幾里得算法可以計算任意兩個整數(shù)的公因子這一理論而設(shè)計的。通過先構(gòu)建計算兩個整數(shù)的最大公因子的算法自組裝系統(tǒng)，然后在此基礎(chǔ)之上，添加一個隨機生成數(shù)子系統(tǒng)，用于構(gòu)建分解整數(shù)的自組裝系統(tǒng)。隨機數(shù)生成子系統(tǒng)可以有效的生成小于2N，且除去個與其互素的整數(shù)之外的所有整數(shù)，很大程度上提高了Tile自組裝算法的速度。該方法從二維自組裝平臺上實現(xiàn)了歐幾里得算法，該算法在