Monthly Archives: December 2008

我不写总结

写写接下来想看的书:

Algorithm Design : 不干这一行了,这本当小说翻翻就得了

关于随机算法和近似算法的,有好书可以给我推荐下

Introduction to Information Retrieve : 挺好的书,通俗易懂,看了1/3了吧

Elements of Information Theory : 硬着头皮看

Vapnik : 统计机器学习的本质

Boyd : Convex optimization

All of statistics : 还好,不太难懂

Ross的概率论和随机过程

卓里奇的数学分析

Rudin的泛函

抽象代数的也来一本

Head First Design Pattern

C++ Template

Thinking in Java 以及关于JVM的东西

Python的稍深一点的书,有好书可以给我推荐下

Functional Programming的,有好书可以给我推荐下

再来本人月神话?

关于认知科学和科学哲学、科学史的入门书,有好书可以给我推荐下

西方哲学史以及更多的罗素

时间回旋;基地、神们自己以及更多的阿西莫夫

斯塔夫理阿诺斯 : 全球通史

还有几本垂涎已久的:编译龙书、AI:Modern Approach、CS:APP、APUE、TAOCP

能看多少算多少吧……

向着变态的道路前进前进!

趣题一则

同学问我的,居然用比较短的时间想明白了,xb一下:

问题是这样的,有N个人之间有一些“认识”关系,“认识”是单向的,即A认识B不代表B一定认识A。现在已知其中存在这么一个人,所有其他的人都认识他,而他不认识任何人。现在你要用最少次数的询问找出这个人。你的询问只能是“A认识B吗?”这种形式。

提示:询问次数是O(N)的

答案(反白显示):其实很简单,只需要注意到一个事实,每次询问必定会排除一个人。我们每次可以随便找两个人AB,问“A认识B吗?”,如果答案为是,那么A就被排除;如果答案为否,那么B就被排除。所以一共只需N-1次询问,最后剩下的那个就是我们要找的人。

圣诞节说个小笑话

刚来天大的第一年,英语系的迎新晚会,几个学长学姐表演英文短剧,演的就是耶稣诞生这一段。刚结婚的玛丽亚把自己”感孕”的事情告诉丈夫约瑟,约瑟无奈地对天长叹:O my God, you gave me such a big green hat!

我和我的ACM-ICPC (2)

[2. 初生牛犊]

先把ACM的话题放一下,我想有一件事可能会有人有兴趣,那就是我进天大时的专业是社会科学与外国语学院英语专业。这件很诡异的事情是样子的,高考完事得了一个不上不下的分数以后,我就想求稳一下,而天大按往年规律来看应该是一个“小年”,我的分数应该至少超过录取线二三十分左右,所以就很信心满满地报了几个喜欢的专业:第一当然是计算机,然后好像是自动化和电信,然后下面几个实在不知道填什么了,就开始乱填,鬼使神差就写了个英语(虽然这是个文科专业,但文科理科生都招)。然后录取线出来发现估计严重失误,比我想象的高得多,然后我就差不多正好压线进,然后就被分到第四志愿——英语了(计算机在我们省那时候貌似仍然是大热门专业,不比录取线高很多是进不了的)刚开始的时候还在为能进天大而感觉挺高兴的,很快发现英语系确实不太适合我。(跑题几句,我并不是说这个专业不好,我知道在天大这个工科学校大家对这样的文科专业确实不很重视,但希望大家明白,在社外学院同样有很多令人尊敬的老师、令人佩服的优秀同学,我从他们身上学到了很多。{还有,很多很多MM啊~} 对于选专业问题我的看法是,没有好不好,只有适合不适合、喜欢不喜欢,而我确实更适合计算机。另外还有就是,艺多不压身,不喜欢的课程实在绕不开的话也不妨学一下,说不定什么时候就会用到。比如现在我要做一些自然语言处理方面的东西,就有点后悔当初没把语言学的东西好好看看,那样的话现在就会省事些了。)为了能转专业,当时在接触ACM之前我还很花了功夫去准备高数之类的东西(这些课英语专业不学,但转专业考试要考)。而最终我是在大一升大二的时候转到了软件学院,实话来讲我是更倾向于转到计算机的(主要是学费问题),但因为转计算机必须在本专业排名前10%且必须参加转专业考试,虽然我的大一成绩足够资格,但专试的科目像高数什么的我们专业都不学的,因为后来沉迷于ACM的关系也没有认真自学过,所以估计就很难成功。而当时软件学院有一个特殊政策(我不清楚现在还有没有)就是不必参加考试,只要通过面试即可,再加上于老师的推荐,相对来说容易得多,所以就选择了软件学院。顺便提一句,我认为软件学院这个措施很好,能够让确实对计算机感兴趣的同学学到自己喜欢的东西,比如我们这届几个转专业的同学,和我比较熟悉的像应翔(cnhawk)、张钊(GDC)等等都在转专业后表现得很出色。

