《来自圣经的证明》收集了数十个简洁而优雅的数学证明，迅速赢得了大批数学爱好者的追捧。如果还有一本《来自圣经的算法》，哪些算法会列入其中呢？最近，有人在StackExchange 上发起了提问，向网友们征集那些来自圣经的算法。众人在一大堆入围算法中进行投票，最终得出了呼声最高的五个算法：

第五名：BFPRT 算法
    1973 年， Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan 集体出动，合写了一篇题为 “Time bounds for selection” 的论文，给出了一种在数组中选出第 k 大元素的算法，俗称"中位数之中位数算法"。依靠一种精心设计的 pivot 选取方法，该算法从理论上保证了最坏情形下的线性时间复杂度，打败了平均线性、最坏 O(n^2) 复杂度的传统算法。一群大牛把递归算法的复杂度分析玩弄于股掌之间，构造出了一个当之无愧的来自圣经的算法。

第四名：快速排序
    快速排序算法是 1960 年由英国计算机科学家 C.A.R. Hoare 发明的，是一种既高效又简洁的排序方法，现在已是学习算法的必修内容之一。快速排序的思想并不复杂，妙就妙在那个线性的数据分割过程，而真正最牛 B 的则是对整个算法的时间复杂度分析。我曾写过一个快速排序平均 O(n log n) 的证明，分析过程绝对值得欣赏。

 
第三名：并查集
    严格地说，并查集是一种数据结构，它专门用来处理集合的合并操作和查询操作。并查集巧妙地借用了树结构，使得编程复杂度降低到了令人难以置信的地步；用上一些递归技巧后，各种操作几乎都能用两行代码搞定。而路径压缩的好主意，更是整个数据结构的画龙点睛之笔。并查集的效率极高，单次操作的时间复杂度几乎可以看作是常数级别；但由于数据结构的实际行为难以预测，精确的时间复杂度分析需要用到不少高深的技巧。

 
第二名：KMP 算法
    KMP 算法是一种非常有效的字符串匹配算法，它告诉了人们一个有些反直觉的事实：字符串匹配竟然能在线性时间里完成！整个算法写成代码不足 10 行，但其中蕴含的天才般的奇妙思想让算法初学者们望而却步，而它的复杂度分析则更是堪称经典。

 
第一名：辗转相除法
    辗转相除法是 Euclid 的《几何原本》中提到的一种寻找两个数的最大公因数的算法。无论是简洁的算法过程，还是深刻的算法原理，抑或是巧妙的复杂度分析，都称得上是来自圣经的算法。而扩展的辗转相除法则构造性地证明了，对任意整数 a 和 b ，存在一对 x 、 y 使得 ax + by = gcd(a, b) 。这一结论的普遍性和实用性让它成为了数论中的基本定理之一，在很多数学问题中都能看到它的身影。

注：文章部分内容整理于网络

      2017年10月26日上午，第十四届中国计算机大会（CNCC 2017）正式在福州海峡国际会展中心开幕，在大会第一天，菲尔兹奖获得者、哈佛大学终身教授丘成桐在会上作为特邀嘉宾做了首个演讲报告，报告主题为《现代几何学在计算机科学中的应用》。

　　报告中丘成桐先生首先介绍了现代几何的发展历史，随后介绍了他与他的学生及朋友在计算机与几何交叉方面的一些研究。对于人工智能，丘成桐先生认为现代以神经网络为代表的统计方法及机器学习在工程实践中取得了很大的成功，但其理论基础非常薄弱，是一个黑箱算法；人工智能需要一个可以被证明的理论作为基础。

      演讲内容整理如下：

胡事民（大会程序主席，清华大学教授）：

　　大家都知道，计算机科学离不开数学，早期的计算机都是数学家帮我们奠定了基础。今天的第一个报告，我们非常荣幸地邀请到了著名的数学家、数学界最高奖菲尔兹奖获得者、哈佛大学教授丘成桐。丘老师不仅是伟大的数学家，他也在计算机方面做了很多工作。他开创了计算共形几何，广泛地应用在图形学、视觉传感器等方面。最近丘先生还在Nature上发表了一篇文章，研究社交网络。下面我们有请丘先生。

丘成桐演讲全文：

　　今天很荣幸地收到你们的邀请来做一个演讲。我本人在数学上的贡献不在计算机数学，最近这十多年来，由于我的学生顾险峰以及其他朋友的缘故，他们叫我帮忙做些跟计算机有关的学问。我发觉，纯数学，尤其是几何学在计算机方面有很大的应用。所以我今天就滥竽充数，讲讲几何跟计算机数学的关系。 

