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

1、Tile自組裝系統(tǒng)作為一種分布式并行計(jì)算模型，在計(jì)算能力上具有圖靈通用性（Turing-universal），即Tile自組裝系統(tǒng)具有計(jì)算通用性，可以計(jì)算一切可計(jì)算函數(shù)。然而到目前為止，并沒(méi)有找到一個(gè)實(shí)用的方法，使得對(duì)于任何問(wèn)題都能直接通過(guò)這種標(biāo)準(zhǔn)方法來(lái)解決。即對(duì)于一個(gè)具體的問(wèn)題，我們并不能從自組裝系統(tǒng)的這種計(jì)算通用性得到可以直接解決該問(wèn)題的任何啟示。基于以上考慮，本文將Tile自組裝系統(tǒng)與四類重要的問(wèn)題建立了對(duì)應(yīng)關(guān)系，這四類問(wèn)題分別是

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

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

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

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

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

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