好了,文科男的故事讲完了,继续说ACM。04年冬天,某次去综合实验楼上机的时候,看到楼外面挂着一个横幅,就是说电信学院(当时还没有计算机学院)科协主办的计算机程序设计比赛,然后我就上天外天去找相关的活动信息,发邮件报了名。然后发现天外天首页上有指向求实BBS的链接,很有兴趣地点进去了,正好在首页上就有一篇ACM版的文章(我们知道被m的文章会按一定机率显示在首页),看到“ACM国际大学生程序设计”这个名字,我才回想起来原来真的有这个比赛,而且在天大真的有那么多关注这个的人(当然比起现在来不在一个数量级的),于是就有了这篇帖子(当时注册帐号是很容易的):

在ACM版的第一帖

在ACM版的第一帖

当然,这里我是怕人家不收,腆着脸说自己参加过OI,懂得一些数据结构和算法,其实我知道我自己会的那点东西根本就还不上道儿。后来,hill给我回了一封信,这信我现在还留着(已得到hill允许公布):

Hill给我的回信

Hill给我的回信

(从这封信也可以看出TJU ACM的发展了,从当年的50题入队到现在与入队无关的随队训练都要选拔,现在的小朋友们不要太羡慕啊,呵呵)

有时候我就想,当时ACM比赛在天大的影响力还很小很小,就连计算机系和软件学院的很多同学都不知道,如果我不是刚好路过时看到比赛的横幅,或者没有乱点一通撞进了BBS上的ACM版,真的很难想象我这个英语专业的学生和一个在计算机专业都还默默无闻的编程比赛之间能有什么交集。生活真的好像是由一系列的偶然组成,其中任何一件事发生一点改变,也许后面的结果就完全不同。但它确实就那样的发生了,而我们也再没有机会退回去看看另一种可能。

哦对了,还有那场比赛,也是挺好玩的,据说是他们找BunnyQ出的题,比赛形式有点不伦不类,一共四道题,你写好一道后就告诉staff,然后就会有一个气球,其实这时候还不知道题目对错,是在赛后评测的。最后我貌似是四道都做了(很水很水的题,比我以前在Ural上做的那些还水),然后这场比赛就很囧的被我这个社外学院的大一新生拿了冠军……当然也是因为没有多少牛人参加,当时ACM队的里的人都没参加,后来认识的人里面好像也就秘中凯(washington)参加了吧。

后来我就和队伍联系上了,有一天被于老师叫到当时的训练场地——网络中心旁边的软件学院小机房见了一面。那天印象里是队员们正在做一场POJ上的练习赛,我还跟风做了一道水题,这也是我在POJ的第一次提交:

我在POJ的第一次提交

我在POJ的第一次提交

然后呢,就是在ZOJ上向着50题的目标努力了(可惜因为那次ZOJ的挂掉,我在ZOJ的第一次提交已经找不到了)。Pascal转C是很简单的事,ZOJ上的水题也比Ural上多得多,所以这个目标对我来说还不算太困难。到放寒假前我已经做了80道左右,排进了ZOJ的前1000名,当时还激动地发帖庆祝了下。然后再开学以后买了台电脑(当时还管得不严,大一买电脑也没啥事),不用天天泡在综合实验楼的机房了,那段时间过得极high,所有的课能逃就逃(此处严重不推荐小朋友们模仿……)还好我高中英语的底子还算凑和,英语专业的考试勉强都能应付过去,然后几乎全部时间都用来看书和做题。每天早晨睁开眼就上ZOJ,遇到实在不能逃的课就拿着一本CLRS到课上偷着看(当时CLRS还没中译版,后来我从来不怵英文书就是那时候被逼出来的),晚上临睡前一定要读一道难题,一边想一边睡过去。我想如果做过ACM的话,大家应该都有一段类似的疯狂经历,那是一个水平呈指数增长的阶段,感觉每一天的自己都比前一天强,每一分钟都在学习新的东西。对于我这个半吊子前OIer来说尤其是这样:在高中的那段时间,我的学习是完全不成体系的,解题的时候基本没有算法可言,完全是朴素的思路或是依赖于偶尔的灵光一闪,当时感觉最无奈的一件事就是TLE。而现在忽然发现,随着学习的深入,两年以前那些让我无可奈何的题目,陆陆续续都被解决掉了,那种不断超越自己的感觉真的是无比美妙。