　　一、现代几何的历史

　　首先，前面几分钟讲讲几何学历史。几何学一开始，就类似今天的人工智能，有很多工程上的应用以及产生的很多定理。不过随后欧几里得将当时主要的平面定理组合以后发现这些定理都可以由5个公理推出来。这是人类历史上很重要的一个里程碑，在很繁复的现象里，他找到了很简单但却很基本的五个公理，从而能将原来的这些公理全部推出来。我是很鼓励我们做人工智能的也能重复这个做法——从现在复杂多样的网络中找到它最简单的公理。

　　由于希腊人的工具不够，所以除了二次方程定义的图形（圆形、直线、椭圆等）以外，他们没有能力处理更一般的图形。一直到阿基米德，才开始做微积分的无限算法（积分体积），同时他们也开始做射影几何的算法。

　　微积分的出现使几何学进入了新纪元，微分几何也因此诞生。几何学在欧拉和高斯手上突飞猛进，变分方法和组合方法被大量地引入到几何学当中。

　　现代几何（近两百年的几何）主要发源于黎曼在1854年的博士论文，这篇论文奠定了整个现代几何的基础，他把几何图像看成一个抽象但是能够自足的空间。这个空间后来成为了现代物理的基础，现在物理中研究引力波等都是从黎曼这里开始的，没有黎曼这个空间，爱因斯坦不可能研究出来广义相对论。同时假如我们细看黎曼的这篇论文的话，就会发现，黎曼还认为离散空间也是一个很重要的空间。这个离散的空间包括了我们现在研究的图论，也用来研究宇宙万物可能产生的一切。所以即使是150年以后的今天，我们依然能看到黎曼的这个观点很重要。

　　二、对称的概念

　　几何学能够提供很多重要的想法，可以讲其影响是无所不在的。几何学的很多概念在高能物理和一般的物理学领域都产生重要的影响。其中一个重要的概念叫做“对称”。“对称”的概念是在1820年到1890年间由几个重要的数学家发展出来的。我们中国喜欢讲的阴阳，其实就是一个属于对称。在数学上有一个叫庞加莱对偶的概念，其实就是阴阳，但这个概念要比阴阳具体得多，同时也真正用在了数学的发展上。

　　19世纪，Sophis Lee发展的李群，也是物理学界最重要的工具之一，在现代物理中几乎没有一个学科可以离开李群的。

　　在几何学上，1870年的时候，伟大的数学家克莱因发表了《埃尔朗根纲领》，在这个纲领里克莱因提出用对称来统治几何的重要原理，随后产生了很多重要的几何学，包括仿射几何、保角几何和投影几何等。

　　这些几何对于图像处理都有密切的关系。我以及我的学生和朋友这十多年来就是用保角几何及种种几何来处理不同的图像。即使是当年看上去不重要的几何，现在实际上都有它重要的用处。这种种的计算都是从对称这个概念发展出来的。从大范围对称到小范围对称，这些在20世纪的基础研究中都有很成功的影响。

　　三、平行移动

　　另外一个很重要的概念，我想是很多做工程的人都没有注意到的，就是平行移动的概念。这个概念影响了整个数学界两千年。平行移动的概念其实就是一点和另外一点要有一个很好的比较的方法；计算机也好，图形学也好，在某一点上看到的事情要和其他点进行比较，比较的方法就叫平行移动。这也是一个很广泛、很重要的概念。现在在计算数学里面还没有大量的引进，但是在物理学界已经被大量地使用上了。所以我期望这些基本的概念以后能在计算机里面大量地使用。

　　四、几何学与计算机相互之间的影响

　　现在我们具体来讲一些的事情。现代几何为计算数学奠定了很多理论的基础，并且指导了计算机科学未来发展的方向。现代几何广泛应用到计算机的所有分支。举例来讲，计算机图形学、计算机视觉、计算机辅助几何设计、计算机网络等等都有广泛的应用。再例如，黎曼几何可以用来理解社交网络；现代几何理论也可以用来理解人工智能的特性。要记住，我们讲的几何并不是高中时代的几何，所有与图像或者网络有关的都是几何的一部分。

　　从另一方面来看，计算机学科的发展为现代几何提供了需求和挑战，也推动了跨学科的发展方向。例如：

• 人工智能中的机械定理证明推动了计算代数的发展；

• 数据安全、比特币、区块链的发展推动了代数数论、椭圆曲线和模形式的发展；

