Blog

知其所以然(三):为什么算法这么难?

广大码农同学们大多都有个共识,认为算法是个硬骨头,很难啃,悲剧的是啃完了还未必有用——除了面试的时候。实际工程中一般都是用现成的模块,一般只需了解算法的目的和时空复杂度即可。 不过话说回来,面试的时候面算法,包括面项目中几乎不大可能用到的算法,其实并不能说是毫无道理的。算法往往是对学习和理解能力的一块试金石,难的都能掌握,往往容易的事情不在话下。志于高者得于中。反之则不成立。另一方面,虽说教科书算法大多数都是那些即便用到也是直接拿模块用的,但不幸的是,我们这群搬砖头的有时候还非得做些发明家的事情:要么是得把算法当白盒加以改进以满足手头的特定需求;要么干脆就是要发明轮子。所以,虽说面试的算法本身未必用得到,但熟悉各种算法的人通常更可能熟悉算法的思想,从而更可能具备这里说的两种能力。 那么,为什么说算法很难呢?这个问题只有两种可能的原因: 算法本身就很难。也就是说,算法这个东西对于人类的大脑来说本身就是个困难的事儿。 讲得太烂。 下面会说明,算法之所以被绝大多数人认为很难,以上两个原因兼具。 我们说算法难的时候,有两种情况:一种是学算法难。第二种是设计算法难。对于前者,大多数人(至少我当年如此)学习算法几乎是在背算法,就跟背菜谱似的(“Cookbook”是深受广大码农喜爱的一类书),然而算法和菜谱的区别在于,算法包含的细节复杂度是菜谱的无数倍,算法的问题描述千变万化,逻辑过程百转千回,往往看得人愁肠百结,而相较之下任何菜谱涉及到的基本元素也就那么些(所以程序员肯定都具有成为好厨师的潜力:D)注意,即便你看了算法的证明,某种程度上还是“背”(为什么这么说,后面会详述)。我自己遇到新算法基本是会看证明的,但是发现没多久还是会忘掉,这是死记硬背的标准症状。如果你也啃过算法书,我相信很大可能性你会有同感:为什么当时明明懂了,但没多久就忘掉了呢?为什么当时明明非常理解其证明,但没过多久想要自己去证明时却发现怎么都没法补上证明中缺失的一环呢?

知其所以然(续)

我有一个习惯,看定理必看证明。一个你不明白其证明的定理在我看来比不知道这个定理还要糟糕,因它给你造成一种懂了的错觉。在没有明白背后的证明之前,任何一个定理对你来说都是等价的——等价于背乘法口诀(只不过有的长一点有的短一点)。一个原本美妙的定理,把其证明扔掉就是真正的买椟还珠,暴殄天物。 从现实意义来说,去理解一个定理的证明会带来巨大的好处,首当其冲的好处就是你很难再忘掉它。这一点其实很容易解释——在理解一个定理的证明之前,定理对你而言是一堆没有内在联系的词句,而在理解了证明之后,定理就归约为证明它所需的条件加上逻辑...这是一个树状的知识结构,越往上层走,需要记忆的节点就越少。

知其所以然(以算法学习为例)

其实下文的绝大部分内容对所有学习都是同理的。只不过最近在正儿巴经地学算法,而后者又不是好啃的骨头,所以平时思考总结得就自然要比学其它东西要多一些。 问题:目前几乎所有的算法书的讲解方式都是欧几里德式的、瀑布式的、自上而下的、每一个推导步骤都是精准制导直接面向目标的。由因到果,定义、引理、定理、证明一样不少,井井有条一丝不乱毫无赘肉。而实际上,这完全把人类大脑创造发明的步骤给反过来了。看起来是阳关大道,实际上车马不通。

数学之美番外篇:快排为什么那样快

