===============

复旦计算机系楼223室原来是理论教研室.

 

理论组教研室里有很多回忆,

 

教研室分成2个屋,外面自习教室,有个不大的书架,一块大白板,里面是机房.

朱老师搬去了逸夫楼,以后教研室就很少有人打扫.

 

教研室有本TAOCP,里面夹着Knuth用铅笔给朱老师写的信.

 

刚来时我从书架时抽下一本大书就从第一页开始看,我说怎么一上来就看不懂,后来知道是STOC的Proceeding.

 

一般师兄师弟都不来,就我一个人,大白板就我一个人乱写乱花,一般是一堆图和公式, 兴致来了就画上一幅. 有一次速写了一个窈窕淑女,忘了擦掉,赵一鸣的密码小组来上讨论班,都说我画的好看.

 

教研室里夏天很多蚊子,有一次我在那里通宵打英雄无敌被咬了无数个包.

 

又是某天师兄师弟都不来,我找来3个人来机房里打Starcraft 2v2, 我同学都说教研室比较象网吧.

 

我曾经在教研室的书架上翻出不下5篇寄给朱老师的声称证明了P=NP的论文,短的十几页,长的上百页.

...........

摘录出我毕业论文里致谢的一段话,总结一下学习TCS的感受:

"难忘在复旦的三年光阴。我从一个城乡规划专业的本科毕业生，踏入我并不了解的理论计算机领域，这个令人不断感受到惊奇与美丽的领域。仍能回忆起钻研白皮书时的痛苦，和同门为一个问题面红耳赤的争论，长时间冥想而毫无进展的烦闷，灵感偶得时的兴奋和漂亮的证明给我的惊喜。这研究中探索的痛苦与艰辛交织着成功的兴奋与喜悦伴着我度过了这难忘而美好的时光。"

 

我想说说我的研究的感受.

 

客观的来讲,以国际的水准来衡量,我的研究连优良都不算,但在国内却可以说是不错的.

 

对于一个初学者来说首要条件是打一个相对好的基础,而最重要的事情就是找到可以入手的问题.这个问题既要有意义,又不能太简单,但又不能难的做不出. 问题的选择可以依赖于导师, 但是有时根据自己现有的知识,评感觉和尝试会有更好的效果. 我导师朱洪老师经常提出一些巨大的Open Problem, 大部分是那种解决了可以直接发STOC或者Journal of ACM的, 有些是那种重要的解决了就可以拿哥德尔奖甚至图灵奖的问题, 说实话我也认真尝试过, 无奈天资实在有限只得作罢, 而另一个导师Rudolf一开始给了我不少他擅长的online algorithm的问题, 无奈我对online algorithm也找不到感觉, 专研了很久也没有成果. 最后在看了很多书,了解了很多方法后,我的研究开始集中于图论的近似算法.
我以前学过美术,对图形有着很好的直觉,所以我很喜欢图论.我这个人做事不认真,不追求完美, 近似算法正好符合了我的天性.

我觉得对我影响最大的是第一篇基本上全部由我自己完成的paper. 这篇paper是研究最小生成树的,只不过权值是边权的和和所有内点(非叶子结点)的权和. 这个问题是我的一个师兄在讨论班上提出的,并且给出了一些算法. 那个时候我正在看Vazirani近似算法的书, 并且在研究一些facility location问题的paper. 我开始试着用目前掌握的方法去研究这个问题, 结合了不少技巧,最后得到了改进的结果,为了完善这篇paper,我又考虑了很多情况,分别给出了几个适用不同情况的算法, 最后形成了一篇比较完整的paper. 我很幸运的是我正在学习的技术正好应用在了这个问题之上, 最后导致了这个问题的解决.这给了我一个好的习惯,就是脑子里永远记着几个没解决的问题, 在每学习一个新方法时, 都试着去联系这些问题看看是否有帮助, 恰当的方法往往直接导致了问题的解决.

 

第一篇国际会议文章的发表对建立自信有很强的作用, 我上面说的第一篇paper, 最初结果不完善的时候投到了Approx, 一个很不错的会议,后来被拒了, 做理论的人在好的会议上给的评语非常的直接,就是你这篇paper不够创新或不够重要或不interesting, 很容易给初学者很大的打击.后来我们改进了这篇文章,最后中了一个比较差的会议,但是就只是这个,也给了我很大的安慰,让我知道付出是有成果的.

 

