知其所以然（以算法学习为例）

学习方法, 算法 - Written by 刘未鹏 on Monday, July 7, 2008 21:05 - 10,326 views - 4 Comments

其实下文的绝大部分内容对所有学习都是同理的。只不过最近在正儿巴经地学算法，而后者又不是好啃的骨头，所以平时思考总结得就自然要比学其它东西要多一些。

问题：目前几乎所有的算法书的讲解方式都是欧几里德式的、瀑布式的、自上而下的、每一个推导步骤都是精准制导直接面向目标的。由因到果，定义、引理、定理、证明一样不少，井井有条一丝不乱毫无赘肉。而实际上，这完全把人类大脑创造发明的步骤给反过来了。看起来是阳关大道，实际上车马不通。

阅读全文 >>

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

数学, 算法, 计算机科学 - Written by 刘未鹏 on Friday, June 13, 2008 19:53 - 11,126 views - 9 Comments

知道这个理论是在TopLanguage上的一次讨论，先是g9转了David MacKay的一篇文章，然后引发了牛人们的一场关于信息论的讨论。Anyway，正如g9很久以前在Blog里面所说的：

有时无知是福。俺看到一点新鲜的科普也能觉得造化神奇。刚才读Gerald Jay Sussman（SICP作者）的文章，Building Robust Systems – an essay，竟然心如小鹿乱撞，手心湿润，仿佛第一次握住初恋情人温柔的手。

而看到MacKay的这篇文章我也有这种感觉——以前模糊的东西忽然有了深刻的解释，一切顿时变得明白无比。原来看问题的角度或层面能够带来这么大的变化。再一次印证了越是深刻的原理往往越是简单和强大。所以说，土鳖也有土鳖的幸福:P

这篇文章相当于MacKay原文的白话文版。MacKay在原文中用到了信息论的知识，后者在我看来并不是必须的，尽管计算的时候方便，但与本质无关。所以我用大白话解释了一通。

阅读全文 >>

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

思维改变生活, 算法 - Written by 刘未鹏 on Friday, April 18, 2008 21:37 - 9,942 views - 7 Comments

波利亚在他著名的《How To Solve It》中讲了这么一个有趣的心理学实验：

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

阅读全文 >>

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

数学, 算法 - Written by 刘未鹏 on Sunday, December 2, 2007 18:55 - 7,419 views - 4 Comments

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

阅读全文 >>

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

数学, 算法, 计算机科学 - Written by 刘未鹏 on Sunday, October 15, 2006 19:16 - 9,413 views - 10 Comments

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

阅读全文 >>