基于0-1规划的DNA计算模型的设计与实现

《基于0-1规划的DNA计算模型的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号UDC1932569学位论文基于0-I规划的DNA计算模型的设计与实现作者姓名：罗海波指导教师：乔建忠教授东北大学信息科学与工程学院申请学位级别：硕士学科类别：工学学科专业名称：计算机系统结构论文提交日期：2008年6月论文答辩日期：2008年6月学位授予日期：2008年7月答辩委员会主席：芝妄；／y评阅人：芝安多∥，j穆坼东北大学2008年6月一——————-AThesisfortheDegreeofMasterinComputerArchitectureTheDesignandImplementationofDNAComputingMod

2、elbasedon0-1programmingByLuoHaiboSupervisor：ProfessorQiaoJianzhongNortheasternUniversityJune2008●-独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：黝移日期：)／帅莎．6．汀学位论文版权使用授权书F=黧雾=焉?嘴靴敝脸部(

3、如作者和导师同意网上交流，请在下方签名：否则视为不同意)学位论文作者签名：黝波签字日期：一I-导师签名：签字日期：：{卅基于O一1规划的DNA计算模型的设计与实现摘要由于生物技术的发展和Adleman实验的成功使人们认识到一种新兴的计算方法．DNA计算。该方法具有的巨大并行性、海量存储以及低能耗等特点，引起了众多学者的关注，成为研究的热点。本文结合生物学的研究方法，对DNA计算及其模拟生物进化过程中的编码问题做了初步地探讨，对0-1规划的DNA计算模型和求解方法进行了研究。在DNA计算中，信息是以DNA序列为载体并通过DNA分子间的特异性杂交来完成

4、信息的处理的，因此，DNA计算首要的问题就是DNA编码问题，目前的编码方法还无法很好地满足特定DNA计算模型的实际要求。本文在对DNA计算编码问题进行了探讨和分析，基于DNA模拟原理和DNA设计的基本原则，针对复杂的O．1规划模型一生产计划模型，提出了DNA编码策略，并用DNA编码链的理论及实验结果验证了编码的可行性。DNA计算离不开生物反应，并且在很大程度上依赖于生物技术，本文在用DNA计算解决生产计划问题的研究中，针对溶液计算的高度并行和高存储性，表面计算的高自动化程度等特点，采用基于溶液与表面计算相结合的方法，来建立复杂的O．1规划问题的DN

5、A计算模型，充分利用了两种计算方法的优点，提高了求解的效率。DNA计算，可以求解复杂的计算问题。论文所构建的解决复杂的O．1规划问题0一生产计划问题的DNA计算模型，尽管在运算规模上还无法达到大容积溶液计算的高并行性和高存储量，但已具备说明问题的特征。通过将生物技术应用到O一1规划问题求解，会给解决NP复杂问题提供一种新思路、新方法。关键词：DNA计算，0-1规划问题，生产计划问题．．III．．一10j-I刍I●-◆东北大学硕士学位论文TheDesignandImplementationofDNAComputingmodelbasedonO一1Pr

6、ogrammingAbstractWiththedevelopmentofbiologictechniqueandSUCCESSofAdleman’Sexperiment，peoplerecognizeanewcomputingparadigms—DNAcomputing．Themassiveparallelism，1ligh—densitystorageandenergyefficiencyofDNAcomputingattracttheconcernofnumerousscholarsfromdifferentfields，whichisthe

7、focusofresearch．Wriththebiologicalresearchmethodandexperimentaltechnique，theencodingproblemandDNAcomputingmodelweremainlystudied，andDNAcomputingbasedon0-1programmingmodelandsohtionwereresearchedinthisthesis．InDNAcomputing，theinformationisalwaysrepresentedbyuniqueDNAsequencesan

8、ditsprocessingisaccomplishedthroughthespecialhybridizationamo