苦等了一周，终于有幸见识了老陈70行的程序。算法和我们预想的一样。随机点，划分voronoi图，找重心，用重心取代原来的点。
    一遍又一遍的计算中，图形不断的扭曲，变形，答案渐渐明晰。无数的六边形，室友说这个很像细胞，而我觉得像蜂窝煤……多么震撼的美丽。突然就想到了《heroes in my heart》的最后一段——
    在一次采访当中，作为数学家的Thom同两位古人类学家讨论问题。谈到远古的人们为什么要保存火种时，一个人类学家说，因为保存火种可以取暖御寒；另外一个人类学家说，因为保存火种可以烧出鲜美的肉食。而Thom说，因为夜幕来临之际，火光摇曳妩媚，灿烂多姿，是最美最美的。
    美丽是我们的数学家英雄们永恒的追求。

 http://www.comp.nus.edu.sg/~xujia/mirror/algorithm.myrice.com/algorithm/commonalg/misc/strassen/strassen.htm

矩阵乘法是线性代数中最常见的运算之一，它在数值计算中有广泛的应用。若A和B是2个n×n的矩阵，则它们的乘积C=AB同样是一个n×n的矩阵。A和B的乘积矩阵C中的元素C[i,j]定义为:　

若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素C[i,j]，需要做n个乘法和n-1次加法。因此，求出矩阵C的n²个元素所需的计算时间为0(n³)。

60年代末，Strassen采用了类似于在大整数乘法中用过的分治技术，将计算2个n阶矩阵乘积所需的计算时间改进到O(n^log7)=O(n^2.18)。

首先，我们还是需要假设n是2的幂。将矩阵A，B和C中每一矩阵都分块成为4个大小相等的子矩阵，每个子矩阵都是n/2×n/2的方阵。由此可将方程C=AB重写为:

　(1)

由此可得:　

C₁₁=A₁₁B₁₁+A₁₂B₂₁                           (2)

C₁₂=A₁₁B₁₂+A₁₂B₂₂                           (3)

C₂₁=A₂₁B₁₁+A₂₂B₂₁                           (4)

C₂₂=A₂₁B₁₂+A₂₂B₂₂                           (5)

如果n=2，则2个2阶方阵的乘积可以直接用(2)-(3)式计算出来，共需8次乘法和4次加法。当子矩阵的阶大于2时，为求2个子矩阵的积，可以继续将子矩阵分块，直到子矩阵的阶降为2。这样，就产生了一个分治降阶的递归算法。依此算法，计算2个n阶方阵的乘积转化为计算8个n/2阶方阵的乘积和4个n/2阶方阵的加法。2个n/2×n/2矩阵的加法显然可以在c*n²/4时间内完成，这里c是一个常数。因此，上述分治法的计算时间耗费T(n)应该满足：

这个递归方程的解仍然是T(n)=O(n³)。因此，该方法并不比用原始定义直接计算更有效。究其原因，乃是由于式(2)-(5)并没有减少矩阵的乘法次数。而矩阵乘法耗费的时间要比矩阵加减法耗费的时间多得多。要想改进矩阵乘法的计算时间复杂性，必须减少子矩阵乘法运算的次数。按照上述分治法的思想可以看出，要想减少乘法运算次数，关键在于计算2个2阶方阵的乘积时，能否用少于8次的乘法运算。Strassen提出了一种新的算法来计算2个2阶方阵的乘积。他的算法只用了7次乘法运算，但增加了加、减法的运算次数。这7次乘法是:　M₁=A₁₁(B₁₂-B₂₂)

M₂=(A₁₁+A₁₂)B₂₂

M₃=(A₂₁+A₂₂)B₁₁

M₄=A₂₂(B₂₁-B₁₁)

M₅=(A₁₁+A₂₂)(B₁₁+B₂₂)

M₆=(A₁₂-A₂₂)(B₂₁+B₂₂)