知道这个理论是在TopLanguage上的一次讨论,先是g9转了David MacKay的一篇文章,然后引发了牛人们的一场关于信息论的讨论。Anyway,正如g9很久以前在Blog里面所说的: 有时无知是福。俺看到一点新鲜的科普也能觉得造化神奇。刚才读Gerald Jay Sussman(SICP作者)的文章,Building Robust Systems – an essay,竟然心如小鹿乱撞,手心湿润,仿佛第一次握住初恋情人温柔的手。 而看到MacKay的这篇文章我也有这种感觉——以前模糊的东西忽然有了深刻的解释,一切顿时变得明白无比。原来看问题的角度或层面能够带来这么大的变化。再一次印证了越是深刻的原理往往越是简单和强大。所以说,土鳖也有土鳖的幸福:P 这篇文章相当于MacKay原文的白话文版。MacKay在原文中用到了信息论的知识,后者在我看来并不是必须的,尽管计算的时候方便,但与本质无关。所以我用大白话解释了一通。

跟波利亚学解题(rev#3)

波利亚在他著名的《How To Solve It》中讲了这么一个有趣的心理学实验: 用一个缺了一条边的正方形围栏围住一只动物(狗、黑猩猩、母鸡、人类婴儿),在围栏的另一侧放上一个被试很想要的物体(对动物来说是食物,对人类婴儿来说是有趣的玩具),然后观察他们各自的行为。发现,狗在扒着围栏吠了几声发现无法通过的时候,不久便学会了从围栏的缺口的那一边绕出去,母鸡则朝着围栏一个劲的扑腾,不会想到绕弯子。此外,人类婴儿很快就学会了绕过障碍;而黑猩猩也学得很快(黑猩猩是和人类最近的灵长类亲属)。这个实验有力的证明了,动物解决问题的能力是进化而来的、天生的、硬编码在大脑的神经元网络里面的。

数学之美番外篇:进化论中的概率论

偶然性在进化中确实存在(例如,偶然性的突变可以产生新的特征),但是进化并不依赖偶然性来产生新的器官、蛋白质或其他实体。截然相反的是,自然选择,作为进化中已知的最主要机制,却会明确保留“需要的”(能适应的)特性,消除“不需要的”(无法适应的)特性。只要选择的影响力存在,自然选择就能把进化向一个方向推进,在出乎意料的短时间内产生复杂的结构。举个例子,现有由13个字母构成的序列“TOBEORNOTTOBE”,假设有几百万只猴子,每只猴子每秒钟挑一条短语,需要78,800年才能从26^13种可能中选出这样的排列。不过,Glendale College的Richard Hardison在20世纪80年代写过一个程序,它能够在随机产生序列的同时,保证那些已经出现在正确位置上的字母不会变化(这样做倒有点《汉姆雷特》 的味道。译注:这个句子看了大半天才明白,嘿嘿)。这个程序平均只需要336次迭代就能生成上文提到的短语,时间少于90秒。更神奇的是,把莎士比亚的整个剧本重新生成一遍也只需要四天半时间。

康托尔、哥德尔、图灵——永恒的金色对角线(rev#2)

哥德尔的不完备性定理震撼了20世纪数学界的天空,其数学意义颠覆了希尔伯特的形式化数学的宏伟计划,其哲学意义直到21世纪的今天仍然不断被延伸到各个自然学科,深刻影响着人们的思维。图灵为了解决希尔伯特著名的第十问题而提出有效计算模型,进而作出了可计算理论和现代计算机的奠基性工作,著名的停机问题给出了机械计算模型的能力极限,其深刻的意义和漂亮的证明使它成为可计算理论中的标志性定理之一。丘齐,跟图灵同时代的天才,则从另一个抽象角度提出了lambda算子的思想,与图灵机抽象的倾向于硬件性不同,丘齐的lambda算子理论是从数学的角度进行抽象,不关心运算的机械过程而只关心运算的抽象性质,只用最简洁的几条公理便建立起了与图灵机完全等价的计算模型,其体现出来的数学抽象美开出了函数式编程语言这朵奇葩,Lisp、Scheme、Haskell… 这些以抽象性和简洁美为特点的语言至今仍然活跃在计算机科学界,虽然由于其本质上源于lambda算子理论的抽象方式不符合人的思维习惯从而注定无法成为主流的编程语言,然而这仍然无法妨碍它们成为编程理论乃至计算机学科的最佳教本。而诞生于函数式编程语言的神奇的Y combinator至今仍然让人们陷入深沉的震撼和反思当中…