DNA計(jì)算中的3—SAT問題的自裝配算法.pdf

1、分類號(hào)：TP301Y792273單位代碼：10005學(xué)號(hào)：$200206030密級(jí)：公丌北京工業(yè)大學(xué)碩士學(xué)位論文題目墜趟△過篡蟲鰉3：曼塑聞?lì)}的自裝里篡洼英文并列墨壁!至=△曼曼墾叢壘墜蘭△亙=魚Q基l至叢MQ里3：S△!題目!盥墜盥△￡Q叢￡衛(wèi)!l盥g研究生姓名：到任專業(yè)：運(yùn)簦蘭與控制論研究方向：應(yīng)用動(dòng)力基統(tǒng)與立叢△j簋導(dǎo)師姓名：重太壺職稱：教授瞼文報(bào)告提交日捌2QQ5生5目學(xué)何授予日期授予單何名稱和地?fù)銳E墨上業(yè)厶堂!』E玨Ⅲ王巫蚓

2、1QQ雖jAbstractInthepast10years，alotofachievehasbeenmadeintheDNAcomputing，particularlyintheSATproblem，currently，likeLipton，Adleman，QinghuaLiueta1havemadegreatprogressinthisfieldInthispaperIcontinuewiththeworkabout3SATprobl

3、em’Seffectalgorithmofmypioneers，hereIgivefourmethodmadeightkindsofalgorithm：Thefirstmethodisselfassemblyalgorithm，intermsofselfassemblytheoryIdevicethefunctionaera，anddevicetheAlgorithmitselftheideaissimple，thatistofindt

4、hosestringsfrommtesttubeswhichmaysatisfyeachofclausesrespective，thenputthisstringstoonetesttubetogethertheywillselfassemblywithenzymes’helptOfindthecommonalitystrings，thatistheformula’SsolutionThesecondmethodisfluorescen

5、cesignalgorithm，itisakindofmethodot’selfassemblyinnature，theideaisjustlikethefirstone，thedifferenceisthatittofindcommonalitystringswithprobemodel，anditsspacecomplexityissmallerthanthefirstoneThethirdmethodisthreelinkalgo

6、rithm，itisthefirstone’simprovealgorithm，itadoptthree—linkwaytodevice，andtakethreetestasoneunittoselfassemblyandusethesamewaytocarryoutTheforthmethodisthree—splitalgorithm，thisisasplitstrategy，firsttesetallvariablesinterm

7、softhenumbersofthevariablewhichittakeplaceintheclausethenbythealgorithmofslopetoexactthesplitpointofk，furthertomakesurethesecondsplitpoint，thatistodistributeallvariabletoparts，thensplitallclausetofourparts，thatistosaythe

8、BooleanformulaissplitintofoursubformulaThisfourmethodsandeightkindsofalgorithm，thefirstthreealgorithmthebasealgorithmofthispaperthecommonofthisthreemethodsistoimprovetheparallelismofalgorithmbythemodelofselfassemblythent

9、educethecomplexityofalgorithm’Stimetoconstant，butthespacecomplexityofalgorithmisnobetterthanothersThe1astmethodovercomefrontalgorithm’Sfaultasitreducethetimecomplexitytoconstant，simultaneityitreducethespacecomplexitymore