在这篇文章里，我们从信息论的角度证明了，基于比较的排序算法需要的比较次数（在最坏情况下）至少为log2(n!)，而log(n!)=Θ(nlogn)，这给出了比较排序的一个下界。但那里我们讨论的只是最理想的情况。一个事件本身所含的信息量是有大小之分的。看到这篇文章之后，我的思路突然开阔了不少：信息论是非常强大的，它并不只是一个用来分析理论最优决策的工具。从信息论的角度来分析算法效率是一件很有趣的事，它给我们分析排序算法带来了一种新的思路。

    假如你手里有一枚硬币。你希望通过抛掷硬币的方法来决定今天晚上干什么，正面上网反面看电影。投掷硬币所产生的结果将给你带来一些“信息”，这些信息的多少就叫做“信息量”。如果这个硬币是“公正”的，正面和反面出现的概率一样，那么投掷硬币后不管结果咋样，你都获得了1 bit的信息量。如果你事先就已经知道这个硬币并不是均匀的，比如出现正面的概率本来就要大得多，这时我们就说事件结果的不确定性比刚才更小。如果投掷出来你发现硬币果然是正面朝上，这时你得到的信息量就相对更小（小于1 bit）；反之如果投掷出来居然反面朝上了，那你就得到了一个相对较大的信息量（大于1 bit）。但平均下来，我们得到的信息量是小于1 bit的，因为前者发生的可能性毕竟要大一些。最极端的情况就是，这是一枚被捣了鬼的魔术硬币，你怎么投都是正面。此时，你投了硬币等于没投，反正结果都是正面朝上，你得到的信息量永远为0。
    这个理论是很符合生活实际的。昨天晚上我出去吃饭时，坐在我后面的那个人是男的还是女的？这种问题就比较有价值，因为大家都猜不到答案究竟是什么；但要问我昨天跟谁一起出去上自习去了，问题的答案所含的信息量就变小了，因为大家都知道如果我破天荒地跑去自习了的话多半是有MM陪着一起去的。如果有网友问我是男的还是女的，那就更不可思议了，因为我不但多次在这个Blog里提到我一直想找一个合适的MM，还在AboutMe里面发了我的照片。如果某人刚操完一个MM，突然扭过头去问“对了，你是男的还是女的呀”，那这个人绝对是一个不折不扣的大傻B，因为这个问题所能带来的信息量几乎为0。
    总之，当每种结果出现的概率都相等，事件的不确定性达到最大，其结果最难预测时，事件的发生将会给我们带来最大的信息量。我们把一个事件的不确定程度叫做“熵”，熵越大表明这个事件的结果越难以预测，同时事件的发生将给我们带来越多的信息。如果在排序算法里每次比较的熵都是最大的，理论上来说这种（基于比较的）排序算法就应当是最优的。但我们一会儿将看到，我们已知的排序算法总是不完美的，每种算法都会或多或少地存在一些价值明显不大的比较。

查看更多 »

    射影几何太科学了！太科学了！以后我要慢慢写进Blog里。这里说一个《什么是数学》中射影几何章节中的一个小插曲，和射影几何本身没太大关系：纸上两点A和B，它们之间的距离大于直尺的长度。你如何只用直尺作出过这两点的连线？注意，你只能使用笔和直尺，不能借助圆规等其它工具。

    首先让我们回顾一下射影几何中的Desargues定理。Desargues定理描述了一个由简单的点和线所构成的美妙的关系：平面上的两个三角形的对应顶点的连线共点，则对应边的交点共线。你可以多画几个图来验证这一结论，这里不再介绍完整的证明了。另外，虽然题目中的直尺不能连接距离太远的两点，但别忘了直尺可以无限延长一条已有的线段，你只需要不断重复“延长 - 描新点”的步骤就可以了。

查看更多 »