• 社交网络、大数据的发展催生了持续同调理论（persistent homology）的发展；

• 动漫、游戏的发展推动了计算共性几何学科的诞生和发展；

• 机器学习的发展推动了最优传输理论的发展等等。

　　五、计算机&几何学研究案例

　　我们下面举几个具体的例子，分别是图论、计算机图形学、计算机视觉、人工智能、深度学习等。这几个和几何都有密切的联系。

　　1、图论

　　我们先讲讲图论。图，就是一大堆顶点、一大堆边把它们连起来，这是最简单不过的事情。对于一个图，譬如交通图，我们要找出它们有着怎么样一个结构，什么地方比较拥挤。有时候我们也要研究怎么将这个图切成小部分，然后分解成简单的子图；如何衡量各个连通分支间的连接度；如何将图染色等。这些问题实际上都跟图上的特征函数有密切的关系。

　　图上的特征函数跟光滑图形上的特征函数有很类似的地方。我在40年前跟几个朋友，郑绍远、李伟光，做了一个工作，将光滑黎曼流形的特征函数推广到图上，得到了很好的结果。这些结果可以用来决定图上的连结的生成，研究图上的边创造过程，尤其是有个量的估值来控制在图上发散的过程。约束发散的过程可以应用到许多实际的过程中。我们还研究了图上的薛定谔方程，定义了图上的量子隧道概念。这些概念都是从物理上来的，被借用到图上。

　　假如我们在考虑有向图，就是每个点、每个边，给它一个方向，我们就可以将拓扑学整个引用到图上去，定义了图上的同调群。同调群可以用来研究图上密切的关系和它的内容。

　　现在我们来讲讲我们做的关于博弈理论的一个事情。进化图论为表达种群结构提供了数学工具：顶点代表个体，边代表个体的交互作用。图可以用来代表各种具有空间结构的群，例如细菌、动植物、组织结构、多细胞器官和社交网络。在进化过程中，每个个体依据自身的适应程度，进行繁殖病侵占到邻近顶点。图的拓扑反映了基因的演化——变异和选择的平衡。类似的，互联网是一个大网，一个非常复杂的网络，我可以在上面研究它的变化。社交行为的进化可以用进化博弈论来研究。个体和邻居博弈，根据收益而繁殖。个体繁殖速率受到自身与其他个体的交互作用影响，从而产生博弈的动态演化。其中心的问题就在于对于给定的图如何决定哪种策略会取得成功。

　　我们在今年年初的时候在nature上发了篇文章，我们得到一个结果，就是在任何给定的图上进行弱选择，自然选择从两种彼此竞争的策略中如何进行挑选，这个理论框架适用于人类决策，也适用于任何集群组织的生态演化。

　　我们从弱选择极限得到的结果，解释了何种组织结构导致何种行为。我们发现，如果存在成对的强纽带结构，合作就会大规模出现。我们用数学证明了社会学方面的一个结论：稳定的伙伴或者伴侣，对于形成合作型的社会起到了骨干作用。

　　2、计算机图形学：全局参数化 – 共形几何

　　下面我要讲的是“计算机图形学：全局参数化 – 共形几何”。这是我们发展了二十多年的一个学问。我和顾险峰从他还在哈佛念博士的时候（1999年）我们就开始做这个事情。

　　当我们将图形整体光滑映射到参数区域，使几何变得很小，会破坏掉整个图形；一般来讲这个要用手工来做，否则的话它变化非常大。针对这个问题，我们使用了纹理贴图、法向量贴图等等的方法。共性几何是一个很重要的从很古典的黎曼几何中产生的几何。

　　举例来讲，这个大卫的雕像，我们将它保角地映射到平面上去。它表面上看好像变化很大，但实际上变化不大，因为它是保角不变的。这在图像处理中是一个很重要的事情。举个例子来讲，从图上要画格点，因为我们画到平面上去以后，我们就可以将平面上画的很好的格点映射到脸上，就可以变成很漂亮的四方形的格点。这对工程处理有很多好处，其好处就是它将图上很小的圆映射到对方图上还是一个很小的圆，不会有扭曲，不会有太大的变化。

　　前面这些应用到一个数学上很重的定理，叫做庞加莱单值化定理，这是一个从黎曼时候开始的定理。就是讲映射的图形只跟它的拓扑性有关，这上面有三种几何，分别为：球面几何、欧氏几何、双曲几何。所有二维的几何，不管是什么样子的，我们都可以用这三种几何来分类。因此我们就可以将很复杂的事情很简单地描述出来。

