fwjmath的相空间

matrix 发表于 2008年6月13日 14时35分 星期五
来自五次方程式部门

密歇根大学计算机科学家开发的一款开源软件(中文)，能将寻找复杂方程式中对称的时间，从数日缩减为数秒。找寻对称是一种能突显通往答案捷径的方法。例如，验证火车时刻表的安全性、确认软件与硬件设计中的臭虫，或着加速一般搜寻任务。

名为saucy（卤莽）的软件由研究人员在2004年开发出来，它能加速基础计算机科学问题的解法，能迅速解答所谓的图自同构问题（graph automorphism problem）。当前软件升级增加了新算法，能更快的发现最短路径和对称。它将复杂方程式转换成图，并在顶点的排列中寻找相似性。在实验测试中，在不到0.5秒内，新软件在全世界路由器的网际网络连接图中捕捉到1083,687个不同的对称。图中的对称性意味着路由器可以被移来移去而不会改变（网络的）运作。在搜寻 Illinois州城市与乡镇之间公路网对称性的过程中，新的算法在0.5 秒内捕捉了104843个对称，而先前最强的演算法花了16分钟。

论文(PDF)

source: http://software.solidot.org/article.pl?sid=08/06/13/0641226

下载了论文来看~~~还是勉强看得明白的~~~算法的思路上还算自然~~~这个算法快的原因一个是面对稀疏图~~~这样的话同一个时间要考虑的结点数目就少了很多~~~另一个原因（据他们说是主要原因）就是观察到大多数图的自同构对称都只涉及到很少几个顶点~~~图的自同构对称置换可以构成一个置换群~~~称为Aut(G)~~~而他们观察到这个群可以由少数几个各自只涉及为数不多的顶点的置换生成出来~~~于是就有了他们的算法~~~

最近课上得差不多了~~~开始钻研图论~~~

source: http://science.solidot.org/article.pl?sid=08/06/06/062235

matrix 发表于 2008年6月06日 14时00分 星期五
来自上帝算法部门

3月份我们曾报道，Tomas Rokick正在开发一个非常高效的方法研究魔方最少的还原步骤，他证明任何魔方都可以在25步内还原。现在根据Tomas Rokick个人主页的更新，他宣布任意结构的魔方都可以在23步内解决。他之前进行运算的工作站为8G内存和1.6GHz Q6600 CPU，现在已经升级为一台超级计算机，索尼图形图像运作公司（Sony Pictures Imageworks）提供给他使用（当然是在电影制作空闲时间内）。在这个曾经制作了《蜘蛛侠3》和《冲浪企鹅》的工作室的帮助下，新的计算结果暗示任意结构的魔方可能的解决步数是21，22或23步。

果然是很好很强大~~~不知道极限是多少？~~~

Foldit是由Bakerlab所在的华盛顿大学的生物化学系和计算机工程系联合开发的一款在线游戏，旨在利用人的解题能力来帮助科学家寻找蛋白质在现实中的折叠结构。

这里有我做的两个介绍视频：

http://youtube.com/watch?v=UB3R5-NU5pc

http://youtube.com/watch?v=FOwrz1tmGXA

然后有中文讨论帖：

http://www.equn.com/forum/thread-18296-1-1.html

这个是我写的一个小小的经验之谈：

http://www.equn.com/forum/viewthread.php?tid=18296&page=2#pid244623

matrix 发表于 2008年5月24日 21时28分 星期六   来自冷静观察部门

冷核聚变（Cold Fusion）是指在接近常温常压和相对简单的设备条件下发生核聚变反应。多个轻原子核被强行聚合形成一个重原子核，并伴随能量释放。1989年3月23 日南安普敦大学的Martin Fleischmann和犹太大学的Stanley Pons宣称成功进行了冷核聚变实验，引起轰动，但其他科学家却无法重复该实验，美国能源部的调查报告认为实验不可信。之后从事冷核聚变的科学家都非常谨慎，前天(22日)日本大阪大学的荒田吉明（Yoshiaki Arata）教授和上海交大的张月昌（Yue Chang Zhang）教授向公众演示了冷核聚变实验，包括6家报纸和2家电视台在内的60余人在场观看了这次引入注目的实验。实验原理是基于他们曾经出版的论文（1，2），方法是用高压将氘气压入包含锆氧化物（ZrO2）和钯纳米粉末的真空单元内。实验产生了大量能源，并观察到氦-4（融合的信号）。这一演示证明这种方法是高度可重复的。

