以文本方式查看主题

-  计算机科学论坛  (http://bbs.xml.org.cn/index.asp)
--  『 生物信息学 』   (http://bbs.xml.org.cn/list.asp?boardid=46)
----  有多DNA算法了解的吗?  (http://bbs.xml.org.cn/dispbbs.asp?boardid=46&rootid=&id=16987)

--  作者：xzjxu
--  发布时间：4/14/2005 6:25:00 PM

--  有多DNA算法了解的吗?
据说可以并行计算,谁能详细介绍一下
--  作者：zhaoming
--  发布时间：4/23/2005 11:27:00 PM

--  
DNA算法和生物信息学不是一回事

前者借助生物技术的手段发展理论计算机科学,为研制DNA计算机做基础性工作;
后者使用计算机科学和计算机技术的方法研究生物学.

两个方法和目的刚好反过来.

传统的电子计算机的算法(图灵算法)也有并行性,但DNA计算机的算法(DNA图灵算法)
有更强大的计算能力和更高的效律.

等DNA计算理论被发展到一定程度,就有可能出现这样的情况:电子计算机计算多少年才能
解决的问题,DNA计算机几秒钟就轻松搞定.

不过,DNA算法的研究太过长期,实验室样机都得等N年,产业化和商业化更是......


--  作者：eyounx
--  发布时间：4/26/2005 5:57:00 PM

--  
以下是引用zhaoming在2005-4-23 23:27:37的发言：
DNA算法和生物信息学不是一回事

前者借助生物技术的手段发展理论计算机科学,为研制DNA计算机做基础性工作;
后者使用计算机科学和计算机技术的方法研究生物学.

两个方法和目的刚好反过来.

传统的电子计算机的算法(图灵算法)也有并行性,但DNA计算机的算法(DNA图灵算法)
有更强大的计算能力和更高的效律.

等DNA计算理论被发展到一定程度,就有可能出现这样的情况:电子计算机计算多少年才能
解决的问题,DNA计算机几秒钟就轻松搞定.

不过,DNA算法的研究太过长期,实验室样机都得等N年,产业化和商业化更是......



图灵算法？
DNA图灵算法？
更强大的计算能力？
“等DNA计算理论被发展到一定程度,就有可能出现这样的情况:电子计算机计算多少年才能
解决的问题,DNA计算机几秒钟就轻松搞定.”等DNA计算发展到一定程度，难道电子计算不发展？
--  作者：zhaoming
--  发布时间：4/26/2005 8:22:00 PM

--  
以下是引用eyounx在2005-4-26 17:57:40的发言：
[ 图灵算法？
DNA图灵算法？
更强大的计算能力？
“等DNA计算理论被发展到一定程度,就有可能出现这样的情况:电子计算机计算多少年才能
  解决的问题,DNA计算机几秒钟就轻松搞定.”等DNA计算发展到一定程度，难道电子计算不发展？

图灵算法就是算法
DNA图灵算法就是DNA算法

电子计算当然在发展,但NP问题的多项式算法你不大可能找到,在DNA计算上,也许它就成为
P类问题了.

--  作者：eyounx
--  发布时间：4/26/2005 11:23:00 PM

--  
以下是引用zhaoming在2005-4-26 20:22:27的发言：
图灵算法就是算法
DNA图灵算法就是DNA算法

电子计算当然在发展,但NP问题的多项式算法你不大可能找到,在DNA计算上,也许它就成为
P类问题了.


目前没听到任何DNA计算模型的超越性，也就是说，DNA计算模型也就是图灵机，所有问题依旧

--  作者：zhaoming
--  发布时间：4/26/2005 11:37:00 PM

--  
以下是引用eyounx在2005-4-26 23:23:43的发言：
目前没听到任何DNA计算模型的超越性，也就是说，DNA计算模型也就是图灵机，所有问题依旧

计算能力没听说超过图灵机,但不断有报道在DNA计算模型上找到了某NP问题的多项式算法,这应该意味着基于DNA计算模型的P类和NP类的划分会和经典模型有所不同.

--  作者：eyounx
--  发布时间：4/27/2005 9:35:00 AM

--  
以下是引用zhaoming在2005-4-26 23:37:51的发言：
计算能力没听说超过图灵机,但不断有报道在DNA计算模型上找到了某NP问题的多项式算法,这应该意味着基于DNA计算模型的P类和NP类的划分会和经典模型有所不同.


不是一回事，在Nondeterministic Turing Machine上，所有NP-C问题都是在多项式时间内解决（实际上这就是NPC定义）。只要它的计算模型未变，所有问题依旧。
--  作者：zhaoming
--  发布时间：4/27/2005 1:14:00 PM

--  
指的是在确定型模型中,它们不能在多项式时间内解决.

--  作者：xzjxu
--  发布时间：5/5/2005 7:32:00 PM

--  
以下是引用eyounx在2005-4-27 9:35:06的发言：
[quote]以下是引用zhaoming在2005-4-26 23:37:51的发言：
  计算能力没听说超过图灵机,但不断有报道在DNA计算模型上找到了某NP问题的多项式算法,这应该意味着基于DNA计算模型的P类和NP类的划分会和经典模型有所不同.
[/quote]
不是一回事，在Nondeterministic Turing Machine上，所有NP-C问题都是在多项式时间内解决（实际上这就是NPC定义）。只要它的计算模型未变，所有问题依旧。


我注意了一下,好象DNA计算就是把时间复杂度转移到了空间复杂度上,这样时间复杂度可以为多项式的.
--  作者：eyounx
--  发布时间：5/5/2005 9:26:00 PM

--  
以下是引用xzjxu在2005-5-5 19:32:03的发言：
[quote]以下是引用eyounx在2005-4-27 9:35:06的发言：
[quote]以下是引用zhaoming在2005-4-26 23:37:51的发言：
   计算能力没听说超过图灵机,但不断有报道在DNA计算模型上找到了某NP问题的多项式算法,这应该意味着基于DNA计算模型的P类和NP类的划分会和经典模型有所不同.
  [/quote]
  不是一回事，在Nondeterministic Turing Machine上，所有NP-C问题都是在多项式时间内解决（实际上这就是NPC定义）。只要它的计算模型未变，所有问题依旧。
[/quote]
我注意了一下,好象DNA计算就是把时间复杂度转移到了空间复杂度上,这样时间复杂度可以为多项式的.



已经说过了，NPC问题在NTM上是多项式时间，这是NPC的定义
--  作者：xzjxu
--  发布时间：5/6/2005 4:14:00 PM

--  
以下是引用eyounx在2005-5-5 21:26:13的发言：
[quote]以下是引用xzjxu在2005-5-5 19:32:03的发言：
[quote]以下是引用eyounx在2005-4-27 9:35:06的发言：
  [quote]以下是引用zhaoming在2005-4-26 23:37:51的发言：
    计算能力没听说超过图灵机,但不断有报道在DNA计算模型上找到了某NP问题的多项式算法,这应该意味着基于DNA计算模型的P类和NP类的划分会和经典模型有所不同.
   [/quote]
   不是一回事，在Nondeterministic Turing Machine上，所有NP-C问题都是在多项式时间内解决（实际上这就是NPC定义）。只要它的计算模型未变，所有问题依旧。
  [/quote]
  我注意了一下,好象DNA计算就是把时间复杂度转移到了空间复杂度上,这样时间复杂度可以为多项式的.
  
[/quote]
已经说过了，NPC问题在NTM上是多项式时间，这是NPC的定义


呵呵,我是同意你的观点的,呵呵
--  作者：xzjxu
--  发布时间：11/15/2005 1:35:00 PM

--  
量子计算就突破了图灵模式!
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 78.125ms