　　上面这些我们得出了很好的结果。但是保角也有它的缺点，所以我们也发展了第二类映射，我们使得面元被保持，而角度不一定被保持。保角映射有时候可能将一个面拉的很远，左手边是保角映射，右手边是保面元映射。右面的图在不同的情形下会得出很好的结果。

　　3、计算机视觉，表情追踪 – 拟共映射

　　共性映射也可以应用到表情识别和追踪当中。我们可以自动地找到球面上曲面间的光滑映射，使得特征点匹配，使映射带来的变化很小。这是我们得到的一个很重要的结果。 

　　因此，我们可以用来追踪表情，表情捕捉。一个人他在笑、在哭、在种种不同的表现的时候，我们能够得到他的重要的面部特征，主要的方法就是我们将它映射到平面上，然后用共形映射或拟共形映射来研究它。这些都是很重要的数学工具，在计算上也有很重要的应用。

　　拟共形映射到目前来讲，纯数学家把它看得还是非常重要的，它不是一个正则方程，而是一个伪正则方程，也即Beltrami方程。这个方程在我们研究图像变形时在数学上是非常重要的，所以我们应用到图形处理里面去也得到很重要的结果。我们可在微分同胚的空间进行变化到最优的映射。它对医疗和动漫都有很重要的应用。

　　4、计算力学 – 六面体网格生成，叶状结构理论

　　我们也可以用同样的变化（保角映射）来产生六面体网格的生成和叶状结构理论。

　　这是在一只兔子上找到的好的网格。但是这个网格会产生一些奇异点（拓扑学的缘故）。针对这些奇异点，我们就做了一些研究，得出了很好的结论。

　　再比如，我们看这个曲面，在这个曲面上我们画出一些叶状的结构，可是它也有一定的奇异点。我们将这些奇异点分类，得出了一些在计算机科学上有意义的结论。

此外，全纯二次微分的网络中间有个六边形的变化。

　　5、数字几何处理-几何压缩：蒙日-安培理论，几何逼近理论

　　下面我们来看计算机的几何压缩中的蒙日-安培理论以及几何逼近理论。如何压缩复杂几何数据，同时保证几误差最小，保证黎曼度量、曲率测度、微分算子的收敛性，这些都是很重要的问题。我们用了很多共形映射的方法将曲面映射到平面去；再用蒙日-安培方程，将高曲率区域放大；随后重采样，在共性参数域上计算Delaunay三角剖分。这样得到的简化多面体网格就能够保证黎曼度量、曲率测度、微分算子收敛。

　　6、区块链：数字安全，椭圆曲线理论

　　这方面很多人都知道，这部分我就跳过去不再讲了。

　　7、人工智能

　　目前机器学习算法需要大量的样本。虽然现在比从前进步得多了，但规模还是很庞大。所以我们的想法是，让理论来帮忙处理这种复杂的数据学习。

　　在机器学习中有很多统计的内容，但是很多内容我们都不是很了解它是如何产生的。所以我们需要用一些比较严格的数学的理论来从这些复杂的现象中抽取出它们的本质。我们今天介绍一下用几何的方法来研究对抗生成网络（GAN）的事情。

　　生成对抗网络GAN（Generative Adversarial Networks）其实就是以己之矛克己之盾，在矛盾中发展，使得矛更加锋利，盾更加强韧。这里的盾就被称为判别器（Descriminator），矛被称为生成器（Generator）。生成器G一般是将一个随机变量（例如高斯分布或者均匀分布），通过参数化的概率生成模型（通常是用一个深度神经网进行参数化），进行概率分布的逆变换采样，从而得到一个生成的概率分布。判别器D也通常采用深度卷积神经网络。

　　举个例子来讲，有个概率分布u，u是基本的白噪音，影射到右手边的图片，一个概率分布v。我们从映射里看到GAN的问题其实就是：在两个概率分布u和v之间，找到一个最优的传输映射，从一个空间到另外一个空间，使它的概率分布是保持的。

　　u通过phi映射到v上去，同时我们要将它传输的代价变得最小。这样的变化是我们所需要的，因为这就不再需要像刚才所说的矛盾变化来达到最好的结果。我们知道，映射可以用一个方程来解决，所以我们其实就是要找一个凸函数U，它的梯度是我们的映射函数phi，它满足一个方程：蒙日-安培方程。

　　我们可以通过对这个方程进行求解的方式来找到最优传输映射，所以就节省很多生成对抗的时间。蒙日-安培方程本身其实是等价于微分几何中的亚历山大定理的。60年代就有人处理过这个方程，我自己也做过这个方程，前几年顾险峰跟他的学生也和我一起对它做了一个计算。

