資源描述：
《離散數(shù)學(xué)中np完全問(wèn)題的dna計(jì)算》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、摘要從1994年至今，DNA計(jì)算已成為數(shù)學(xué)、生物學(xué)、化學(xué)、計(jì)算機(jī)科學(xué)等領(lǐng)域的一個(gè)研究熱點(diǎn)，并解決了很多NP一完全問(wèn)題。如何減少編碼量大的問(wèn)題，即解決“指數(shù)爆炸”問(wèn)題，是DNA計(jì)算面臨諸多困難和主要技術(shù)問(wèn)題之一。這就需要我們對(duì)已有的算法進(jìn)行改進(jìn)或?qū)ふ倚碌乃惴āＤ壳?，DNA計(jì)算在計(jì)算原理可行性的論證上比較成熟，對(duì)于表面技術(shù)的研究還處在探索階段，隨著表面技術(shù)的日益成熟，DNA計(jì)算將會(huì)從理論走向?qū)嵺`。離散數(shù)學(xué)是數(shù)學(xué)的一個(gè)分支，離散數(shù)學(xué)中有諸多的NP一完全問(wèn)題，如：求主范式問(wèn)題，圖著色問(wèn)題，求傳遞閉包問(wèn)題，最大匹配問(wèn)題，旅行商問(wèn)題等等。目前，DNA計(jì)算是解決NP一一完全問(wèn)題最有效的方法，本
2、文采用DNA計(jì)算解決了離散數(shù)學(xué)中具有代表性的三個(gè)難計(jì)算問(wèn)題：命題邏輯中“求主范式問(wèn)題”；圖論中“圖著色問(wèn)題"；集合論中“求傳遞閉包問(wèn)題"。本文首先介紹了DNA計(jì)算背景、現(xiàn)狀、原理與基本模型。然后，解決了離散數(shù)學(xué)中上述的三個(gè)問(wèn)題。第一，根據(jù)DNA發(fā)夾結(jié)構(gòu)的突出優(yōu)點(diǎn)，即不需要特殊的生物操作，這樣從很大程度上減少了生物反應(yīng)時(shí)間，并且根據(jù)主范式的定義與DNA發(fā)夾結(jié)構(gòu)的定義知，完全可利用DNA發(fā)夾結(jié)構(gòu)模型，求解離散數(shù)學(xué)中命題公式的主范式；第二，利用DNA計(jì)算機(jī)模型，采取合理編碼使得解空間的生成基于三進(jìn)制，并采取逐步產(chǎn)生滿足定義的DNA鏈的方法，將離散數(shù)學(xué)中圖3一著色問(wèn)題的DNA分子鏈數(shù)由0
3、(3”)減少到了0(2”)，這樣很好地解決了圖3—著色問(wèn)題中的“指數(shù)爆炸’’問(wèn)題，并給出了其應(yīng)用；第三，利用Adleman試管模型，借鑒Hamilton路徑問(wèn)題的思想，求解了難計(jì)算的傳遞閉包問(wèn)題。最后，總結(jié)了全文，討論DNA計(jì)算與數(shù)學(xué)的密切關(guān)系及其在數(shù)學(xué)領(lǐng)域內(nèi)的應(yīng)用，并討論了進(jìn)一步的研究方向。關(guān)鍵詞：DNA計(jì)算；可滿足性問(wèn)題；主范式；圖著色；傳遞閉包摘要AbstractDNAcomputinghasbeenatouchypointforresearchinmathematics，biology,chemisty,andcomputersciencefrom1994topresen
4、tdays．IthassolvedmanyproblemssuchasNPcompleteproblem．OneofmanydifficultiesandmaintechnologythatDNAcomputingfacesishowtoreducethelargecodingquantity,namely,toslove‘'indexexplosion'’problem．Asaresult，weshouldimprovetheexistingcomputingmethodsorfindoutnewcomputingways．Atpresent，DNAcomputingisdem
5、enstratedrelativelymuturelyincomputingtheoryfeasibilityandisstillexploringsurfacetechnology．Asthesurfacethnologycomestomature，DNAcomputingsurelytendstotransferfromlaborotarytomarket．DiscretemathematicsconsistsofSOmanyNPcompleteproblems．Theyareprincipalnormalformproblem，graphcoloringproblem，tr
6、ansitiveclosureproblem，maximummatchingproblem，andtravelquotient．Nowadays，DNAcomputingisthemosteffetivemethodforsolvingNPcompleteproblems．ThispapersolvesthreetypicalproblemsindiscretemathematicsbymeansofDNAcomputing．Theyareprincipalnormalformprobleminpropositionallogic，graphcoloringproblemingr
7、aphtheory,andtransitiveclosureprobleminsettheory．ThisarticleintroducesthebackgroundofDNAcomputering，currentsituation,principleandbasicmodelatfirst．Andthen，itsolvesthreecorrespondingproblems．Firstly,astypicaladvantageofDNAhairpinstructureistha