source: http://hardware.solidot.org/hardware/08/05/24/1314226.shtml

如果这是真的就好了~~~冷核聚变向来是人类的梦想~~~不用复杂的托卡马克装置也不用激光更不用维持一个等离子火球就可以享受聚变的能量~~~

不过由于以前的一些虚假实验，我们还是要比较小心~~~不要这么快庆祝~~~

最近四川地震，本来应该早一点写的，这两天只顾着关心新闻了。越看新闻，心情越沉重。天灾不可避免，地震不可预测。四川又是山地，震后气候条件又不好，这种情况下伤员的抢救就只能靠运气了。好在现在大部人马已经在深入灾区，情况开始稳定。现在我们也不能做什么了，只能希望抢救人员努力，大家有钱捐钱，没钱捐血，再不济像我这样的也要上网帮忙到处转贴情况，好让更多的人放心。

温总理已经到前线了，我真的很感动。照片照不出什么来，但是如果看那段流传的前线记者QQ记录的话，真的真的很感动，因为在抢救工作期间稳定灾民情绪是很重要的。

顺便BS一下那些粪青，没有科学常识就在骂地震局骂解放军，我以后见一个打一个毫不留手。

关于地震的科学常识的话可以看这里：http://songshuhui.net/archives/141

这里资料很齐全，而且不断有更新。

抢救地震伤员，祈愿天佑吾国。

注：本文遵守首页上的CC版权声明，转载请注明作者与出处，谢谢！

序

这个文章是我跟pchu说好了一起写的。规则很简单：他跟我分别给出两样东西，分别作为开头和结尾。他给的开头是福尔摩斯，我给的结尾是衍射，这就是这个奇怪题目的由来。当然，在这种限制下想写出很系统化介绍某种东西的文章是很困难的，所以大家可能就只能看到一些东西的片断，所以就将就一下吧。好了，我们开始旅行了，出发！

起点：福尔摩斯的眼睛

福尔摩斯这个英国著名侦探小说家柯南·道尔笔下的人物，想必大家对他都很熟悉。而大家对他最为称道的恐怕就是他那双锐利的眼睛了。他能通过裤脚上的泥点推断出一个人在来之前到过伦敦什么地方，也能通过一个人的外貌判断出这个人的身份和职业，甚至还有曾经到过的地方。福尔摩斯的断案能力恐怕是跟他敏锐的观察力息息相关的，但是在观察力的背后还有一个重要的因素就是他丰富的刑侦知识。

当然，福尔摩斯只是一个小说人物，但是他的这种超乎寻常的观察力和推理已经成为了大家对于一个优秀侦探的基本印象，以至于现在“现代福尔摩斯”已经成为了人们对那些优秀侦探的尊称。当然，由于科技的发展，现代的侦探的工具比福尔摩斯用的尺子和烟斗要优秀得多。这些现代工具让侦探们拥有了比福尔摩斯更敏锐的观察能力。可以说，这些工具让侦探们具有了“福尔摩斯的眼睛”。下面我们就来简单看一些例子。

关于刑侦技术，大家可以第一个想到的就是美剧CSI中描述的各种先进的技术。但是事实上现实生活中没有多少案件是可以用到这样高级的技术的。刑侦中用得最多的技术，恐怕就是最基础的血液分析。由于重大案件通常会伴随着流血或者凶杀事件，所以对于血液的研究对于侦查是十分有用的。