　　对抗生成网络实质上就是用深度神经网络来计算概率测度之间的变换。虽然规模宏大，但是数学本质并不复杂。应用相对成熟的最优传输理论和蒙日-安培理论，我们可以为机器学习的黑箱给出透明的几何解释，这有助于设计出更为高效和可靠的计算方法。

　　六、总结

　　我们看到现代数学和计算机科学的发展紧密相关，共形几何的单值化定理、蒙日-安培理论、最优传输理论等现代几何中的定理应用到计算机科学中的很多领域。我希望我们能够将更多那些表面上看来很高深的数学应用到我们日常的计算机上去，不但是能够有效地提出计算机的算法，同时也能够给它一个理论的基础。人工智能需要一个坚实的理论基础，否则它的发展会有很大困难。

引文摘要：

1.AI 跟 IT 技术的主要差别是什么？简单的说，就是 AI 对数学要求较高，对编程要求较低，而 IT 开发对于编程要求高，特别是对编程经验要求高，但对数学要求不高。

2.毫不夸张的说，在 AI 学习的入门阶段，数学是主要的攻坚对象，任何胸有大志的 AI 学习者都不要幻想绕过数学。

3.首先，数学不过关的人在 AI 这个圈子里是无法参与交流的；数学不过关而只能调参数的人，实践当中并不好用；其次，数学不过关而只能调参数的人，实践当中并不好用。第三，即便是调参这件事情本身，懂不懂数学也是有很大差别的。

4.对于绝大多数 AI 工程师来说，还是应该以机器学习为主导，对于其中涉及的数学知识形成理解，打牢基础，突出重点，适度拓宽，这就算过关了。

查看全文

引文摘要：

1. 人工智能让现有优势荡然无存。人工智能就是通过机器进行深度学习来工作，而这种学习过程就是大量地识别和记忆已有的知识积累。这样的话，它可以替代甚至超越那些通过死记硬背、大量做题而掌握知识的人脑。而死记硬背、大量做题正是我们目前培养学生的通常做法。所以，一个很可能发生的情况是，未来的人工智能会让我们的教育制度下培养学生的优势荡然无存。
2. 知识越多未必创造力越强。知识越多未必创造力越强。“创造性思维=知识×好奇心和想象力”。这个简单的公式告诉我们，知识越多未必创造力越强。因为人接受的教育越多，知识积累多了，但好奇心和想象力可能减少，所以创造力并非随着受教育时间的增加而增加。儿童时期的好奇心和想象力特别强，但是随着受教育的增加，好奇心和想象力通常会逐渐递减。

3. 功利主义扼杀了创造性思维。我把创新的动机分为三个层次，分别代表三种价值取向：一、短期功利主义；二、长期功利主义；三、内在价值的非功利主义。后面的比前面的有更高的追求。对短期功利主义者而言，创新是为了发论文、申请专利、公司上市；对长期功利主义者而言，创新有更高的追求，为了填补空白、争国内一流、创世界一流；而对内在价值的非功利主义者而言，创新有更高的追求：追求真理、改变世界、让人变得更加幸福。

查看全文

数学篇

1. Introduction to Linear Algebra

    

2. Linear Algebra and its Applications

    

3. A First Course in Probability（8th edition）

    

4. Probability Theory: The Logic of Science

    

5. Statistical Inference

    

6. Convex Optimization

    

7. Elements of Information Theory

    

机器学习篇

1. Machine Learning

    

2. Elements of Statistical Learning

    

3. Pattern Recognition and Machine Learning

    

4. Information Theory, Inference and Learning Algorithms

    

引文摘要：

1、量子计算机的横空出世，使得人类拥有的计算能力，正处在指数级增长的前夜。

2、新一代互联网在全球范围的推广应用，将让以人与人链接为特征的互联网，转变为人与人、人与物、物与物链接三位一体的物联网，大数据将井喷式涌现。

3、人工智能真是来得太快了，简直是猝不及防！甚至，连艺术领域，这个原本是人类最自信不会被人工智能篡夺的领域，也开始告急了。

4、面对人工智能，我们改变不了科技的进程，但是，我们可以改变自己，以及我们下一代的知识结构。有学者分析，面对步步逼近的人工智能，你有三个选择：

• 要么积累财富，成为资本大鳄
• 积累名气，成为独特个体
• 积累知识，成为更高深技术的掌握者

查看全文