我来说说交流的作用,交流的直接作用是增加知识面,另外交流的作用是使得研究变的活跃,使研究不是那么孤独和枯燥,交流有很多形式,比如听讲座,讨论版,或者是几个人一起闲聊或者想问题. 另外一个交流的重要作用就是找到当然的热点和可以着手的问题, 而这些问题多处于前沿且尚未结局, 不会出现在经典的教科书里, 如果交流时你发现一个和自己背景相近的人在研究某一问题, 那么首先这个问题是让人感兴趣的,另外很大可能是这个问题是有希望解决或改进的,那么你不妨花些时间来考虑一下这个问题.我的几篇文章都是通过这种办法得到的问题. 另外,很多人在做完报告后会提出一些他尚未解决的open problem或者further research, 也是可以试试的.能够用一个人熟悉的知识解决他自己不熟悉领域的问题是令人兴奋的,也是交流的魅力所在. 我在港科大有一次听报告,是关于Game Theory的,我不是很熟悉,报告人最后提出了一个Open Problem,他把game theory的问题转化成了一个图论问题,但不能解决这个问题,报告人在game theory有很好的工作, 但可能并不太熟悉图论, 而我正好对图论有一些研究, 报告的当天晚上我就做出了一个猜想并给了证明解决了这个问题,尽管后来发现当时的这个证明有漏洞,不过猜想是正确的,我很快弥补了这个漏洞,就这样很愉快轻松的与报告人合作了一篇paper.

当有几篇文章已经发表,并且同时有若干问题在自己的研究计划中时,研究就可以说走上了正轨,就已经有了自己的研究感受,知道该如何继续了.

 

数学家Holmas的一篇文章<<怎样做数学研究>>让我很有体会.他说"我喜欢做研究，我想做研究，我也得做研究，我却不愿做下来开始做研究—我是能拖则拖迟迟不肯动手." 他把除了集中注意力思考问题外的事情全部比喻成"削铅笔",他总是希望把铅笔削好再集中精力思考问题,并且把"削铅笔"当成是很好的休闲.我不是一个懒惰的人, 在我最努力的第一年,我也只不过每周集中精力学习不到25小时,到了三年级我更是每周连10个小时都不到.我花费了大量的时间在削铅笔上,比如Starcraft, Warcraft, DotaA,和哥们喝酒腐败,泡bbs农民版和睡觉,甚至花20分钟看Proof from the BOOK上的一个精彩证明都是很好的消铅笔活动. 我不得不承认我的铅笔很多,压力又很小,花了太多时间在削铅笔这上面,我希望以后到了压力大点的地方会有改观.

 

在最初的阶段,我把大部分精力都放在打基础上面,我把算法导论上不懂的章节都看了一遍,并做了很多习题,并且看计算理论和复杂性白皮书.后来第2个学期,就开始看一些进阶的书比如approximation algorithm和randomized algorithm等等,这个时候我就开始分配一些时间看paper和想具体的研究问题上来,我的第一篇文章就是在这个时候完成的.而到研2的时候因为有不少会议要开,就变的浮躁了不少,不过我仍然将学习和自己研究的时间分成50/50, 再以后我都始终保持学习新的知识, 除非有时在突破某个问题, 一段时间的思考集中到顶点的时候我才将全部时间用来研究.我觉得孔子的那句话很好"学而不思则罔,思而不学则殆".

 

说说TCS的的强校和强人吧,这可能对想出国深造TCS的同学的选校和陶瓷比较有帮助.我又不得不申明下我的观点可能会片面,只希望能有帮助

.

先说说美国.

我在这里就不介绍美国计算机的四大强校CMU MIT Berkeley Stanford了,我想任何人拿了这里的offer都不会犹豫的接受的,如果有人犹豫那么可能就是跟超牛的导师了,这样肯定也不需要往下看了...不过这4个里面感觉Stanford的TCS相对弱些,因为Knuth退休中,Motwani主要精力现在在Data Mining上,不过加州的阳光一样吸引着无数的人.

 