M₇=(A₁₁-A₂₁)(B₁₁+B₁₂)

做了这7次乘法后，再做若干次加、减法就可以得到:　

C₁₁=M₅+M₄-M₂+M₆

C₁₂=M₁+M₂

C₂₁=M₃+M₄

C₂₂=M₅+M₁-M₃-M₇

以上计算的正确性很容易验证。例如:　

C₂₂=M₅+M₁-M₃-M₇=(A₁₁+A₂₂)(B₁₁+B₂₂)+A₁₁(B₁₂-B₂₂)-(A₂₁+A₂₂)B₁₁-(A₁₁-A₂₁)(B₁₁+B₁₂)=A₁₁B₁₁+A₁₁B₂₂+A₂₂B₁₁+A₂₂B₂₂+A₁₁B₁₂-A₁₁B₂₂-A₂₁B₁₁-A₂₂B₁₁-A₁₁B₁₁-A₁₁B₁₂+A₂₁B₁₁+A₂₁B₁₂   =A₂₁B₁₂+A₂₂B₂₂　

由(2)式便知其正确性。

至此，我们可以得到完整的Strassen算法如下：

procedure STRASSEN(n,A,B,C);
begin
if n=2 then MATRIX-MULTIPLY(A，B，C)
else begin
将矩阵A和B依(1)式分块;
STRASSEN(n/2,A11,B12-B22,M1);
STRASSEN(n/2,A11+A12,B22,M2);
STRASSEN(n/2,A21+A22,B11,M3);
STRASSEN(n/2,A22,B21-B11,M4);
STRASSEN(n/2,A11+A22,B11+B22,M5);
STRASSEN(n/2,A12-A22,B21+B22,M6);
STRASSEN(n/2,A11-A21,B11+B12,M7);                     ;               

end;

end;

其中MATRIX-MULTIPLY(A，B，C)是按通常的矩阵乘法计算C=AB的子算法。

Strassen矩阵乘积分治算法中，用了7次对于n/2阶矩阵乘积的递归调用和18次n/2阶矩阵的加减运算。由此可知，该算法的所需的计算时间T(n)满足如下的递归方程:

按照解递归方程的套用公式法，其解为T(n)=O(n^log7)≈O(n^2.81)。由此可见，Strassen矩阵乘法的计算时间复杂性比普通矩阵乘法有阶的改进。

有人曾列举了计算2个2阶矩阵乘法的36种不同方法。但所有的方法都要做7次乘法。除非能找到一种计算2阶方阵乘积的算法，使乘法的计算次数少于7次，按上述思路才有可能进一步改进矩阵乘积的计算时间的上界。但是Hopcroft和Kerr(197l)已经证明，计算2个2×2矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再寄希望于计算2×2矩阵的乘法次数的减少。或许应当研究3×3或5×5矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是O(n^2.367)。而目前所知道的矩阵乘法的最好下界仍是它的平凡下界Ω(n²)。因此到目前为止还无法确切知道矩阵乘法的时间复杂性。关于这一研究课题还有许多工作可做。

本页最后一次更新于09/29/2004
email: starfish@vip.sina.com
©2000 算法与数据结构 http://algorithm.126.com/ 版权所有 转载请保留出处

中文名称：维度：数学漫步
英文名称：Dimensions: a walk through mathematics
资源类型：DVDRip
发行时间：2008年
地区：美国
语言：英语
简介：


《维度；数学漫步（Dimensions: a walk through mathematics）》是两小时长的CG科普电影，讲述了许多深奥的数学知识，如4维空间中的正多胞体、复数、分形（fractals）、纤维化理论（fibrations）等等。

mkv格式，英语声道，双字幕（中文及英语）默认中文字幕。
在这里做个小说明，文件里已经包含了中英字幕，切换字幕由于不同的播放器有不同的方法。在此就不一一例举了，个人推荐win下使用kmplayer,linux下用smplayer.