对于血液的分析，第一步就是对血液痕迹的确定。在电视剧里边大家可能会看到侦探们用一种喷雾喷洒地面，然后再用紫外线灯照射，有过血迹的地方就会呈现蓝白色的荧光。其实这种喷雾就是一种特殊的化学物质和过氧化氢的混合物，这种化学物质名为鲁米诺试剂（luminol），也叫发光氨。这种试剂检验血液痕迹的原理很简单。血液中含有血红蛋白，其中含有铁离子，是过氧化氢分解的一种催化剂。过氧化氢分解时会释放出具有强氧化性的单个氧原子，然后氧原子就会与鲁米诺试剂发生氧化还原反应，使鲁米诺试剂发出蓝白色的荧光。知道原理之后，我们可以想到既然是氧化还原反应使鲁米诺试剂发出荧光的话，岂不是很多化学药品都可以做到这一点？事实上，这种血液的检测方法的缺点也就在于这里。如果罪犯事先用家庭常用的漂白粉清洗过现场的话，现场也会残留具有氧化性的氯化合物，会对荧光的判断造成干扰。不过，有经验的侦探通常都可以分清两者的区别，另外一种规避的办法就是先让犯罪现场干燥几天再进行血迹检测，这时候不稳定的氯化合物会分解殆尽，干扰也就会降低。当然，这种方法由于准确度有限，所以通常鉴定出血迹之后侦探们还会用别的方法来进行对比鉴定。尽管有这些缺点，这种血迹鉴定的方法还是被广泛采用，因为它也有几个很明显的优点。首先，它不会对血迹的化学成分造成干扰，因为血迹在这里是作为催化剂出现的，这样就给后期的证据提取提供了方便。其次，这种方法可以检测出浓度为百万分之一的血液痕迹，普通的清洗方法对它的干扰不大，而且根据荧光的强度等等信息可以推断出血迹出现的大概时间。最后，这种方法简单易行，而且成本不高，便于广泛铺开使用。所以这种检验方法实在是很流行。

血迹提取出来了，接下来的工作有两个方向，一个是轨迹分析，另一个是成分分析。轨迹分析说白了就是根据血迹的形状推断凶手作案的工具和方式，比如说在凶手挥动凶器的时候，可能会有微量的死者血液随着凶器的挥动溅到墙壁和天花板上，通过对这些血液痕迹形状的分析我们可以知道凶手使用的凶器的大致大小、形状和类型，甚至还可以知道凶手当时挥动凶器的力度和轨迹。成分分析就更为复杂。一般来说，现在的技术已经可以分清血迹是人血还是动物血，可以辨别血型，最后最强大的一招就是提取DNA样本，然后用PCR等方法倍增后与犯罪嫌疑人的DNA进行比对。由于DNA相当于一个人独一无二的标记，所以这种方法的准确率极高。不过由于成本实在很高，所以也不经常采用。

除了血液的处理之外，还有一样很基础的刑侦技术就是指纹提取。人们很早就观察到，每个人的指纹都有独特之处，两个人的指纹相同是几乎没有可能的。人的皮肤又会不停分泌油脂和汗液，这些物质在手指接触其它物体的时候会在物体上面留下痕迹，这就是指纹。正是因为这样，指纹的提取才成为了刑侦中的一个重要元素，因为这种方法成本较低，方便快捷，而且准确率也颇高。

通常被提取的指纹都是位于凶器表面或者是墙壁桌子镜子等光滑表面上的，因为这些表面上的指纹比较容易提取。提取的方法也很多，大多数都是先使指纹显形，然后再照相记录。提取的方法有很多，最简单的就是用光照的办法，因为油脂等等物质虽说透明，但毕竟是杂质，会对表面的光学特性有影响。所以通过光学的方法可以辨析出一部分指纹。常用的方法有很多，有时候就算用普通的光源都能发现指纹，有时候就需要一些特殊的光源比如说紫外线灯。另一种常用的方法就是利用油脂容易粘住小东西的特性，用粉末来进行提取。这种方法也是很方便的，大家在家里就可以用奶粉试试，也可以使用碘的蒸汽。不过这两个方法在指纹很“老”的时候就会失去效用，那时候就要用更高级的物理和化学方法来处理指纹了，其中最简单的就是硝酸银法。因为汗液中含有氯化钠，而银离子对氯离子是很敏感的，于是我们就可以利用这个反应使指纹显形。当然，这些提取指纹的方法，犯罪分子用一个手套就可以使它完全失效。不过也有通过犯罪分子丢弃的手套来提取指纹的案例，这就只能怪贼太笨了。