不得不提Cornell了,是我的dream school,不过无情的把我拒掉了,里面很多的大师级人物,这里的系头是Eva Tardos,女中豪杰,不让任何须眉,拥有很多可以让一个名不见经传的人一夜成名的工作. John Kleinberg, TCS里的"当红小生", 美国天才奖得主,有很多富有创造性的工作,他研究热门的社会和信息网络,这些工作有组于在现在的internet上寻找规律和设计算法. 而且Tardos和Kleiberg合写了一本<<Algorithm Design>>,是本科生的教材,好像也开始流行起来,中国大陆有影印版,我没看过.还有Shmoys和Williamson,这两个人主要方向是组合优化和近似算法,Shmoys最有名气的工作应该是在Facility Location问题上,他用Rounding and Filtering的办法给出了metric space上的第一个有常数近似的算法(with tardos and Aardal), 被引用无数.Williamson最著名的当属他的将semidefinite programming应用于近似算法了(with Goemans),这个方法写入了这之后几乎所有的近似算法教科书和lecture notes. 这里的Phd毕业生最后到美国Top的学校教书,比如Tardos的学生 Tim Roughgarden好像现在在Stanford做Assoc Prof.

 

其中Princeton理论组拥有无限豪华的阵容, TCS家喻户晓的Arora,新秀Moses Charikar,做计算几何的Bernard Chazelle,图灵奖得主Robert Tarjan. 再加上Princeton显赫的名声,具有无穷的吸引力,我认识的一个MPI的德国学生拿到了基本所有Top学校的Offer,最后选择了Princeton.

以上这6个可以算顶级的TCS理论组.
我下面介绍些理论比较强的学校,这些组在美国计算机系里就叫Theory Group.

 

我首先想到了Rutgers University, 这个学校是DIMACS(center for Discrete Mathematics and TCS)的中心,这个中心里笼络了新泽西州(包括princeton)很多的大牛. 这个学校的理论组更是拥有十多个Faculty, 说几个我听说过的. Endre Szemeredi, 应该是这个组里最出名的人,不过严格来说他是的数学家,搞图论的,有著名的Szemeredi Regularity Lemma,搞图论的每个人都知道,而且这个Lemma在TCS里也有广泛的应用. Mario Szegedy, PCP定理的证明者之一,哥德尔奖得主(因为PCP定理),不过他现在搞什么我也不太清楚. Muthukrishnan,一个搞数据流很出色的新秀, 他在SODA上做的一个数据流的Talk被很多做数据流的人(很多不是TCS的人)学习和引用. 不过好像没怎么听说他的cs要过中国人..

 

Yale是个不错的选择, 比如D.Spielman, smooth analysis的创立者(和一个著名的TCS中国教授 Teng Shanghua,现在在Boston College),并且有很多Planar Separator 和Mesh Generation等方面的其他著名工作. 还有Ravi Kannan, 也非常的牛(TCS还有两个出名的Kannan, 在U penn),
还有Joan Feigenbaum, 是Andrew Yao的学生, 她收了很多中国学生, 可惜在我这年她不招生...

 

Upenn理论组有三个强悍的老印,Khanna Sanjeev, Guha Sudipto, Kannan Sampath,发STOC/FOCS像灌水一样.

我去香港科大交流的时候,我给Mordecai Golin(HKUST的一个assoc prof, Princeton的Phd)看过我最初的申请学校的list, 他把我准备申请的Top list里去掉了Princeton, 说这里虽然老师牛,但不管学生,当然我也知道我申princeton是浪费钱, 把 2nd class list里去掉了Yale,说这里也是老师牛,但不管学生的.然后他在2nd class里给我加上了 University of Maryland-College Park和 New York University.

 

下面就吹吹我要去的UMCP, 严格来说有3个正经做算法的, 一个是Samir Khuller, Cornell毕业的, 近似算法里很出名的人, Ausiello那本书参考文献里(前面提到的)连着2页纸都是他的文章. David Mount,做计算几何的, 比较出名的工作是关于 nearest neighbor和range search的,现在兴趣好像在Kinetic data structure. Aravind Srinivasan好像也是Cornell毕业的,什么都做,不过却都做的不错.  理论组里还有Jonathan Katz, 密码学和复杂性理论新秀, Uzi Vishkin并行算法的大牛. 另外我选择这里是感觉这里的研究生教育比较扎实,导师和学生有很好的合作关系,如果学生天资有限,那么去到顶级名校可能是件痛苦的事情,但在这里却不会被抛弃,而且最后毕业时也能达到一定的高度,这也是我选择这里的原因之一.

 