老古董了，现在找都找不到。真想要一个。
不知道有没有人见到过。
来源：http://jandan.net/2008/05/24/curta-calculator.html

    Ubigraph是一个全新的图论动画生成软件，利用它你可以快速生成图论模型的图形和动画，直观地展示出各种图论模型的三维结构，演示各种图论算法的过程，非常适合用于研究和教学。之前本Blog曾经介绍过一个类似的软件graphviz，但这里提到的Ubigraph显然更强大一些。上面的动画就是由Ubigraph生成的二叉查找树演示动画（高清版here），看上去相当的酷。值得一提的是，Ubigraph也是相当易用的。graphviz有它自己的语法规则，而Ubigraph则直接支持Python, Ruby, PHP, Java, C, C++等几乎所有主流语言，因此不管你原先使用的是什么语言，你都可以很快地融入到Ubigraph来。例如，在C语言中包含一个头文件UbigraphAPI.h，你便可以像往常一样用循环语句“画”一个环。

#include <UbigraphAPI.h>
 
int main(int const argc, const char ** const argv)
{
int i;
for (i=0; i < 10; ++i)
ubigraph_new_vertex_w_id(i);
 
for (i=0; i < 10; ++i)
ubigraph_new_edge(i, (i+1)%10);
 
sleep(2);
 
ubigraph_clear();
}

    你可以在这里下载这个软件。目前该软件暂时没有Windows版。

    一个迟到的消息：Google Treasure Hunt 2008已经开始了，这是Google Sydney为了挖掘出新的工程师而精心设置的一个活动。现在已经有两道题目了，在以后几周的时间里Google将陆陆续续地发布更多的题目。第一个答对所有问题的人将成为这次Treasure Hunt的获胜者。
    有兴趣的朋友赶快去试一试。

    今天，我们将从一系列公理开始，从自然数的产生一直说到实数理论的完善。你或许会对数学的“科学性”有一个新的认识。注意，本文的很大一部分内容并非直接来源《什么是数学》，这篇文章可以看作是《什么是数学》中有关章节的一个扩展。

    自然数是数学界中最自然的数，它用来描述物体的个数，再抽象一些就是集合的元素个数。在人类文明的最早期，人们就已经很自然地用到了自然数。可以说，自然数是天然产生的，其余的一切都是从自然数出发慢慢扩展演变出来的。数学家Kronecker曾说过，上帝创造了自然数，其余的一切皆是人的劳作。 (God made the natural numbers; all else is the work of man.)
    随着一些数学理论的发展，我们迫切地希望对自然数本身有一个数学描述。从逻辑上看，到底什么是自然数呢？历史上对自然数的数学描述有过很多的尝试。数学家Giuseppe Peano提出了一系列用于构造自然数算术体系的公理，称为Peano公理。Peano公理认为，自然数是一堆满足以下五个条件的符号：
   1. 0是一个自然数；
   2. 每个自然数a都有一个后继自然数，记作S(a)；
   3. 不存在后继为0的自然数；
   4. 不同的自然数有不同的后继。即若a≠b，则S(a)≠S(b)；
   5. 如果一个自然数集合S包含0，并且集合中每一个数的后继仍在集合S中，则所有自然数都在集合S中。（这保证了数学归纳法的正确性）

    形象地说，这五条公理规定了自然数是一个以0开头的单向有序链表。
    自然数的加法和乘法可以简单地使用递归的方法来定义，即对任意一个自然数a，有：
a + 0 = a
a + S(b) = S(a+b)
a · 0 = 0
a · S(b) = a + (a·b)

    其它运算可以借助加法和乘法来定义。例如，减法就是加法的逆运算，除法就是乘法的逆运算，“a≤b”的意思就是存在一个自然数c使得a+c=b。交换律、结合率和分配率这几个基本性质也可以从上面的定义出发推导出来。
    Peano公理提出后，多数人认为这足以定义出自然数的运算，但Poincaré等人却开始质疑Peano算术体系的相容性：是否有可能从这些定义出发，经过一系列严格的数学推导，最后得出0=1之类的荒谬结论？如果一系列公理可以推导出两个互相矛盾的命题，我们就说这个公理体系是不相容的。Hilbert的23个问题中的第二个问题就是问，能否证明Peano算术体系是相容的。这个问题至今仍有争议。

查看更多 »

来源：http://digg.com/general_sciences/Imaginary_Numbers

  来自Samsung的一段精彩的视频，你可以在短短两分钟的时间内看到10个经典的错觉演示。