朱清时也许还是看了点书的


所有跟贴·加跟贴·新语丝读书论坛

送交者: 雅诗 于 2007-01-28, 04:47:09:

下面朱清时的这段话(引自柔然的文章)非常有趣。

 【代数复杂性的概念可以作复杂性的现代定义的例子。至少在某种程度上,
一个系统的状态可以用一系列数据来描述,这些数据可用数字表示,它们构成一
个数列,因此我们只要定义这种数列的复杂性就行了。
  考虑一个具体例子,比如:l、4、9、16、25、36等数字构成的数列,我们发
现这个数列可以由自然数n的平方得到。
  每当给出一个数列时,我们就进行类似的研究,确定是否存在一个计算机程
序和一组初始数据(为了规范,假设均为图灵机),用它们可以计算出整个数列?
它们若存在并能表达出来,则程序和初始数据的最短长度便是代数复杂程度的量
度;若它们的长度大得难以表达(甚至不存在),则这样的系统就称为复杂系
统。】
  
这段话有趣的地方是把几种复杂度理论揉在一起了。图林机与最主要最基本的复杂度理论, NP 理论(见柔然的文章), 联系在一起。代数复杂性(复杂度?)的英文为 algebraic complexity 吧, 也是一个很重要的理论, 跟 NP 理论有一定联系, 考虑的也是计算所需要的时间空间等等。朱院士举的例子考虑的是程序的长度,却有点像 Kolmogorov complexity (wiki 如下), 哈哈. 像那个斜眼的笑话了。 不过也许朱院士自己是明白的,只不过说得太通俗, 反而让一些人(如我)糊涂了。


http://en.wikipedia.org/wiki/Kolmogorov_complexity

In computer science, the Kolmogorov complexity (also known as descriptive complexity, Kolmogorov-Chaitin complexity, stochastic complexity, algorithmic entropy, or program-size complexity) of an object such as a piece of text is a measure of the computational resources needed to specify the object.




所有跟贴:


加跟贴

笔名: 密码: 注册笔名请按这里

标题:

内容: (BBCode使用说明)