同时提供其它语言的字幕下载地址。
第一章
第二章
第三章
第四章
第五章
第六章
第七章
第八章
第九章
结尾第二部预告
同时在这里给各位道个歉，因为个人的失误在制作的过程中，误把TR当成第九章节了，
因此发布的时候没有把第九章节发布出去，现在特补上第九章节。

同时放上第九章节的http下载地址，其它章节有必要的稍后也一并放上。
第九章节－证明 http下载地址

第一章：二维空间

喜帕恰斯 (Hipparchus)说明了两数如何描述球面上之点。
他接着解释了球极投影法：我们要如何在一张纸上描绘出地球呢？


第二章 : 三维空间

M. C. Escher 叙述那些二维生物试图想象三维物体的故事.

第三、四章：四维空间


数学家 Ludwig Schläfli 介绍了存在於四维空间中的物体，让我们见识到了一系列奇形怪状的四维正多面体。它们有著24、120、甚至600个面!

第五、六章: 复数


数学家Adrien Douady讲解复数. 以简单的术语解释负数的平方根. 变换平面, 图片形变, 创造分形图形.


Chapters 7 and 8 : Fibration


The mathematician Heinz Hopf describes his "fibration". Using complex numbers he builds beautiful arrangements of circles in space.

第九章 : 证明


数学家 Bernhard Riemann将阐述数学中证明的重要性. 他将证明一个关于球极投影的定理.

最后章节：
第二部预告

http://www.verycd.com/topics/333658/

博客李淼 http://limiao.net/ 

最近网络上不可避免地出现诺奖讨论热。学术界大多是讨论科学奖，而一般的博客讨论文学奖更多些（据我看来，虽然普通人觉得自己懂文学，其实他们不具备说三道四的资格，特别是那些文学奖作品是三流的言论，此事以后再谈）。

在过去，我们谈这些，被人称为诺奖情结。现在谈，诺奖情结还有。这种情结其实和得奥运金牌以及办奥运一样，是急于被人家承认的心态（我用得金牌而不是夺金牌，就是因为不喜欢这种心态）。这两年学术界一年一度还是谈，我想急于被人家承认的心情不那么迫切了，大家出于检讨目前中国学术界以及大环境的状态的动机更多了。

下面我贴两封信，关于亚洲人得奖的话题。第一封是英文的（感谢吴咏时老师寄来此信），鉴于一些人英文不那么好，我大致逐段翻译一下。

第一封信 作者：冯达旋

More After Thoughts on Japanese Nobel Chemistry Laureate in 2008

Osamu Shimomura (Shimomura Osamu, born August 27, 1928)

In this new century (21st century,) Japanese (not necessarily Japan because two are US
citizens) have already won EIGHT Nobel prizes. Of course there may be more this year since economics, literature and peace have not been announced yet.

Since 2000, Japanese have so far won the following Nobel prizes

（翻译：更多的关于08年日本人获得化学奖的思考

在新世纪（21世纪），有8位日本人获得诺贝尔奖（有两位是美国公民），今年也许还会有文学、和平或经济奖。2000年以后，下列日本人获奖：）

1. Osamu Shimomura of the Marine Biological Laboratory (MBL) in Woods Hole, MA, USA
(Chemistry 2008) (US Citizen) Ph.D. from the University of Nagoya.

2. Yoichiro Nambu of Enrico Fermi Institute, University of Chicago Chicago, IL (US Citizen) D.Sc from the University of Tokyo.

3. Makoto Kobayashi of High Energy Accelerator Research organization (KEK) in Tsukuba, Japan. Ph.D. from Nagoya University.

4. Toshihide Maskawa of Kyoto Sangyo University; Yukawa Institute for Theoretical Physics (YITP), Kyoto University, Kyoto, Japan. Ph.D. from Nagoya University.

5. Masatoshi Koshiba of the University of Tokyo (Physics 2002) Undergraduate from the
University of Tokyo and Ph.D. from the University of Rochester.

