matrix 发表于 2008年12月06日 17时00分 星期六
来自P-=-NP部门

Aram Harrow和同事刚刚在预印本网站发表了一篇论文：解决线性方程系统的量子算法（PDF）。以下引用格致的介绍：

我们现有的量子算法，比如Shor算法，Grover算法大都只能对经典算法作出多项式性的改进，新算法把最好的经典算法效率作出了指数性的提高，把求解稀疏矩阵方程的复杂度由O(n)降低到log(n）。更加重要的是，这是第一个解决了科学和工程中最常见的问题的量子算法。像Shor算法那样破解密码毕竟用途有限。在实际的工程和科研中，我们遇到最多的问题就是解线性方程组，且我们遇到的大部分线性方程组都是稀疏的，维度也非常高。新量子算法将能非常迅速的解决常见的线性方程组。唯一的问题是我们需要一台真正的量子计算机，MIT，斯坦福，马里兰，现在瞧你们的了。

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

相当不错~~~有这个动力的话量子计算机问世又近了一步了~~~

source: http://science.solidot.org/article.pl?sid=08/09/12/0559219

matrix 发表于 2008年9月12日 14时00分 星期五
来自真运气部门

第44个梅森素数是于2006年9月发现的，但在短短半个月内，GIMPS分布式计算接连发现了两个梅森素数。

2008年8月23日，一台GIMPS客户端计算机报告发现了第45个梅森素数，第一轮验证已经完成，确认是一个新的素数，第二轮验证的完成日期是9月11日。但始料未及的是，9月6日，又一台计算机报告发现了第46个梅森素数，独立验证确认这也是一个新素数，第二轮验证预订于14日。GIMPS将于下周透露细节。

我只能说运气太好了~~~要不就不发现~~~一发现就是两个~~~又有人能领奖金了~~~

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步。

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

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

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

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

update：已经被强烈怀疑是造假了~~~看来聚变能源还是任重道远啊~~~

matrix 发表于 2008年3月20日 13时42分 星期四
来自重大新闻部门

加拿大和德国科学家组成的研究小组利用高压硅氢化合物制造出室温超导体。研究人员声称可以避开冷却需求，因此可保证超导电线在常温下工作。Saskatchewan大学的John Tse教授说，“如果氢化合物经受足够的压力，它就会具备超导电性。”他与手下的博士生Yansun Yao完成了理论研究，德国Max Plank学院的研究员Mikhail Eremets完成了实验验证。新的超导家族基于叫“硅烷（silane）”的氢化合物，它与甲烷有点类似，硅烷由一个硅原子和4个氢原子组成（甲烷则是一个碳原子和4个氢原子）。

source: http://science.solidot.org/article.pl?sid=08/03/20/0544225

人类梦寐以求的东西终于实现了~~~

matrix 发表于 2008年3月07日 15时30分 星期五
来自量子猫部门

1974年，Stephen Hawking预言黑洞可能会发出辐射——这就所谓的霍金辐射(Hawking radiation)，当一对虚粒子突然出现在黑洞视界周围时，一个会掉入黑洞，另一个则以辐射形式逃逸出去，就像是黑洞发出辐射一样。至今还没有人观察到霍金辐射，因为信号太弱了。

意大利di Trento大学的科学家宣称首次观测到了霍金辐射，但不是来自黑洞，而是玻色-爱因斯坦凝聚的音波边界，他们创造的一个数学模型。结果和理论预测完全一致，虽然仅仅是计算机模拟试验，研究人员仍然坚信他们第一次观察到了“霍金辐射”。科学界还是很看重“第一”的，不过数学真的是这么计算的吗？

论文预印本发表在arXiv上。

source = http://science.solidot.org/article.pl?sid=08/03/07/0731238

这个之前在《环球科学》上面就看过原理的描述~~~

这个结果是霍金辐射的一个比较有利的证据，因为通过类比可以将时空类比成流体~~~现在对流体有类似霍金辐射的现象的话，我们对时空中也存在霍金辐射这样的现象也会更有信心~~~这就是类比推理，一种很有用的不完全归纳法，详见波利亚的《怎样解题》~~~

matrix 发表于 2008年2月22日 22时05分 星期五
来自GFW系统有没有镜像部门

普林斯顿大学的研究人员利用冷却重启法破解了硬盘加密技术。大家可能都有所了解，内存中的数据并不会随着电源关闭而立即消失，数据消失的时间从几秒钟到几分钟不等。使用冷却剂冷却内存，则可以延缓数据消失的时间。在实验中，研究人员甚至还动用了-196 °C液氮，他们把使用过的内存从计算机中取出保存在液氮容器中达一个小时以上，然后再安装到计算机中，发现其中的数据几乎完好无损。以下摘要来自他们完成的、提供给同行审议的论文：

“与多数人的印象相反，现代计算机中使用的动态随机存取存储器（DRAM）在掉电后依然能保存数据几秒钟至几分钟，即便是在工作温度或者是从主板上移除。DRAM并非是可靠的存储器，只要没有刷新，数据就不会马上消失，保留的内容足够让恶意攻击者或法院取证获得全系统的存储映像。意味着当黑客能够直接接触物理硬件时，操作系统中加密材料的安全性非常有限。我们测试了流行的硬件加密系统——BitLocker，FileVault，dm-crypt，和TrueCrypt——没有使用任何特殊的设备。我们用实验方法展现了内存剩磁的程度和可预测性。我们发现剩磁时间可以通过简单的技术戏剧性的增加。我们用新算法寻找内存映像中的密钥，修正因为数据位消失而产生的错误。论文中我们讨论了几个减轻风险的策略，但显然不存在简单的修补术。”

实验视频：Half-size WMV(33 MB)；论文全文（PDF）。

source: http://it.solidot.org/article.pl?sid=08/02/22/1348234

其实我觉得有时候搞信息学和计算机的人容易忽略一点：有时候你面对的不是纯逻辑的抽象系统而是真实存在的物理系统。有些东西可能在逻辑上无懈可击，但是在实际生活中总会有找到绕过去的破解之道~~~比如说量子计算机的可能局限性就是一个例子~~~它在实际上不一定是梦寐以求的非确定性图灵机~~~

matrix 发表于 2008年2月16日 12时25分 星期六
来自微软耍流氓部门

微软研究人员研究用“信息流行病”更高效的分发软件的补丁。

微软英国剑桥研究所的Milan Vojnović和同事想要利用类似网络蠕虫的方式在电脑之间传播补丁，代替从服务器下载，从而降低服务器负荷。研究人员同时还希望以此防御恶意蠕虫，提升蠕虫之间竞争——部署一种白帽（white-hat）蠕虫，使它比新的攻击性病毒更快的把补丁传送到易受攻击的电脑上。现有的多数蠕虫是通过随机的探测子网络中电脑，寻找新的肉鸡和感染宿主，Vojnović认为这非常低效，浪费时间。Vojnović的团队设计了更智能的策略，提供更高的击中率。

source: http://it.solidot.org/article.pl?sid=08/02/16/0435250

这可是Kohlrabi小说中的一个设想啊~~~看来快要实现了~~~

但是这样还是有问题~~~万一有黑客截获这个蠕虫然后分发恶意修改后的新的蠕虫怎么办？~~~

matrix 发表于 2008年2月14日 15时12分 星期四
来自黑金之海部门

根据“卡西尼号”探测器发回的数据，土星卫星Titan上的液体碳氢化合物是地球上已知石油和天然气储量的数百倍（图片，卡西尼雷达数据组合视频）。碳氢化合物雨从天而降，聚集在一起，形成辽阔的海洋和巨大的沙丘。Johns Hopkins大学的Ralph Lorenz说，“它就像一座巨大的有机化学工厂”。

source: http://science.solidot.org/article.pl?sid=08/02/14/071238

等到能去开采的时候说不定人类早就不需要使用这些有机燃料了~~~现在我们需要的时候又没法弄来~~~

不过话说Titan上面这么多有机物~~~也有可能成为生命的源泉~~~

matrix 发表于 2008年2月12日 13时42分 星期二
来自人人都爱民谣部门

"2001年911事件发生后不久，一个小包裹寄给了20世纪前半最伟大的民歌手Woody Guthrie的档案馆。在确认并非包裹炸弹后，Guthrie的女儿发现它是Woody Guthrie在1949年的一次实况表演的录音磁带，是某人私下里录制的，也是目前留下的唯一一个实况演唱录音带，Guthrie后来患上Huntington舞蹈病而停止了表演。他的女儿决定把录音带转换成数字格式，但是由于时代长久，转换的效果非常非常差，就像"wow-wow"，数学家J. Howarth使用自己开发的算法对录音进行了后期调整，尽可能使它接机原声（调整后的音乐）。由于在恢复工作上的贡献，他被授予格莱美奖。文章提供了两段处理前和处理后的片段。"

source: http://science.solidot.org/article.pl?sid=08/02/12/0538250