NYU里TCS最大的优势就是NYU里的Courant数学中心, NYU的应用数学在全美应该是前5, 而他的TCS理论组是属于这个中心的, Richard J. Cole是Courant的副头,是做算法的, 他早年做Dynamic Range minimum query等数据结构,现在好像兴趣到Game Theory了,就是这个人热情洋溢的回复了我的陶瓷信,最后无声的据了我...还有Joel H. Spencer,就是前面写了probabilistic method的那个. 还有Chee K. Yap,也是相当牛的.

 

说说两个常春藤里排最后两个的学校, Dartmouth和Brown.

Dartmouth的cs排名不高,因为它实在太小了,好像就16个faculty,但是却几乎有一半是TCS相关的, Peter Winkler是其中最出名的(也是Mordecai告诉我的),他严格来说是个组合数学家,我读过他的一个工作, 但就这个简单但精致的证明就足够让我们崇拜他的智慧的了. 组里还有
Lisa Fleischer,女的,也是Cornell毕业的,Tardos的学生, 解决过一个著名的问题,就是用组合方法在多项式时间内minimize submodular function, 另外也有很多近似算法方面的扎实工作, 今年又开始对Game Theory感兴趣(好像和 Richard Cole合拿了一个关于Game Theory的NSF的funding), 另外Amit是princeton毕业的一个新秀,做复杂性的, 组里还有Cormen, 就是算法导论的作者CLRS里那个C.

 

Brown是朱老师去美国时带的学校,里面有一个我特别喜欢的教授 P.Klein, 做图算法的,著名的工作有线性复杂度的最小生成树的随机算法, 带权平面图旅行商问题的最优近似算法等等. Franco P. Preparata是计算几何的创世人之一, 是真正的牛导, 台湾中研院资讯所长D.T.Lee就是他的学生. 还有另外一个就是写了我上面说的的probability and Computing的Eli Upfal.

 

最后说说三个UC的学校, berkeley就不说了.
UCSD, 是Graham夫妇呆的地方, 丈夫就是那个Concrete Math的作者之一, 著名的计算几何里的求凸包的Graham算法好像也是他的.他老

婆是中国人,金芳容, Fun Chung Graham, 著名女数学家, 研究图论, 主要是谱图论和复杂网络, 他的很多学生就因为研究复杂网络去了Yahoo, Google, 不过我偷偷告诉你,她是女权主义者,就喜欢女学生.

 

UC-Irvine, 有著名的Eppstein和Goodrich, Eppstein算是计算几何界里人人皆知的人物了,异常的多产,我读过他不少paper, idea经常如天外来客. 他好像学生时代做过AI,第一篇文章发在IJCAI,立刻觉得没了追求,就去做理论了.不过他貌似没带出过什么出色的学生, 可能因为UCI的计算机招不到什么好学生, 我审他家的申请材料给我搞丢了, 我又寄了一份, 又没寄到, 打电话询问,小秘态度及其恶劣...

 

UC-riverside, 这个学校的综合排名的cs排名相对不高,但却有很好的理论组, 比如Chrobak,做在线算法的大牛,在K-server问题上有一系列著名工作, N.Young (Mordecai在princeton的同学) 和Tao Jiang. 有八卦说Tao Jiang ex-wife是复旦某系系花. 这个Tao Jiang本人也玉树临风,他现在主要兴趣是做算法相关的生物信息. 这个系好像对复旦的学生很友好, 我的材料晚到了很久, 它还是态度很好.
 
其他还有很多非常不错的地方, 比如Georgia Tech,有超级大牛V.V.Vazirani, 他是那种可以让人放弃CMU的牛导,我觉得他带的博士中好几个我觉得是TCS中最成功的博士, 再比如Duke, 有著名的P.K.Agarwal, 等等,很难一一列举.

 

说几个美国以外的地方吧.

 

世界上能和美国顶级名校比如MIT抗衡的可能也就是以色列的weizmann研究所和Tel-viv大学了,里面无数的各个学科的领军任务和顶级牛人.

而且这里的研究生教育非常的扎实,毕业生都是同行的皎皎者.不过好像很少的人去那里留学,可能是有关于安全方面的考虑....

 

加拿大的学校里TCS应该首推Waterloo,这里一度是CS北美第一强校,如今有点没落,不过仍然瘦死的骆驼比马大,这里的理论组人数众多,开设的课程十分全面,研究生在这里可以得到很好的教育, 上文提到的Erik Demaine就是这里的Phd.
UToronto里有著名的图灵奖得主,NPC理论的缔造者Cook, Cook对组合优化也有着巨大的贡献, 也是那种可以让人放弃CMU的牛导.

 