6. Koichi Tanaka of Shimadzu Corp. (Chemistry 2002) Undergraduate from Tohoku University and the ONLY known NON-Doctorate Nobel laureate!

7. Ryoji Noyori of Nagoya University (Chemistry 2001) Ph.D. from the University of Kyoto

8. Hideki Shirakawa of Tsukuba University (Chemistry 2000) Ph.D. from Tokyo Institute of Technology

Few nations in the world can claim to have such accolades. So how did that happen for Japanese is surely something other nations, especially those in Asia Pacific, who would like understand.

Let me offer some of my less than expert views. I hope that this would be what the Chinese would refer to as┻縥まド, or throw a stone to draw a jade.

（翻译： 不多的国家能够有这样的荣耀。日本人是如何做到这一点的？一些其他国家特别是亚洲国家一定最想知道。

让我陈述一下非专家意见，用中国的话说，是抛砖引玉。）

1. This is long time in the making. I would even postulate that it began with Ming-ji Reformation in the mid-19th century. If this is indeed true, patience seems to be an ultimate virtue.

（翻译：这是长期的事情。我猜应该从19世纪中叶的明治维新开始。如果这么猜是正确的，那么耐心是终极优点。）

2. The very first Nobel laureate came in 1949, when Hideki Yukawa of ” Kyoto Imperial University,” now Kyoto University won it in physics. It is interesting that in 1949, Yukawa was a visiting professor at Columbia University. I recalled Professor T. D. Lee told me a long time ago when I was visiting his “tiny” office in the Physics Building of Columbia University that the former occupant of his office was Yukawa!

（翻译：第一个诺奖是1949年的汤川，京都帝国大学。在49年，汤川也是哥伦比亚大学的客座教授。我记得我曾访问过李政道教授在哥大物理系的小型办公室，他告诉我那曾是汤川的办公室。）

3. Japanese scientists are mostly all home-grown. This is, in my opinion, fundamentally important because it has as much scientific as it has psychological impact on aspiring young minds. For example. of the eight since 2000, you would notice that only 2 have US citizenships. However, even for those two, they completed their doctorates in Japan which means that they already inherited the Japanese scientific tradition. For Japanese higher education, I think this must also mean that it has rendered in the last century its own universities to be as good as possible
scientifically on the world stage. In this regard, it is interesting that whatever current ranking one wants to utilize, University of Tokyo and University of Kyoto always appear on top. A good friend of mine from one of the best US universities once told me that “the definition of a great university is that it can IGNORE rankings!”

（翻译：这些日本科学家基本上都是在日本受教育的。在我看来，这很重要，因为对激励年轻人来说不仅有科学影响同时也有心理影响。举例来说，2000年之后的8位诺奖获得者，有两位美国公民。即使这两位，也是在日本获得博士学位的。这意味着上世纪的日本高等教育在国际范围内也是很好的。不论你如何排名，东京大学和京都大学的世界排名总是在前列。有一次，一位来自一家美国一流大学的朋友告诉我，一家伟大的大学的定义是它可以不在乎排名。）

4. After WWII, Japanese government, despite its ups and downs (and a very good Japanese leading physicist and friend once told me that it is mostly downs than ups,) its support of science and science education never wavered or retreated. In the second half of the 20th century, what ever Japanese built with public funds, they always built some of the best facilities, if not the best. Examples are numerous. In areas I am familiar with, such as Super-Kamiokande neutrino observatory, SPRING8, a world renowned 3rd generation synchrotron radiation facility, and so on, once they are up and running, the world scientists would converge there. I am sure that in other areas of science, such as life sciences, the Japanese Government support is just as aggressive and sustaining. In my opinion, the support of such facilities from the
Government is probably not because it wants to win some prizes (and of course prizes are good to have as icing on a cake,) but to build a landscape of supreme scientific excellence. Once that landscape is built and psychologically penetrated into the aspiring young minds, and this will take enormous resources and time (hence patience is really needed,) outstanding science will emerge! Few nations in Asia seem to have “stomachs” for patience. This is an important and profound lesson one can learn from the Japanese, in my opinion.