在信息化的今天，侦探们除了面对暴力犯罪以外，还要对付高科技犯罪。这些犯罪也迫使侦探们发展出针对这些信息技术的侦查技巧和工具，其中除了大家熟知的网络入侵痕迹检查和数据复原技术等等之外，还有一些很偏门的东西，比如说利用操作系统本身的一些不算是漏洞的缺点，还有就是直接利用无线电方法。

大家知道，我们的电脑在删除文件的时候，大半是只会将文件的索引删除，文件的真实内容仍然好好躺在硬盘里边。这就是一些入门级的数据恢复软件可以处理的范围。现在市面上也有所谓的“文件粉碎机”之类的软件出售，这些软件大多是通过覆盖文件所在扇区的内容来彻底消灭痕迹的。而美国军方销毁文件的标准做法是对文件所在扇区用全0和全1间隔覆盖8次，力图消去可能的剩磁。但是有时候其它文件也会透露出一些重要信息。磁盘系统的写入单位是簇，一簇的大小大概是几KB。但是一个文件不一定能够完全占据整数个簇，这是操作系统就会用内存的数据去继续填充。这样的话通过分析这些内存数据，侦探们有时候也能发现一些线索。

无线电监听就更直接了。早在20世纪中期，贝尔实验室的研究人员就已经发现电子仪器的操作会发射一些电磁波，通过检测这些电磁波可以大概知道电子仪器进行了什么操作。于是乎，美国警方就又发明了一种新的侦查方法。他们可以直接把车停在犯罪嫌疑人的屋外，利用无线电来监听屋内键盘的操作，这样的话无论是多高深的技术都如玻璃一样透明了。

虽然侦探们拥有了这么多的对付高科技犯罪的方法，有一样东西还是他们无能为力的。这不是因为科技发展还不够的问题，而是科技已经发展到可以证明侦探们对这样东西是无能为力的了。那就是密码。

第二站：密码，人类智慧的较量

密码术由来已久。最早的密码恐怕要追溯到埃及金字塔上的象形文字。在一些金字塔上就有用形态相似读音不同的象形文字互相代替的现象，不过这看起来更加像某种吸引游人停留的手段。密码术的最早有实际意义的应用恐怕还是在我们中国。比如说古代的用兵凭证“虎符”本身就有密码的功能，既能代表一些简单的信息，也能证明来人的身分，因为虎符本来是一体的，剖开后就可以依据花纹是否相合判断是否原件。还有竹简书写术和密码诗等等就不细说了。西方的密码应用也很早，最有名的就是圆筒书写法。首先寄件人将布条缠在某一直径的圆筒上，然后再在布条上写字。解开后布条上就有一列被打乱了的字迹了。收件人收到布条以后，只需要将布条往相同直径的圆筒上一缠，马上就能读出寄件人写的内容。而在这个过程中，传信的邮差由于不知道圆筒的直径，所以根本不能了解布条上写的内容。如果说金字塔上的密题是字母替换密码的先声的话，这种圆筒书写法恐怕就是移位加密法的前身了。

在密码学研究当中，我们通常有如下的术语。要传递的信息叫做明文，就像寄件人写的内容。在传递中别人无法阅读的信息叫密文，就像邮差手上的布条。将明文转化为密文的过程叫加密，将密文转化为明文的过程叫解密。在加密过程中用的决定加密结果的信息叫加密密钥，在解密过程中的就叫解密密钥。在很多时候加密密钥和解密密钥是一样的，在圆筒加密法中的对应物就是圆筒的直径。通常在一个例子里边，我们