欧州里面的学校我知道2个,一个是德国的Saarland University, 这个学校里面有Max-Pluck institute-informatik(MPI) 可以说是欧洲学计算机最好的地方, 我的德国老板Rudolf就是这里毕业的, 我去过这里, MPI是一栋很大的楼,其中Theory Group占了整个2楼, 至少30-40多号人, 这里是一个TCS人才的集散中心,有很多人来这里做visit和做postdoc,在丰富了自己的研究后到其他地方去拿职位. 因此里面研究气氛很活跃, 能接触到各种不同的领域, 这里postdoc都要教课,内容根据自己喜好, 因此能有很多有趣的课程,我去的时候就听了combinatorial geometry的课程,这个课程在一般的大学里是不多见的. 不过这里你也没有自己严格的advisor, 所以可能需要个人比较活跃去融入这个活跃的研究气氛中.

 

另外一个是瑞士的ETH, 理论组也是很大,牛人很多, 绝对是学习TCS的好地方,Rudolf原来就劝过我申请这里,不过我最后没有申请,不过听说这里不能移民,可能很多人因为这个不会愿意来这里.

我没听说过英国有搞算法的人,法国不少,但是对学校了解不多....

===============

先说说读书.

记得当年学习算法小有心得的时候,曾经嘲笑过很多网上的bbs上文章,什么算法的四书五经,葵花宝典等等,其中的不少上有着指点江山的气概,下用着教化民心的口吻,激励并误导着无数的有志青年. 是不是这里就有很多的读者,连算法导论都没好好读过就开始每天2页的专研Knuth的the art of computer programming? 有多少连大O小o都不清楚,就准备决心开始通读Concrete mathematics?又有多少连NPC的概念都不知道,在一遍遍思索着哈密顿路的多项式算法. 如果有,那么我们有很多共同语言,因为其实这3件事情我都做过.

 

如果你正在阅读the art of computer programming(TAOCP),如果你还能勉强读懂,你将毫无疑问的感受到其中组合结构和算法分析的艺术性美感.Knuth以其唯美主义大师风范穷毕生精力的经典著作,目前单在计算机领域我想无它能出其右.
这本书的普及可以说从某种程度来说让更多人认识到了理论计算机科学已经不再是应用数学的一个小小分支,而已经形成了有着其自身魅力的一门独立学科.该书为knuth大爷赢得了Turing奖和无数的赞誉.在中文影印版书皮的背面,有Bill Gates的一句话书评"如果你读懂了TAOCP,请给我投一份简历".在如此多的光环下,人们于是把这个stanford的退休老头子当成神一样来膜拜,把他的书当成圣经一样来阅读. Bill Gate的评论把本该是算法分析研究者应用的字典变成了学习计算机人手一册的手册.很多人把对该书的通读速度和程度变成了衡量自己智力水平的标准.
但是作为21世纪学习TCS的学生,我只想说,这本40年前的书实在是太老了,而且它的难度使得他并不适合做入门和打基础的树,最重要的是它里面讨论的内容已经不再是TCS研究的热点,现在已经很少有人再去分析一下Shell排序的时间到底是多少,也很少人再去算一下3阶无穷小量小o前面的系数.不过无论如何,这本书都是本闲来无事陶冶情操的好书.

 

打基础,国外有很多优秀的教材,我看过的也觉得最好的就是<<算法导论>>吧,我觉得这是不二选择,我个人觉得这本书的地位就是<<心理学与生活>>在心理学的地位,萨缪尔森的<<经济学>>在经济学的地位一样,是及其经典全面的入门教材.有人说内容多了点,但是如果真想搞的话就都读了,全都是基础,我没见过写的更详细更透彻的书,全部算法都有伪代码,都有例子,翻来覆去的解释,无数的插图,还有网上MIT的视频课程.最精妙的是上面的题目,每章后面的problem,不太难,但是却很有启发性,实在是很推荐.

 

算法导论出现前有本流行很广泛的书, Aho,Hopcroft和Ullman的<<the design and analysis of computer algorithms>>,是老一辈人心中的经典,如果算法导论出现后就吧这本书取代了,这本也有影印版,可以参考看看.

 