（翻译：二战之后，日本政府从来没有在支持科学研究和科学教育上含糊过，尽管政府有好有不好（一位日本科学领袖告诉我，大部分是不好的）。20世纪下半叶，不论用公费建造什么研究设施，这些设施总是好的，如果不全是最好的，有很多例子。在我研究的领域，有Super-Kamiokande中微子实验室，SPRING8，国际上出名的第三代同步辐射加速器。我相信在别的领域，例如生命科学，日本政府的支持是具有经略性和持久性的。在我看来，日本政府对这些设施的支持不是为了想获奖（当然获奖不是坏事，就像蛋糕上的装饰），而是为了打造杰出的科学景观。一旦景观建成，并且对有抱负的年轻人发生心理影响，这当然需要巨大的资源和时间（所以耐心是需要的），就会产生卓越的科学成就。在亚洲，很少国家有这样的耐心。这是我们从日本人学习到的重要的一课。

5. Building scientific legacy, traditions and schools of thought. This is as true in science as it is in humanities. The best example as I have mentioned yesterday is the legacy of Yukawa (Nobel in 1949) and Tomonaga (Nobel in 1972.) However, legacy is great to have if one can build on it, and with all these Japanese Nobel accolades in the new century, the Japanese were relentless in leveraging the legacy to greatly enhance its scientific excellence.

（翻译：建设科学传统、遗产和思想学派，在科学和人文上是一样的。昨天我提到的一个最好的例子是汤川（49年诺奖）和朝永（72年诺奖）的遗产。拥有遗产是了不起的。有了21世纪新的诺奖荣耀，日本将不遗余力地强化他们在科学上的杰出地位。）

第二封信 亚洲科学家有望获得更多诺贝尔奖——从2008年诺贝尔物理奖谈起 作者：潘国驹

瑞典皇家科学院7日宣布，美籍日本科学家南部阳一郎与两位日本本土科学家小林诚和益川敏英教授一道荣获2008年度诺贝尔物理学奖。就这三人获奖理由，瑞典皇家科学院称，南部阳一郎发现了次原子物理的对称性自发破缺机制而获奖，日本科学家小林诚、益川敏英因发现了对称性破缺的来源获奖。南部阳一郎等人的得奖无疑成为亚洲科学家获得更多诺贝尔奖的助推器，在增加信心的同时也备感任重道远。这篇文章我们要探讨亚洲的科学潜力以及有待改善的一些建议。

此前获得诺贝尔物理学奖的日本人有汤川秀树，朝永振一郞，江崎玲於奈，小柴昌俊。今年，我们再一次看到物理奖的工作主要是在日本本土进行的。除了物理，日本科学家在化学、文学等领域也取得了一些惊人的成果，共有15人获得诺贝尔奖，尤其是今年物理奖的工作，这表明日本或亚洲的确能做出世界最好的科研成果，日本的文化以及日本人作学问的一丝不苟的认真精神是他们成功的基石。中国百年动乱从辛亥革命、抗日战争、国共内战到反右、文化大革命，一系列的动荡，造成社会的不稳定，无疑也影响到科学研究，可庆幸的是最近30年，随着中国改革开放的不断深入，科技也跟着起飞，相信不久的将来我们会看到更多新的成果，从今年物理奖也许我们得到下列几方面的启示：