这段时间有一个很重要的事情就是05年上半年上届老队员的讲座,以现在的眼光来看可以说是入门级的内容,但对于当时的我来说实在是宝贵的学习机会,给我印象最深的是Oxford讲的Prim和Dijkstra,美妙的算法一下子就把我征服了,听完讲座马上回去把能切的题都切掉了。还有一个让我印象深刻的事就是学习DP的时候,我前面说过高中那几个月这个东西我就一直没明白过来,虽然有时候也能照猫画虎做出几个,但总是感觉没有体会到这种算法设计思想的本质。然后某一天我就下定决心要把它弄明白,趴在床上把王晓东那本《算法分析与程序设计》里面的几个例子翻来覆去地看啊看啊,突然就一下子全明白了,那个词怎么说来着,“醍醐灌顶”,什么状态表示、转移方程,所有这些线索一下子理顺清楚了,这个困扰我两年的问题竟然就在那一瞬间解决,那时候真的激动地要几乎要叫出来。然后我做的事就是打开ZOJ,把之前想过但不会做的题尝试着一个个往DP上套,一下子又解决掉一大片题目。后来最后的两次讲座我还被于老师要求上去讲东西,于是就把刚明白一点的DP讲了讲,似乎效果还不错,呵呵。

04年的冬天和05年上半年我就是在这样一种痴狂的状态下度过的。暑假集训开始前我在ZOJ做了400多道题,排进前100了,在所有新队员里面是最多的,如果只从题数上看已经达到了上一年一队队员的程度。而我也终于发现,我已经无可救药的爱上了这个比赛。

(待续)

“万有引力是如何产生的?”

在水木的Science版看到了这样一个问题:

发信人: jinguojie (jinguojie), 信区: Science

标  题: 万有引力是怎么产生的?

发信站: 水木社区 (Thu Dec 11 14:17:00 2008), 站内

最近忽然意识到这个问题:高中物理讲了万有引力的公式,却从来没讲过为什么万物之间会存在“引力”。

有没有资料解答这个问题的?

然后引发了很多精彩的讨论,扯出了广义相对论、人择原理、奥卡姆剃刀等等。其实这个问题我在刚学物理课的时候就已经以一个中学生所能做到的最严肃的科学态度思考过了,很有意思的是我思考的也是关于万有引力定律公式的问题,大概是因为这个公式太有人工拼凑的痕迹吧。当然,我的思考是不可能找到答案的,并且当时我对自己的问题很感到怀疑,因为我感觉如果这是一个有意义的问题的话,那么不可能这么多年来没人想到,但是这个问题却没有在课本上有解释,所以只有两种可能:要么这个问题过于简单或是没有意义,要么这个问题是目前无人能解。而在当时我认为一定是前者了,直到后来渐渐感觉不是那么回事,这次终于看到有人提了这个问题,并且下面有回复说“这是一个好问题”以及“这个问题已经快要问到物理学的本质了”,更加让我确信事情没有这么简单。

这个问题一个很现代的回答是,根据广义相对论,大质量物体周围的空间会发生弯曲,所以沿测地线运动的物体在弯曲空间里就变成了沿曲线运动,导致看上去存在一个“引力”。但我们很自然会继续追问,为什么有质量的物体周围空间会发生弯曲?现在没有人能解释了,就算将来又出现了一种理论解释这种现象,就像我们现在用相对论解释牛顿定律一样,那个新的理论一定又有一些无法解释的假定,只是因为这些假定能够包容更多的现象,能够更好地解释现有的理论,我们就又承认那个理论是正确的,直到再次发现不能解释的现象为止。然而,这样一层层解释上去,什么时候我们才可以相信我们触到了本质?或者甚至是在离本质越来越远?这种问题究竟是不是科学可以回答的,或是只能诉诸宗教?

如果再细究的话很快就又收敛到那几个哲学终极问题上了,所以先打住到这里。以我的智力无法得出答案了,聪明的,你能告诉我吗?