上来就说了2本好书,就随便再多推荐几本.有了本科高数,线代和概率的基础,再加上算法导论,基本上就可以应付大多数TCS中的高级教材了,事实上这些书也是国外大学研究生的教学用书.我按着不同的小方向来说,我所能说到的基本都是我看过或听说过的.当然限于我的知识面,我也不可能列举的全面.

 

先说说近似算法Approximation algorithm,近似算法和不可近似性这个方向恐怕是目前20多年在TCS中发展最迅速和最活跃方向了,看看这些年主流的理论的国际会议,基本上近似算法和不可近似性占到最大的比例.近似算法说白了也就是用少的时间求出接近最优的解,因为这个世界上太多NPC问题,因此对这么多NPC问题设计多项式时间近似算法显然有重要的理论和现实意义.现在用最多的恐怕就是V.V.Vazirani的那本Approximatino Algorithms了,国外大部分学校上这个课都用这本.这本里每一章讲一个问题,前半本书都用的是combinatorial的方法,後半本用的是mathematical programming的方法.系统讨论不可近似性就是Ausiello等写的这本Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties.这本里面比较详细的介绍了PCP定理和不可近似性的关系.(PCP定理是近年来复杂性理论最重要的突破之一,这个证明被号称是复杂性理论建立以来最复杂的证明,今年出现了PCP的新的证明,不过仍然很复杂..)
更重要的是这本书后面有一个list,里面有几百个NPC问题的近似性与不可近似性的结果,这个list也有网上的版本,这对于查一个问题是否是NPC问题和这个问题的近似性十分的重要: http://www.nada.kth.se/~viggo/problemlist/compendium.html .另外你如果想知道近似算法解谁比较牛比较活跃,看看这本书参考文献,看看谁的名字出现次数多就一个大致的概念了.
兴界出版社影印了一本挺老的书,Hochbaum编的Approximation Algorithms for NP-hard Problems, 也还不错,不过很贵,要90多块.不过这个领域发展太快,有很多重大的突破,很多结果已经都被改进,比如arora和michelle的Euclidean空间的TSP问题的PTAS,再比如Feige的Set Cover问题被证明不能(1-\epsilon)lnn近似等等,在这本书发行的时候还没有.不过这本里面也收录了一些其他书里不常见的,比如schedule问题,度数最小生成树,比如online algorithm,再比如堵丁柱的那个成名作品,就是证明平面上最小Steiner树和最小生成树的比率最小取\sqr{3}/2.

现在很多讨论组合优化的书也开始写很多有关近似算法的内容,因为本质上来讲,近似算法研究的问题都是组合问题,也都是优化问题,其中A.Schrijiver的那3本砖头<<combinatorial optimization>>就是最好的例子,这3本就像TAOCP一样,太厚了,我只是当字典来查查.近似算法还有不少的书,我没仔细看过,没什么给我留下太多印象.

 

这些年对随机数在算法的应用(也就是随机算法randomized algorithm),以及其对计算效率影响的本质,和应用概率方法(probabilistic method)分析组合问题也是TCS热点之一. 最著名的书就是Motwani和Raghavan那本<<Randomized Algorithm>>了,内容比较全,讲了随机算法在各个不同领域的应用,比如数论算法,数据结构,图论算法,online算法等等,这本书是我读过的比较累的书之一.
还有一本是<<Probability and Computing: Randomized Algorithms and Probabilistic Analysis.>>by M. Mitzenmacher and E. Upfal. 也挺出名的.张勤曾象我推荐过mit的David Karger的博士论文,这位同学用随机算法改进了很多基本图论问题的算法,比如min-cut,比如最小生成树的随机线性算法.

 

probabilistic method应该说是P.Erdos大师发扬广大的,用来漂亮的解决了无数的问题.
本质上来讲probabilistic method并不是讨论概率问题,而只是用概率方法来解决问题或证明定理,其中大多数是确定性的问题.
比如我们想证明事件a是存在的, 这是个确定性的问题,没有任何随机性在里面. 但我们可以认为的加入概率, 我们假设每个事件都有一定概率出现,如果时间a的出现概率不为0,那么自然就说明了a是存在的.关于这个有本很经典的书,就是Alon和Spencer的<<probabilistic method>>,写的很容易懂,很多小章节,都是这个方法比较漂亮的应用,是比较好的消遣读物.

