google pagerank 解说，翻译的不怎么样……
http://www.kreny.com/pagerank_cn.htm
google Matrix
http://en.wikiversity.org/wiki/Google_Matrix
最开始的paper
http://www-db.stanford.edu/~backrub/pageranksub.ps
稀疏矩阵特征向量arpack软件包
http://www.caam.rice.edu/software/ARPACK/
各种算法的评价
ftp://info.mcs.anl.gov/pub/tech_reports/reports/P547.ps.Z
http://web.eecs.utk.edu/~dongarra/etemplates/node5.html
http://www.grycap.upv.es/slepc/documentation/reports/str4.pdf
来到教室的时候，时候已经不早了，后排已无立锥之地。在此之前我多做的事情无非就是上了次厕所而已，像每一个深受文学作品和纯情电影毒害的笨蛋一样，我无精打采的四处张望着，不愿错过任何一个命中注定的她出现的瞬间。不过此时是在男厕所，所以也有一个可能是我正在焦急地寻找着一个便池。这就涉及一个资源分配的问题了，教学楼每层有两个厕所，上课或者周末，百分之八十的蹲位都会被浪费，然而遇上下课的高峰期，还是会有不少涨得通红的面孔挨个敲着紧关的小门，近乎哀求的明知故问——有人么。似乎这么做能够形成某种心理暗示，加强肛瑞脑消金兽门括约肌的机能。其实利用云计算我们可以完美的解决这个问题——将全世界所有的厕所资源统一起来，放置于地球中心——全球任何一个地方到厕所的距离是相当的。这样一来，当下课再次来临的时候，我们就可以看到浩瀚无垠的便池和蹲位，美国的日本的欧洲的俄罗斯的……而且不用担心和黄毛们竞争，至少有一半的鬼子们还在睡觉。
于是我巧妙地利用时差节约了数十倍的厕所资源，作为一个计算机系的学生，我对这个想法很满意。
不经意间我注意到了一个白色外衣的女孩。我只能说她很美，搜肠刮肚想出的种种词句似乎都无法准确描述刹那间怦然心动的感觉。而且我好这口并不等于你也好这口，就像莫奈被认为技法只是小学生水平的《日出》，我觉得它最令人印象深刻之处就在于盯着这样的作品不会像盯着令人眼花缭乱的现代派作品一样产生眩晕的感觉。
总而言之，如卡尔维诺所说，形象一旦被词句固定住，就被从记忆中抹去了。我想把她保存在脑海中，所以不愿统统写下来。
她这个时候坐在最后一排同行的两个女孩儿中间，依上文所述，后排已水泄不通，我只好找了个中游靠窗的位子。此时我是多么懊恼刚才去了不该去的地方。
没有什么比在一个秋日的午后听马XX哲学基础更无聊的事情了。讲台上干瘪的中年人自己到底是信什么的还真难说，第一节课最常被提到的名字是卡尔波普，其还饶有兴致地推荐我们去看《开放社会及其敌人》以及《历史决定论的贫困》。当然为了防止出现什么不可预知的问题，他还最后特地关照地补充了一句，如果没有足够的辨识力很容易被卡尔波普绕进去。不过我很怀疑到底有没有人会真的去看。
这样百无聊赖的时刻，背单词或许是个不错的选择，但无论是王小波的《红拂夜奔》还是卡尔维诺的《树上的男爵》，都无法使我静下心来。午后的阳光斜射在木制的桌面上，泛黄的纸页显得如此刺眼，文字仿佛被一重热气笼罩着，目光一行行扫过，字迹和背景混作一团，渐渐模糊。我只觉得浑身上下燥热难耐，脑子里一片空白。
我假装环顾四周，和一切没人听的课一样，也就是些低垂的疲倦的脑袋、若有所思的眼神、微分方程作业和单词书。这些并不是重点，我每次扫视的终点都会落到那个白色影子上——这才是我的真正目标。她趴在桌子上的时候，我也感觉全身舒展开来，她在看着什么的时候，我就想像那本书该是什么。会是王小波和卡尔维诺的么，或者陀思妥耶夫斯基的也行。如果她也喜欢《捏朵奇卡涅茨瓦诺娃》那就再好不过了。
这就是我第一次见到她时的场景，那时起我就意识到，这个故事就像个可识别问题的图灵机，对于小雪这个输入，要么accept，要么我就要永远运行下去。
今天yo2复活了，我很开心。
可是昨天我的心情很糟糕，因为课程设计的成绩出来了，参考了其他几个同学的程序之后我认为这个结果很扯淡。甚至一度动起埋伏在xxx老师的办公门口让后揍他丫一顿狠的的念头。可是转念一想，xxx老师不是至少装作和我很熟的样子么？于是我简直可以想象到那两个啥都不知道的烟酒僧乱给分的情形。
其实我完全可以把这个当作浮云的。就是这些浮云让我产生去外面见见世面的想法，可是外国人却天真的将GPA当作重要标准。
这个悖论真他妈让人抓狂。
《我们的祖先》的确是本好书，尤其是《树上的男爵》。
男爵认为，要看清地面上的生活就要和它保持距离，所以他选择了树上的生活。
也许总有一天，我会被逼到树上。
热爱大地——生活在树上——升入天空
当一支非洲球队拥有纪律性的时候，他们是多么可怕！
面对南非的穆里尼奥式打法，墨西哥队的应对方案是——佯攻左路，转移右路；中路虚晃，转移至右路；45度长传转移右路……于是我们看到墨西哥队的12号一 次又一次的将球传入人群中，最后被各种破坏……丫的墨西哥你什么时候改一根筋了，太让我失望了！终于有一次，多斯桑托斯溜到了右路，选择了内切，一脚劲射 被扑出！墨西哥队开窍了！！！然后12号又一次又一次地将球传入人群中被破坏，不对，现在他连球都接不到了……
好在墨西哥队的定位球依旧是那么犀利，不过就是进不了，丫的就是进不了！
下半场，南非队做出了换人调整，换下了左边后卫15号，不过我觉得挺奇怪的，这哥们表现的挺出色的，而且他留在场上，可以让墨西哥队继续传球到右路，然后 12号跟他一对一…… 这个时候墨西哥队也做出了换人调整，他们终于换下了12号，解说员表示墨西哥主教练一定嘱咐他们要多打左路，于是他们一次又一次地将球传到了南非队的左 路……
南非队在全场球迷的呐喊声中，终于利用一次反击机会打入精彩的一球。此时墨西哥队似乎一下子被打懵了，场面混乱不堪……镜头切换到教练席，墨队助教向主教练不断耳语。此时，墨西哥队换上了本场比赛的秘密武器——布兰科！！！
是的，这个名字怎么这么熟悉啊，然后我发现这个布兰科就是98年世界杯的蛙跳男……可是蛙跳男再也跳不起来了，此后的比赛中貌似一共给了他三次特写，两次传球失误，一次越位，然后他露出天真无邪的灿烂笑容……
好吧，这事如果放在中国，国内报纸一定纷纷揣测现在国家队出场的价码是多少。
其实布兰科的作用这个时候才真正体现了出来，当他上场之后，南非人突然产生了11打10的错觉，防线也在不知不觉中松动了……前场任意球，传到后点，墨西哥队竟有三名队员无人盯防，于是马克斯轻松射门得分。
我们接着谈到错觉，其实这也不一定是错觉，之后的比赛竟然貌似真的对攻了出来。此时非洲球员无比强大的身体素质体现了出来，直接长传找前锋，而前锋竟可以随便在两名后卫下拿到球，最后时刻的一脚门柱另全场唏嘘不已……
除此之外不得不提的是，墨西哥队你丫一般队员都找些小矮人就算了，连个守门员都找个防高球这么挫的，你丫到底想不想进16强？想不想进16强？想不想进16强？！
网上盛传一胡东篱把酒黄昏后适”打牌日记“，内容如下：
7月4日
新开这本日记，也为了督促自己下个学期多下些苦功。先要读完手边的莎士比亚的《亨利八世》。
7月13日
打牌。
7月14日
打牌。
7月15日
打牌。
7月16日
胡东篱把酒黄昏后适之啊胡东篱把酒黄昏后适之！你怎么能如此堕落！先前订下的学习计划你都忘了吗？子曰：“吾日三省吾身。”不能再这样下去了！
7月17日
打牌。
7月18日
打牌。
所以我今天的内容是：
3月9日 不能打实况了！
自打被“连坐”之后，便没怎么写了。毕竟为了只言片语而翻人比黄花瘦墙终究是件得不偿失的事。况乎就算我留下了，谁来看呢？骨子里的惰性又战胜了架设一个独立blog的想法。索性就在这儿重新开始吧。
怀着良好的自我感觉参加了第一次班会，然后得知本专业的同学纷纷脱胎换骨，绩点猛增，名次竟然掉到了30+。原本以为本学期再发奋一下，兴许还能拿 点奖学金的愿望面临着艰巨的挑战。考虑到4.5以上的有20+人之多，我必须在本学习修无穷多的学分，并且得到无限接近于5的绩点……
于是干脆就凭兴趣选课好了，《魏晋文学》看起来不错。刘老师四十岁上下，精神抖擞，气宇轩昂。环顾四周，却立马蔫了下来。用他的话来说，就是“我从 没上过这么少人上的课”……此时一位迟到的同学走进了教室，于是听课人数立马增加了七分之一！待情绪稳定下来，他还是不得不跟我们这半打牛弹起了琴。谈什 么呢？谈读书。一般看到这个题目马上就感到乏味和无聊的一定是没读过什么书的人，因为我没读过什么书，所以我也感到乏味和无聊。刘老师似乎也察觉到了这一 点，于是做了个现场调查，你们有多少藏书？我状着胆子报了个两位数，发现还不算少的，可是等轮到山大过来的一位交换生同学的时候便立马自愧不如了。只见这 位其貌不扬的同学淡淡地说了个“五六百”，虽只三字，谈吐之间的淡定和从容却已经显露无遗。
听着听着，我觉得这个刘老师并不是心目中那种“老学究”和完全没有理性思维的“抒情文科男”形象。这厮不仅读汉唐魏晋，也读鲁迅王小波。进过财政 部，当过主持人，但还是从了内心的感召，回归文学，选择了当了这么个小教授。用另一个老师的话来说，这是王维式的田园风格，而不是陶渊明式的田园风格。陶 渊明还没有得，就舍了。而王维十九岁就中了状元，声名和财富，都已早早到手，是得了之后再舍。读书能带来什么？黄金屋和颜如玉都是来骗你上当的。但读书， 至少能带来判断力。在这一方面，刘老师觉得韩寒要比“含泪余秋雨”强上不少。一个四十岁的大叔，对韩寒和王小波了如指掌，这是一种什么样的精神？
说到王小波，就不得不说一下寒假才看完的《红拂夜奔》。人力长安里的每一个人，不都像是活在洛阳城里么？从这个角度看，刘老师又多少有点李卫公的风 范，毅然决然的奔了，不知道有没有个如红拂般的美女相伴。我们也像是活在洛阳城里，服从领佳节又重阳导上的安排，接受规划好的命运，不需要，也不应该思考。我也像卫 公一样有着千千万万个脑子，每个脑子都能独立工作，冒出无数乱七八糟的想法。是的，我只是想让生命变得有趣一点。
所以，决不妥协。
本来不想比的，可是后来想到做hdu保持状态是我提出来的方案，于是只好做个表率了。
A 题 00:58:51 (-5)
上来一看就是一道水题啊。我平复了兴奋的心情之后，在10min交了一次。然后发现是求方程是否存在非负整数的解，而不是是否有整数解。于是赶快想公式，回忆起了sgu那道equation，号称时间漩涡啊。终于得到了$latex x=x_0-bt$和$latex y=y_0+at$这个通解的公式。于是又要处理正负数的向下和向上取正整问题，各种WA。崩溃边缘发现好像会溢出，改成INT64之后终于通过。真是悲剧啊。
E题 01:19:50
落后的好处就是可以跟题。发现EF都有不少人过，于是看题。E题给定一棵树，求将指定节点连接的最小花费。很明显，既然是棵树，那么方案就有且只有一种了。随便找一个要求的节点BFS，然后标记一下经过的边。于是1Y。信心大涨！
F题01:38:14(-1)
回过头来看，这一段时间我出题的确挺快的。不过也主要是因为太水的问题。F题给定一列灯的状态，已知开关可以使连续的K个灯状态改变，求最少开关数使灯全亮。从左到右，若是关的，则添加一个灯。非常容易的贪心。WA了一次，重看题，发现有K=0这个trick。改了之后就A了。此题已过，我竟然进了前10。不过这个时候，其他的题目都没有什么人做，必须要自己开题了。
B题 03:23:12(-9)
考虑到G和I是resty出的，我就先不做了。然后看B和C，C嘛，好像要平面几何的，我最讨厌了，于是决定挑战一下宇宙核武的B题。给定区间[x,y]，求其中B进制下数位和为M的个数。或者是求[x,y]中，B进制数位和为M的数。第二问二分一下答案就变成了第一问，而第一问化归一下就是这么个问题——统计0~x中B进制下位数和为M的数的个数。很快就想到了DP。然后就是稍微推一下。结果事实证明我一碰到这种需要注意+1-1的数学题就搞陀不清。A题的悲剧再次上演，我各种迷糊的写完了之后竟然TLE了。大惊！居然会TLE。找了很久发现二分的时候(x+y)/2会溢出……于是进入了WA时间，其中经历各种问题，比如0~x，我没把x算进去，还有x居然会大于y，必须要swap（阴险啊！）！以及各种低级错误。为了防止溢出又都改成了int64，各种绝望后，终于在第10次提交的时候AC了。确切的说是第11次。因为有一次不小心交到了C上……
C题 03:48:02(-1)
其他的题目实在不好做，于是还是来搞C。结果越想越清楚，越想越清楚。所谓投影不过就是坐标正负值换一下而已。写的很带劲。越看越简单，不断地自我陶醉中……最后竟然1Y！（-1是因为B交错了……）
这个时候，某小弟发来信息，说H他已秒。考虑到G和I我可以要标程，那我岂不是可以马上连过三题，扬名立万？！经过激烈的思想斗争之后我决定还是光明磊落的自己做。可是看完GH，我又犹豫了……
不会做啊不会做啊，只好狂刷rank，发现排名还可以，居然有第六，要是再做一题……
G题 04:55:58(-2)
还剩半小时憋不住了，找resty要点提示，结果一句二分答案，立马醍醐灌浆！我激动万分地写完之后，wa了……还好代码只有60行，又交了一次后，发现打错了两个变量。于是，4：55，AC！
最后竟然名列第三，由于A和B的脑残，罚时快到radiant的两倍了……
剩下的题目，D题太bt了，还涉及了第二类stirling数，各种精度要求，无人能过。H题二分答案加网络流，虽然我还是不会做……I题ws的宽搜，不告诉你有10w组数据，就算预处理了还要拼人品。
名字很拽吧？其实丫的就是刚刚发生的一悲剧……
话说中午我从食堂路过，喜欢盯各种旮旯角落的嗜好让我注意到了一个不起眼角落里的红色 海报。定睛一看，夸张不修边幅的黑体字，随便处理了一下的背景，不用看肯定也知道是学术相关的……哟，还是咱电信学院的，哟，还是分布式计算的，哟，还是 普林斯顿的！看到Princeton University，USA的时候，我还特地拼写了一下，确信不是“李鬼”。总算有牛人来本校做报告了，我感动的热泪盈眶，要知道，作为一个黄渡理工的 本科生，实在是很难在这个地方感受到什么学术氛围。好不容易上次来了个MSRA的院长吧，还尽谈些经济危机的事……倒是诸如十大歌手这样的比赛，可以看到 满天飞舞的海报，甚至现场海选？还音箱评委整的个超级女声似的。最了不起的是研究生会（我到了嘉定才知道有这么个组织），今天迎新晚会，明天毕业晚会，光 棍节还有赤裸裸的速配活动，平均每两个星期就能看到它们的横幅……我说研究生才几年啊？你们真的是来“研究”的么，还是来研究“生”的……（本人仅仅针对 其中一小撮，广大正直有爱充满理想的研究生同学不要攻击我……）
这一不小心就扯远了，话说我看完海报之后，瞄了一眼日期，23日，这不今天么？晚上吃完饭了再来关注一下。
可是数论课的时候，我越想越不放心，咱这偏僻地方，人家能在这过夜么？万一是下午的怎么办？于是我忧心忡忡的上完数论课，跑到电信楼确认一下时间——1：30至3：30。悲剧啊！
好 不容易来了个普林斯顿的，就这么两张寒碜海报就算是通知了，你说除了我这种有诡异癖好的人，谁知道啊？没办法，Huangdu Institude of Technology就是这样，似乎只对各大招聘会感兴趣，而且本校学生就是牛，基本上问的问题都是多久可以干到管理层，或者干脆说你们管理层招不招 人……
好了，下面说费曼。为啥说费曼了，因为上面这个问题让我想起他一个事，概括的来说就是——“哥只想做个普通人，千万别告诉别人我来了”。出自《别闹了，费曼先生》，摘录如下：
诺贝尔奖后遗症
我有三四次这种受惊的经验，像个白痴一样，一时之 间无法意会过来。当伯克利大学邀请我去做物理演讲时， 我准备了一些颇为专门的题材，预期听众都是物理系学生。 但是等我到达会场时，发现偌大的演讲厅里挤满了人！事 实上我知道，懂得我演讲内容的人不可能挤得满一个演讲 厅的！我的问题是，我总是希望能让听演讲的人开心，但 是如果每个人再加上他们的兄弟姊妹都跑来听，我就没辙 了，因为我不知道究竟来了些什么人！ 学生明白我没法简简单单地跑到一家学校，跟物理社 的学生演讲后，我说：“我们来想一个很沉闷的题目，取 个很沉闷的教授名字，只有那些真正对物理有兴趣的学生 才会来的，这才是我们想要的听众，好不好？你们不要大 做宣传。” 于是，校园里贴了几张海报：“华盛顿大学华伦教授 将于5月17日下午3点于D102教室，发表质子结构的演讲。” 等我上台后，我说：“华伦教授临时有事没法来演讲， 所以他打电话给我，问我能不能来谈谈这个题目。刚巧我 对这个题目也稍微作过一些研究，所以我就来了。”简直 是天衣无缝。 但是不知怎的，这个社团的辅导老师发现了我们玩的 把戏，大发雷霆。他对学生说：“你们知道吗？如果大家 知道费曼教授要来，很多人都会想来听他演讲。” 学生解释：“正是因为这样，我们才那样做呀！”但 是教授仍然大为光火，因为他事前对这个玩笑竟然毫无所 悉。 知道那些学生碰上了这么多麻烦，我决定写信给那位 教授，向他解释这一切都是我的错，是我要求他们依我的 安排，否则我不肯演讲，是我叫学生不要告诉任何人，我 说我很抱歉，请原谅我等等。这就是我得了那该死的奖之 后，所要忍受的麻烦事！ 去年阿拉斯加大学的学生邀请我去演讲，除了地方电 视台的访问之外，整个过程都十分愉快。我不想接受采访， 那没有什么意思。我来是要对物理系学生演讲，仅此而已， 如果城里每个人都想知道我讲了些什么，学校报纸刊登报 道就够了——我得了个诺贝尔奖，大家还是必须来采访我 这个大人物的，对不对？ 我有个很有钱的朋友，他提到这些捐钱设立奖金或赞 助演讲的人时说，“小心观察，看看他们到底做过什么违 背良心的事情，需要靠这来减轻罪恶感。” 我的朋友山德士（Matt sands）有一度想写一本叫《 诺贝尔的另一个错误》的书。
最 后再说说分布式计算。话说这次这个Princeton的就打算说说他们组研究并行计算的一点点心得，他们的水平现在可以并联24台计算机，让计算速度提升 13倍。这让我想起一个什么事呢？上次人工智能课一未知专业同学眉飞色舞地跑我跟前，那感觉就像前两年大牛市菜场里买菜小贩说“我有内部消息的”的神情， 得意洋洋地告诉我一大秘密！他高傲的把研究出了千万亿次计算机的国防科大鄙视了一遍，然后告诉我什么千万亿次计算机啊，全是用的intel和amd的 CPU，一点技术含量都没有，美国随便找个本科生都能把它焊出来……
做为一个焊不出千万亿次计算机的中国本科生，我感到压力很大。
题目大意：
给定一个正整数数列(长度小于10万)，请你划分成若干段，使得$latex sum[1]>=sum[2]>=$ … $latex >=sum[k] $ 。
求最大的段数，即max(k)。
如 $latex 10 {\ } 10 {\ } 1 {\ } 9 $，即划分成$latex |10 | 10 | 1{\ } 9 | $ 使得 $latex 10>=10>=(1+9)$
题解：这题和经典的最长非降子序列非常像，但是规则变成了子段和非降。细细一想，还真难啊。首先不难想到一个贪心的算法——假设最后一段只取最后一个，然后从后往前扫描，遇到大于等于前一段，则划分一段，接着向前扫描。然而，反例很快就被找出了，比如说我给的例子……
接下来搜索到了如下一个算法：
用$latex g[i] $表示$latex i-n$的数字所能划分出的最大段数，$latex f[i] $表示当$latex g[i] $取到最大值时，最左段的最小和。那么不难发现递推规则如下
设$latex j>i$，则当$latex g[j]+1>g[i] $且 $latex sum[i..j-1]>f[j] $时，
$latex f[i]=sum[i..j-1] $ 而 $latex g[i]=g[j]+1 $
或者是$latex g[j]=g[i] $且$latex sum[i..j-1]<f[i] $且$latex sum[i..j-1]>f[j] $时（即同样高度，最左段的和更小）
$latex f[i]=sum[i..j-1] $
由于$latex g[i]$函数是非升的（显然，我们只要把第$latex i$个数字放到最左边一段去，就可以构造出一个段数为$latex g[i+1] $的方案），而$latex sum[i..j]$随着$latex j $的增长而递增的（左端点固定 ，右端点递增，和肯定递增）。那么我们从小到大枚举$latex j $，第一个能够转移的j必然就是最优的。因为此时$latex g[j]>=g[k](k>j) $，且$latex sum[i..j-1]<=sum[i..k](k>j-1) $。
于是我们就得到了一个$latex O(n^{2})$的算法。然而题目中的n高达十万，所以我们还得继续优化。
设$latex sum[i]=sum[1..i] $，则转移条件是$latex sum[j-1]-sum[i-1]>=f[j] $且 min(j)，我们把$latex sum[j-1]$移到等式右边，就变成了$latex -sum[i-1]>=f[j]-sum[j-1]$，由于i是递减的（我们从后往前做），所以$latex -sum[i-1]$是递增的，所以当某个$latex j$，使得$latex f[j]-sum[j-1]<=-sum[i-1] $，那么所有的对于所有小于$latex i$的都会满足。于是对于所有的$latex f[k](k>j)$，都没有必要保留了。于是，我们可以用一个双向队列来维护。复杂度降到了$latex O(n)$。
可是，有一点我们忽略了，就是这个算法是基于一个猜想的，那就是同一个数列所有划分成 n 段的方案中最小最左段和长度必然大于等于划分成 $latex n+1 $ 段的最小最左段和。否则，可能会出现这样一个情况，由于我们$latex f[i]$是基于划分成$latex g[i]$段的，假设$latex [i..n] $划分成$latex g[i]-1$段的方案中，最小最左段和为$latex w$。若$latex w<=sum[1..i-1]<f[i]$，那么我们就会漏掉从i处断开，划分成$latex g[i]$段着一种方案。若$latex g[k](k>i)$都小于$latex g[i]-1$，那么我们就得不到正确答案了。
所以我们必须证明$latex w>=f[i] $。
即将任意一个数列，划分成n段的最小最左段和$latex s_n$大于等于划分成$latex n+1$段的最小最左段和$latex s_n+1$。
我们用数学归纳发来证明，首先显然$latex s_1>s_2 $。
假设$latex s_k>s_k+1$，那么我们考虑如下一张图：
图1
假设我们把数字$latex x $看作数轴上长度为$latex x$的线段，那么原问题等价于在这一连串竖线中选取若干个，使得隔开的区间长度非升。
我们害怕出现的就是如图所示$latex C $部分>$latex A $的情况。
如果出现$latex C>A $的情况，我们就沿虚线重新划分。那么就变成了如图2的情况。
图2
我们将$latex D$段和$latex E$段合并。那么构造出了一个新的$latex k+1$方案。其中$latex A=C$。我们把$latex A$和$latex C$去掉，那么就变成了一组$latex k-1$和$latex k$的方案。由已知条件得$latex B>=D+E$。又因为$latex C=A>=B>=D+E$所以新方案也是合法的，但是最左段和（即A部分）比原来的要小了。于是和已知条件矛盾。
所以图一中的$latex A>=C$。于是命题得证。
特别鸣谢：无所不能的刘城同学(Tongji) 总有有趣题目的陈聪同学(ZJNU)
转载自：科学松鼠会 songshuhui.net
木遥 发表于 2009-12-10 11:20
木遥按：这是美国数学家 John Baez 今年 11 月 14 日在他的网页上贴出来的一篇文章（原文）， 很快引起了许多人的兴趣。标题中的“根”是指数学中一个多项式的解。如果你还没有忘光你的高中数学课，就应该知道下面这两个事实：任何一个多项式在复数域 中必有根，并且每个复数都可以在复平面上对应于一个点。这样，给定一系列多项式，我们就可以把它们的根都画在复平面上，从而形成一些特定的图案。请放心， 即使你对多项式毫不了解，也不会妨碍你欣赏这些图案之美的。也许你曾经听说过经典的曼德布洛特集合（Mandelbrot set），那你很容易就能在这里看到某些相似之处。所不同的是，人们对这些新的图案还所知甚少。
下面所有括号中的文字都是我所添加，以帮助不熟悉复平面的朋友了解所说那些的点的位置。每幅图都可以点击放大。
点击图片可以看大图。二次多项式的根是灰色的，三次多项式的根是青蓝色的，四次多项式的根是红色的，五次多项式的根是黑色的。横轴是实轴，纵轴是虚 轴，中间的大洞的中心是原点。两侧小一点的洞的中心是 ±1，在 ±i 处和 1 的所有六个虚根出也各有一个小洞（即中间那个大洞上下不远处对称的那些小洞）。
你可以在这里看到许多迷人的图案，给人的感觉是这些整系数多项式的根在竭力避开那些整点和单位根似的，──除非这些整点和单位根本身就是多项式的根。如果你把图案放大，可以看到更多细节：
在这里你可以看到，在 1 这个点所在的空白区域周围环绕着一些美丽的羽毛，在 exp(iπ/3) 这个点周围有一个六瓣的星形（即左上角那个梅花形状的洞），还有一条奇特的红色连线把这两个点连接起来，还有很多其他的点周围的星形的洞，诸如此类。
人们应该开始研究这些东西才对！让我们把所有系数为 -n 到 n 之间的整数的 d 次以下多项式的全体根构成的集合称为 Christensen 集 Cd,n，很显然当 d 和 n 越大， Cd,n 这个集合就越大，并且当 n 趋于无穷大时这个集合趋于布满全复平面。如果固定 d, 令 n 趋向于无穷大，那么我们就能得到全体有理复数；如果令 d 和 n 同时趋于无穷大，那么我们就能得到全体代数复数。于是一个有趣的问题就是，如果我们固定 n，令 d 趋于无穷大，会得到什么呢？
在上面这些图片的鼓舞下，Sam Derbyshire 决定绘制一些分辨率更高的多项式根的图片。试验了几次之后，他觉得他最喜欢的是系数为 ±1 的多项式。他把所有 24 次以下的这样的的多项式的根绘制成一副高清晰度的图片，这些多项式一共有 224 个，其根大约共有 24 × 224 个，也就是大约四亿个。他用 mathematica （一个数学软件）花了大概四天时间才计算出所有这些根，得到了大约 5G 的数据。然后他用 Java 语言生成了这幅美妙的图案：
颜色表示根的密度，从黑色到暗红色到黄色再到白色。上图是低分辨率版本，这里有一个 90M 的文件可供下载。我们可以放大一点看到更多细节：
请注意单位根周围的那些小洞，还有圆弧内部的那些羽毛。为了更清楚地观察，我们把下面这些标记出来的区域放大：
这里是 1 这个点处的那个洞。（即上面最右边那个标记出来的区域。）
中间那条白线是实轴。这是因为有非常多的多项式根都是实数。
然后这里是 i 这个点处的洞。（即最上面那个标记区域。）
这是 exp(iπ/4) 这个点周围。（差不多位于 1 和 i 正中央。）
请注意，根的密度在接近这个点的时候会变大，然后又突然变小。可以看到这些密度所形成的微妙的图案。
但是更漂亮的是当我们来到单位圆内部时的那些羽毛状图案！这里是实轴附近的样子，这个图的中心位于 4/5 点处。（右边数第二个标记区域。）
在 (4/5)i 点处的样子就截然不同了。（从上数第二个标记区域。）
但是我觉得最漂亮的还要说是 (1/2) exp(i π / 5) 这个点周围的区域。（剩下的那个标记区域。）这幅图生动的展示出，在我们的数学研究中，规律性是如何从一团混沌中逐渐成型的，就像从薄雾中隐约显现出来一样。
这里有太多东西需要解释了，每幅图片都至少需要一两个定理来描述。如果想看到更多的这类结果，可以参见：
Loki Jörgenson， 限定系数多项式的根 以及 相关图片。
Dan Christensen，整系数多项式的根的图案。