1）首先，亚洲的科学家是有能力与欧美科学家一样，做出最尖端的科研成果。因为亚洲文化和智慧在一定程度上能推动或提升科研的水平，过去日本、中国、韩国、印度等国的科学成就可以说明这一点。随着经济的起飞，亚洲的教育以及科技的投资会有极大的推动力。不过，我们需要特别注意的是，一定要加大基础研究的投资。科学研究就像一棵树，树干和根就是基础研究，只有重视基础研究，树才有可能长出树叶，甚至开花、结果。中国奥运成功，神七上天，光有这些还不够，中国同时也需要诺贝尔奖。我们不仅仅需要比尔•盖茨和任天堂，也需要基础科学。其它科目，中国的年轻一代也在奋力直追。

2）正如我在9月10日《联合早报》发表的文章中提到的，目前亚洲科技有一点需要重视的是要加强自己的信心，不要在全球化的冲击下，事事都被西方牵着鼻子走，渐渐地失去主动权以及创新精神。中国若要在未来10至20年，摘下诺奖，必须鼓励创新精神，改革相应的制度，培养科学兴趣，而不仅仅是完成科学任务。有了兴趣，创新的可能也就较大。

3）我们需要多一些自由讨论。今年6月，我去北京参加中国科学院理论物理所成立三十周年活动。中科院前院长周光召教授在庆祝会上讲话，他特别强调了中国科学界应该多鼓励自由讨论、自由发挥个人能力，这一看法很重要，亚洲国家一向受儒家思想影响，听命上级指示，忽略个人看法。所以，我认为周光召鼓励自由讨论的气氛，非常及时必要，只有民主自由的讨论，才有可能寻找出科学的真谛。

4）尽量减少繁琐的官僚制度。我也曾提到过今年得奖的南部阳一郎教授觉得亚洲的体制过于保守，尤其对年青人设置许多不必要的限制，浪费不少时间在行政工作上。他认为美国的制度比较灵活，在聘请升级等方面都比较开明，这点亚洲国家是应该学习的。我和南部阳一郎教授有过不少接触，还在1990年请他来新加坡参加世界规模最大的国际高能物理大会，并作总结性的演讲。他是一个非常谦虚但同时也很独特的人，尽管日本政府高规格礼遇他，可他就是不愿长期在日本生活工作，原因就是他怕繁琐的行政工作耽搁他的科研时间。

我们看到亚洲的科技不断地在迈进，除了建立信心之外，也要认识到自己的弱点。

（作者为南洋理工大学高等研究所所长、报业集团华文报咨询团成员）

下图是南部，贴此图祝贺他 （离开芝大后再也没有见过他）

Neil的反面教材http://blog.sina.com.cn/kiddingandserious   

看了神经科学博士饶毅最新的一篇博文：美妙的生物荧光分子与好奇的生物化学家。我认为这是一篇很好的文章，推荐你也读读。

    在个文章里提到了一种“研三病”，原文如下：

———————————————————

neil: 

    在这里说两句实话：我已经有相当长的一段时间不和别人进行学术观点的交流和沟通了，经常逛我博客的朋友也能观察出一个规律：我几乎从不在自己博客上写我有关学术的态度和观点，也极少在自己博客上谈工作。在我看来，造成这样情况的原因在于，我和自己学术圈内的朋友存在沟通障碍，以前的每一次谈话都不欢而散。最终结果是我认为他们患有“研三病”，而他们认为我患有“极度空想症”。而这种彼此对对方的定义基本上在短时间内又都是“无法验证”的。

    考虑到从事科学研究工作的人都是偏执狂，每个人都固执得要命。

    我认为大伙都还是保有自己的观点比较好。

    关于研三病，很遗憾的说，我过去的很多同学和好朋友都是因为“信仰出了问题”，或者说因为患有这种病而离开学术圈的，他们一个一个的离开曾经一度让我感到非常的沮丧和孤独，可是我却又无能为力。这对我而言是非常痛苦的事情。

    我现在所唯一能做的，就是写这样一篇博客，告诫，或者说提醒你们注意保有内心的纯洁和信仰，不要轻易的被世俗所迷惑和感染。否则，离开这个圈子离开这条道路，只是迟早的事情。