写到这里八卦两句erdos,这位老兄以天才多产和合作者众多闻名于数学界和理论计算机界,他一生和同时代的大概500个左右在不同的领域的人内进行过合作,包括数学家,工人,农民和火车上邂逅的妙龄女郎，发表了大约1,500篇论文。我们估算了一下,这需要他平均一个星期左右写一篇文章.并且流行起了一个著名的Erdos Number,意思就是在co-author关系下到Erdos的最短距离.那么直接和Erdos一起写过paper的co-author的Erdos Number就是1。那么Erdos的co-author的co-author的Erdos Number就是2, 以此类推。Erdos Number越小，说明此人和Erdos的学术关系越近。据说，当今世界90%的还活跃的数学家的Erdos Number小于8。搞数学和TCS的人们还会互相炫耀一下自己的Erdos Number。我小炫耀一下,我的Erdos Number是3(Me-F.Rudolf-N.Alon-Erdos):)

有人整理了Erdos很多漂亮的证明编成一本书,叫<<proof from the BOOK>>,里面大部分都是初等的但十分精彩的proof,如果你读了很多技术性很强很繁琐的paper的话,可以看这本书里的证明当成一下调剂.

 

概率论在算法的另外一个应用就是Average case analysis了,我们以前说的随机算法的随机因素是在算法中的,也就是说算法应用随机数,然后我们分析平均效果,但在average analysis中,算法可以是确定性的,我们假设输入是有一定分布的,然后来分析平均的效果.这需要大量的我们在本科概率里没有的数学知识,我知道的两本书,一本是knuth的弟子sedgwick的<<Analysis of algorithms>>, 里面不全是average analysis,还有很多一般的analysis,我没仔细看过, 张勤看过说很多错误. 我看过的一本<<average case analysisi 哦分algorithms on sequences>>,我觉得不错,里面有挺多不是很基础的,比如Matingale,Mellin Transfrom, Poissonization等等.

 

写到这里我自己都感觉TCS真是无边无际的,就算我只把我自己了解的都写出来都需要不知道多少篇幅. 随便捡点我最感兴趣的吧.

 

要说我对TCS的热爱是发源于我学习计算理论和复杂性理论的.这是门计算理论讨论计算本质的,而计算复杂性则是讨论计算资源和计算效率和具体问题间的关系的. 与算法设计需要的精妙技巧不同,计算理论和复杂性理论包含了更多的对问题本质的哲学性思考,从形式语言到图灵机,到NP理论,再到伪随机和交互证明理论,这些中都包含了研究者对问题本质的认识,同具体问题的算法设计相比,它们是在一个更抽象和概括的层次上进行演绎推理. 这些和具体问题的具体算法一起构成了整个TCS的大厦. 我认为一个学生即使有高超的算法设计技巧,如果他不懂得基本的计算理论和复杂性理论,也不能说他懂得TCS. 关于计算理论,我们学校本科用的教材是Sipser的<<Introduction to the Theory of Computation>>,我个人比较钟情与Hopcroft,Motwani和Ullman的那本<<introdcution to automata theory, language and computation>>, 这本有算法导论的风格,很多的例子,讲的非常详细,而且习题很精妙,强烈推荐. 关于复杂性理论,复旦理论组里最著名的一本书叫"白皮书",是Weizmann Institute的Oded goldreich用的网上的一个notes (http://www.wisdom.weizmann.ac.il/~oded/cc99.html). 我看的时候觉得挺不错的,内容挺全,不过很多师兄弟反应说写的一般...另外还有一本Papadimitriou写的<<computational complexity>>,也还凑合,不太全,比如#P啊,Interactive proof,commnication complexity都没有,不过这本有影印版. 堵丁柱写过本中文的,上面好像内容也挺多的,不过我没看过,而且我觉得还是看英文的好,要不会出现terminology的问题.

 

再说说图论算法(Graph algorithms)和算法图论(algorithmic graph theory),他们的区别从字面上可以看出来.我想说明的是这2个东西和目前数学上研究的纯数学图论是有一定区别的,区别就是他们更多的研究图的有关算法的性质,当然他们和纯数学图论是不可分割的.
推荐本比较经典的书 Algorithmic graph theory and perfect graphs, by Martin C. Golumbic 和waterloo用的一个课程(Graph-Theoretic Algorithms)的notes (http://www.student.cs.uwaterloo.ca/~cs762/Notes/index.php),notes写的很简单易懂,而且里面的知识很基本(比如interval graph, chordal graph, SP-graph, planar graph, treewidth等等),但是却很少有比较完整的介绍这些知识的书.
另外有一个网站 http://wwwteo.informatik.uni-rostock.de/isgci/classes.cgi 里面可以查到很多图形类之间的关系,比如interval graph是perfect graph等.

说道perfect graph,就想又八卦下近年来图论的巨大突破 strong perfect graph theorem (参见: http://users.encs.concordia.ca/~chvatal/perfect/spgt.html ) 和突破这个问题的其中2个人 Seymour和 Robertson 和他们的另一个更重大的突破,也就是Graph Minor theory, (见http://planetmath.org/encyclopedia/GraphMinorTheorem.html).该定理在证明前叫 Wagner's conjecture, 事实上连Wagner本人都不相信他本人做的这个conjecture是正确的,足见这个定理是多么令人惊奇. 这个定理的证明这个被称为20世纪最重要的数学遗产之一. 他们的证明共贯穿20几篇journal文章, 总共1000多页,(并且是densely-argued). 比如Tree-width, tree decomposion, pathwidth等图论中的重要概念,都是在graph minor theorem证明中的副产品. 这个定理在TCS中具有非凡的意义, 它直接暗示了许多问题都有固定参数的多项式算法(Fixed Parameter Tractable), 并且现在兴起了一个新的东东,叫Algorithmic graph minor theory, Eric Demaine和他的一个学生Hajiaghayi在做.

 

提到Eric Demaine就开始八卦他,这个同学是81年的,是TCS中小有名气的少年天才.此人20岁在waterloo的博士毕业,现在是MIT的assoc prof. 此人14岁开始写paper,写到现在可能写了有200-300篇了吧,合作者估计也几十上百个了,现在只要是理论的主流会议,只要一开会,就有该生的一堆文章发表. 他的paper我读过不少, 体现就两个字, 聪明. 他那个学生好像也不是省油的灯,博士没毕业也5,60篇文章了,而且全部是好的会议,不是随便发的水文.

TCS实在是包含太多的东西, 比如计算几何, 编码密码, 参数复杂性这些都是发展的非常迅速且庞大的学科,还有近些年兴起的数据流算法,计算经济学,量子计算等等,我也只是了解他们的皮毛. 做学问的深度和广度是一个矛盾体, 也是引起无穷讨论的话题. 我认为在国内这样一个相对落后的环境下(当然除了清华Andy Yao的Group),对很多类似闭门造车的学生来说,在得到指导和交流有限而自身又不是天赋奇才的情况下,一定的广度甚至是深度的基础.这个广度首先给了整个学科的一个框架性的认识,使得可以在这个框架下对某个问题的定位,重要性和难度有一个比较正确的估量,另外对现有方法的了解能够减少在解决具体问题时走的弯路. 另外很重要的一点是, 广泛的阅读可以培养兴趣,欣赏别人发现的漂亮而深刻的结果也是令人兴奋的,这比长时间被一个问题卡住无进展从而尚失研究的兴趣要好的多.

 

并且我也认为一个TCS的学生应该多读书,多懂些东西,而且并不局限于TCS,不要被人家一个manifold, 一个nash equalibrum 或者quantum entanglement这样的基本名词吓到.我花了大量的时间在这些并不属于我研究领域的书上面,当然也并不因为炫耀或用来增加谈资,只是因为我想知道,我想了解现象背后的规律.这种求知的欲望是一个研究者学习和研究的动力源泉.

 

快毕业了,百无聊赖,写点总结性的东西吧,包括不少感受,比较学术,有些专业名词,还有一些科普,一些八卦.

 

写这篇文章的目的是整理总结一个自己的思路,因为三年确实读了学了不少东西,另一个目的是也许能对背景类似的初学者有所帮助.

 

严格说来本科的时候也有接触过算法, 因为学校的程序设计比赛,没花什么精力也十分的业余,现在想想那个时候连算法导论都没听说过,连快速

排序都不能顺利写好,实在是不能称为懂得TCS. 真正全面的接触算法和TCS应该还是在研究生开始的这段时间.

 

作为学习理论计算机(Theorectical computer science, TCS)的一个研究生,我也只能说写点自娱自乐的感受和体会,不能够高屋建瓴,是因为我

学问的片面和研究的肤浅. 另外我的感受并不等同于每个人的感受.我有很多想法, 你如果不认同, 那么请你一起探讨或者一笑置之,如果你没

什么概念, 你或许能从这里找到一点感觉.