计算机重要人物及算法的力量

1、计算机科学家-图灵o 图灵（图灵（1912.6.23-1954.6.27）是英国著名的）是英国著名的数学家和逻辑学家，被称为计数学家和逻辑学家，被称为计算机科学之父、人工智能之父，算机科学之父、人工智能之父，是计算机逻辑的奠基者，提出是计算机逻辑的奠基者，提出了了“图灵机图灵机”和和“图灵测试图灵测试”等重要概念。人们为纪念其在等重要概念。人们为纪念其在计算机领域的卓越贡献而设立计算机领域的卓越贡献而设立“图灵奖图灵奖”。计算机科学家-Dijkstra o 艾兹格艾兹格W迪科斯彻迪科斯彻 （Edsger Wybe Dijkstra，1930年年5月月11日日2002年年8月月6日）荷兰人。日）

2、荷兰人。 计算机科学家，毕业就职于荷兰计算机科学家，毕业就职于荷兰Leiden大学，早年钻研物理及数大学，早年钻研物理及数学，而后转为计算学。曾在学，而后转为计算学。曾在1972年获得过素有计算机科学界的诺贝年获得过素有计算机科学界的诺贝尔奖之称的图灵奖，之后，他还获尔奖之称的图灵奖，之后，他还获得过得过1974年年 AFIPS Harry Goode Memorial Award、1989年年ACM SIGCSE计算机科计算机科学教育教学杰出贡献奖、以及学教育教学杰出贡献奖、以及2002年年ACM PODC最具影响力最具影响力论文奖。论文奖。计算机科学家-约翰冯诺依曼 o 1903年年12月

3、月28日，在布达佩斯诞日，在布达佩斯诞生了一位神童，这不仅给这个家庭生了一位神童，这不仅给这个家庭带来了巨大的喜悦，也值得整个计带来了巨大的喜悦，也值得整个计算机界去纪念。正是他，开创了现算机界去纪念。正是他，开创了现代计算机理论，其体系结构沿用至代计算机理论，其体系结构沿用至今，而且他早在今，而且他早在40年代就已预见到年代就已预见到计算机建模和仿真技术对当代计算计算机建模和仿真技术对当代计算机将产生的意义深远的影响。他，机将产生的意义深远的影响。他，就是约翰就是约翰冯冯诺依曼（诺依曼（John Von Neumann）。）。计算机科学家-约翰麦卡锡 o 1927年年9月月4日麦卡锡生于日麦

4、卡锡生于美国波士顿一个共产党家庭，美国波士顿一个共产党家庭，父母的工作性质决定全家需父母的工作性质决定全家需不断搬迁，从波士顿迁到纽不断搬迁，从波士顿迁到纽约，然后又到了洛杉矶。他约，然后又到了洛杉矶。他因在人工智能领域的贡献而因在人工智能领域的贡献而在在1971年获得图灵奖。实年获得图灵奖。实际上，正是他在际上，正是他在1955年的年的达特矛斯会议上提出了达特矛斯会议上提出了“人人工智能工智能”这个概念。这个概念。1959年，麦卡锡开发年，麦卡锡开发了著名的了著名的LISP语言，语言，成为人工智能界第一个成为人工智能界第一个最广泛流行的语言。最广泛流行的语言。 计算机科学家-姚期智姚期智o

5、姚期智姚期智(Andrew Chi-Chih Yao)，世界，世界著名计算机学家，著名计算机学家，2000年图灵奖得主，美年图灵奖得主，美国科学院院士，美国科学与艺术学院院士，国科学院院士，美国科学与艺术学院院士，中国科学院外籍院士，清华大学高等研究中中国科学院外籍院士，清华大学高等研究中心教授。心教授。1967年获得台湾大学物理学士学年获得台湾大学物理学士学位，位，1972年获得美国哈佛大学物理博士学年获得美国哈佛大学物理博士学位，位，1975年获得美国伊利诺依大学计算机年获得美国伊利诺依大学计算机科学博士学位。科学博士学位。1975年至年至1986年曾先后年曾先后在美国麻省理工学院数学系、

6、斯坦福大学计在美国麻省理工学院数学系、斯坦福大学计算机系、加利福尼亚大学伯克利分校计算机算机系、加利福尼亚大学伯克利分校计算机系任助教授、教授。系任助教授、教授。1986年至年至2004年在年在普林斯顿大学计算机科学系担任普林斯顿大学计算机科学系担任Wiliam and Edna Macaleer工程与应用科学教工程与应用科学教授。授。2004年起在清华大学任全职教授。年起在清华大学任全职教授。IT精英-李开复李开复o 李开复（李开复（1961年年12月月3日）是一日）是一位信息产业的执行官和计算机科学位信息产业的执行官和计算机科学的研究者。的研究者。1998年，李开复加盟微年，李开复加盟微软

7、公司，并随后创立了微软中国研软公司，并随后创立了微软中国研究院（现微软亚洲研究院）。究院（现微软亚洲研究院）。2005年年7月月20日加入日加入Google（谷歌）（谷歌）公司，并担任公司，并担任Google（谷歌）全球（谷歌）全球副总裁兼中国区总裁一职。副总裁兼中国区总裁一职。2009年年9月月4日，宣布离职并创办创新工场日，宣布离职并创办创新工场任董事长兼首席执行官。任董事长兼首席执行官。李开复之算法的力量（1）o 算法是计算机科学领域最重要的基石之一，但却受到了国算法是计算机科学领域最重要的基石之一，但却受到了国内一些程序员的冷落。许多学生看到一些公司在招聘时要内一些程序员的冷落。许多学

8、生看到一些公司在招聘时要求的编程语言五花八门就产生了一种误解，认为学计算机求的编程语言五花八门就产生了一种误解，认为学计算机就是学各种编程语言，或者认为，学习最新的语言、技术、就是学各种编程语言，或者认为，学习最新的语言、技术、标准就是最好的铺路方法。其实大家都被这些公司误导了。标准就是最好的铺路方法。其实大家都被这些公司误导了。编程语言虽然该学，但是学习计算机算法和理论更重要，编程语言虽然该学，但是学习计算机算法和理论更重要，因为计算机算法和理论更重要，因为计算机语言和开发平因为计算机算法和理论更重要，因为计算机语言和开发平台日新月异，但万变不离其宗的是那些算法和理论，例如台日新月异，但万变

9、不离其宗的是那些算法和理论，例如数据结构、算法、编译原理、计算机体系结构、关系型数数据结构、算法、编译原理、计算机体系结构、关系型数据库原理等等。在据库原理等等。在“开复学生网开复学生网”上，有位同学生动地把上，有位同学生动地把这些基础课程比拟为这些基础课程比拟为“内功内功”，把新的语言、技术、标准，把新的语言、技术、标准比拟为比拟为“外功外功”。整天赶时髦的人最后只懂得招式，没有。整天赶时髦的人最后只懂得招式，没有功力，是不可能成为高手的功力，是不可能成为高手的 李开复之算法的力量（2）o 算法与我算法与我o 当我在当我在19801980年转入计算机科学系时，还没有多少人年转入计算机科学系时

10、，还没有多少人的专业方向是计算机科学。有许多其他系的人嘲笑的专业方向是计算机科学。有许多其他系的人嘲笑我们说：我们说：“知道为什么只有你们系要加一个知道为什么只有你们系要加一个科科学学，而没有，而没有物理科学系物理科学系或或化学科学系化学科学系吗？吗？因为人家是真的科学，不需要画蛇添足，而你们自因为人家是真的科学，不需要画蛇添足，而你们自己心虚，生怕不己心虚，生怕不科学科学，才这样欲盖弥彰。，才这样欲盖弥彰。”其其实，这点他们彻底弄错了。真正学懂计算机的人实，这点他们彻底弄错了。真正学懂计算机的人（不只是（不只是“编程匠编程匠”）都对数学有相当的造诣，既）都对数学有相当的造诣，既能用科学家的严

11、谨思维来求证，也能用工程师的务能用科学家的严谨思维来求证，也能用工程师的务实手段来解决问题实手段来解决问题而这种思维和手段的最佳演而这种思维和手段的最佳演绎就是绎就是“算法算法”。 李开复之算法的力量（3）o 记得我读博时写的记得我读博时写的OthelloOthello对弈软件获得了世界冠对弈软件获得了世界冠军。当时，得第二名的人认为我是靠侥幸才打赢他，军。当时，得第二名的人认为我是靠侥幸才打赢他，不服气地问我的程序平均每秒能搜索多少步棋，当不服气地问我的程序平均每秒能搜索多少步棋，当他发现我的软件在搜索效率上比他快他发现我的软件在搜索效率上比他快6060多倍时，才多倍时，才彻底服输。为什么在

12、同样的机器上，我可以多做彻底服输。为什么在同样的机器上，我可以多做6060倍的工作呢？这是因为我用了一个最新的算法，能倍的工作呢？这是因为我用了一个最新的算法，能够把一个指数函数转换成四个近似的表，只要用常够把一个指数函数转换成四个近似的表，只要用常数时间就可得到近似的答案。在这个例子中，是否数时间就可得到近似的答案。在这个例子中，是否用对算法才是能否赢得世界冠军的关键。用对算法才是能否赢得世界冠军的关键。 李开复之算法的力量（4）o 还记得还记得19881988年贝尔实验室副总裁亲自来访问我的学校，目的年贝尔实验室副总裁亲自来访问我的学校，目的就是为了想了解为什么他们的语音识别系统比我开发的

13、慢几十就是为了想了解为什么他们的语音识别系统比我开发的慢几十倍，而且，在扩大至大词汇系统后，速度差异更有几百倍之多。倍，而且，在扩大至大词汇系统后，速度差异更有几百倍之多。他们虽然买了几台超级计算机，勉强让系统跑了起来，但这么他们虽然买了几台超级计算机，勉强让系统跑了起来，但这么贵的计算资源让他们的产品部门很反感，因为贵的计算资源让他们的产品部门很反感，因为“昂贵昂贵”的技术的技术是没有应用前景的。在与他们探讨的过程中，我惊讶地发现一是没有应用前景的。在与他们探讨的过程中，我惊讶地发现一个个O(nO(n* *m)m)的动态规划的动态规划(dynamic programming)(dynamic

14、 programming)居然被他们做成居然被他们做成了了O(nO(n* *n n* *m)m)。更惊讶的是，他们还为此发表了不少文章，甚至。更惊讶的是，他们还为此发表了不少文章，甚至为自己的算法起了一个很特别的名字，并将算法提名到一个科为自己的算法起了一个很特别的名字，并将算法提名到一个科学会议里，希望能得到大奖。当时，贝尔实验室的研究员当然学会议里，希望能得到大奖。当时，贝尔实验室的研究员当然绝顶聪明，但他们全都是学数学、物理或电机出身，从未学过绝顶聪明，但他们全都是学数学、物理或电机出身，从未学过计算机科学或算法，才犯了这么基本的错误。我想那些人以后计算机科学或算法，才犯了这么基本的错误

15、。我想那些人以后再也不会嘲笑学计算机科学的人了吧！再也不会嘲笑学计算机科学的人了吧！ 李开复之算法的力量（5）o网络时代的算法网络时代的算法o有人也许会说：有人也许会说：“今天计算机这么快，算法还重要吗？今天计算机这么快，算法还重要吗？”其实其实永远不会有太快的计算机，因为我们总会想出新的应用。虽然永远不会有太快的计算机，因为我们总会想出新的应用。虽然在摩尔定律的作用下，计算机的计算能力每年都在飞快增长，在摩尔定律的作用下，计算机的计算能力每年都在飞快增长，价格也在不断下降。可我们不要忘记，需要处理的信息量更是价格也在不断下降。可我们不要忘记，需要处理的信息量更是呈指数级的增长。现在每人每天都

16、会创造出大量数据（照片，呈指数级的增长。现在每人每天都会创造出大量数据（照片，视频，语音，文本等等）。日益先进的纪录和存储手段使我们视频，语音，文本等等）。日益先进的纪录和存储手段使我们每个人的信息量都在爆炸式的增长。互联网的信息流量和日志每个人的信息量都在爆炸式的增长。互联网的信息流量和日志容量也在飞快增长。在科学研究方面，随着研究手段的进步，容量也在飞快增长。在科学研究方面，随着研究手段的进步，数据量更是达到了前所未有的程度。无论是三维图形、海量数数据量更是达到了前所未有的程度。无论是三维图形、海量数据处理、机器学习、语音识别，都需要极大的计算量。在网络据处理、机器学习、语音识别，都需要极

17、大的计算量。在网络时代，越来越多的挑战需要靠卓越的算法来解决。时代，越来越多的挑战需要靠卓越的算法来解决。李开复之算法的力量（6）o 再举另一个网络时代的例子。在互联网和手机搜索，如再举另一个网络时代的例子。在互联网和手机搜索，如果要找附近的咖啡店，那么搜索引擎该怎么处理这个请果要找附近的咖啡店，那么搜索引擎该怎么处理这个请求呢？最简单的办法就是把整个城市的咖啡馆都找出来，求呢？最简单的办法就是把整个城市的咖啡馆都找出来，然后计算出它们的所在位置与你之间的距离，再进行排然后计算出它们的所在位置与你之间的距离，再进行排序，然后返回最近的结果。但该如何计算距离呢？图论序，然后返回最近的结果。但该如

18、何计算距离呢？图论里有不少算法可以解决这个问题。里有不少算法可以解决这个问题。o 这么做也许是最直观的，但绝对不是最迅速的。如果一这么做也许是最直观的，但绝对不是最迅速的。如果一个城市只有为数不多的咖啡馆，那么这么做应该没什么个城市只有为数不多的咖啡馆，那么这么做应该没什么问题，反正计算量不大。但如果一个城市里有很多咖啡问题，反正计算量不大。但如果一个城市里有很多咖啡馆，又有很多用户都需要类似的搜索，那么服务器所承馆，又有很多用户都需要类似的搜索，那么服务器所承受的压力就大多了。在这种情况下，我们该怎样优化算受的压力就大多了。在这种情况下，我们该怎样优化算法呢？法呢？ 李开复之算法的力量（7）

19、o 首先，我们可以把整个城市的咖啡馆做一次首先，我们可以把整个城市的咖啡馆做一次“预处预处理理”。比如，把一个城市分成若干个。比如，把一个城市分成若干个“格子格子(grid)”(grid)”，然后根据用户所在的位置把他放到某一，然后根据用户所在的位置把他放到某一个格子里，只对格子里的咖啡馆进行距离排序。个格子里，只对格子里的咖啡馆进行距离排序。o 问题又来了，如果格子大小一样，那么绝大多数结问题又来了，如果格子大小一样，那么绝大多数结果都可能出现在市中心的一个格子里，而郊区的格果都可能出现在市中心的一个格子里，而郊区的格子里只有极少的结果。在这种情况下，我们应该把子里只有极少的结果。在这种情况

20、下，我们应该把市中心多分出几个格子。更进一步，格子应该是一市中心多分出几个格子。更进一步，格子应该是一个个“树结构树结构”，最顶层是一个大格，最顶层是一个大格整个城市，整个城市，然后逐层下降，格子越来越小，这样有利于用户进然后逐层下降，格子越来越小，这样有利于用户进行精确搜索行精确搜索如果在最底层的格子里搜索结果不如果在最底层的格子里搜索结果不多，用户可以逐级上升，放大搜索范围。多，用户可以逐级上升，放大搜索范围。 李开复之算法的力量（8）o 上述算法对咖啡馆的例子很实用，但是它具有通用上述算法对咖啡馆的例子很实用，但是它具有通用性吗？答案是否定的。把咖啡馆抽象一下，它是一性吗？答案是否定的。

21、把咖啡馆抽象一下，它是一个个“点点”，如果要搜索一个，如果要搜索一个“面面”该怎么办呢？比该怎么办呢？比如，用户想去一个水库玩，而一个水库有好几个入如，用户想去一个水库玩，而一个水库有好几个入口，那么哪一个离用户最近呢？这个时候，上述口，那么哪一个离用户最近呢？这个时候，上述“树结构树结构”就要改成就要改成“r-tree”r-tree”，因为树中间的每，因为树中间的每一个节点都是一个范围，一个有边界的范围。一个节点都是一个范围，一个有边界的范围。o 通过这个小例子，我们看到，应用程序的要求千变通过这个小例子，我们看到，应用程序的要求千变万化，很多时候需要把一个复杂的问题分解成若干万化，很多时候

22、需要把一个复杂的问题分解成若干简单的小问题，然后再选用合适的算法和数据结构。简单的小问题，然后再选用合适的算法和数据结构。李开复之算法的力量（9）o并行算法：并行算法：GoogleGoogle的核心优势的核心优势o上面的例子在上面的例子在GoogleGoogle里就要算是小里就要算是小casecase了！每天了！每天GoogleGoogle的网站的网站要处理十亿个以上的搜索，要处理十亿个以上的搜索，GMailGMail要储存几千万用户的要储存几千万用户的2G2G邮箱，邮箱，Google EarthGoogle Earth要让数十万用户同时在整个地球上遨游，并将合要让数十万用户同时在整个地球上遨

23、游，并将合适的图片经过互联网提交给每个用户。如果没有好的算法，这适的图片经过互联网提交给每个用户。如果没有好的算法，这些应用都无法成为现实。些应用都无法成为现实。o在这些的应用中，哪怕是最基本的问题都会给传统的计算带来在这些的应用中，哪怕是最基本的问题都会给传统的计算带来很大的挑战。例如，每天都有十亿以上的用户访问很大的挑战。例如，每天都有十亿以上的用户访问GoogleGoogle的网的网站，使用站，使用GoogleGoogle的服务，也产生很多很多的日志的服务，也产生很多很多的日志(Log)(Log)。因为。因为LogLog每份每秒都在飞速增加，我们必须有聪明的办法来进行处每份每秒都在飞速增

24、加，我们必须有聪明的办法来进行处理。我曾经在面试中问过关于如何对理。我曾经在面试中问过关于如何对LogLog进行一些分析处理的进行一些分析处理的问题，有很多面试者的回答虽然在逻辑上正确，但是实际应用问题，有很多面试者的回答虽然在逻辑上正确，但是实际应用中是几乎不可行的。按照它们的算法，即便用上几万台机器，中是几乎不可行的。按照它们的算法，即便用上几万台机器，我们的处理速度都根不上数据产生的速度。我们的处理速度都根不上数据产生的速度。李开复之算法的力量（10）o 那么那么GoogleGoogle是如何解决这些问题的？是如何解决这些问题的？o 首先，在网络时代，就算有最好的算法，也要能在首先，在网

25、络时代，就算有最好的算法，也要能在并行计算的环境下执行。在并行计算的环境下执行。在GoogleGoogle的数据中心，我的数据中心，我们使用的是超大的并行计算机。但传统的并行算法们使用的是超大的并行计算机。但传统的并行算法运行时，效率会在增加机器数量后迅速降低，也就运行时，效率会在增加机器数量后迅速降低，也就是说，十台机器如果有五倍的效果，增加到一千台是说，十台机器如果有五倍的效果，增加到一千台时也许就只有几十倍的效果。这种事半功倍的代价时也许就只有几十倍的效果。这种事半功倍的代价是没有哪家公司可以负担得起的。而且，在许多并是没有哪家公司可以负担得起的。而且，在许多并行算法中，只要一个结点犯错

26、误，所有计算都会前行算法中，只要一个结点犯错误，所有计算都会前功尽弃。功尽弃。李开复之算法的力量（11）o那么那么GoogleGoogle是如何开发出既有效率又能容错的并行计算的呢？是如何开发出既有效率又能容错的并行计算的呢？oGoogleGoogle最资深的计算机科学家最资深的计算机科学家Jeff DeanJeff Dean认识到，认识到，GoogleGoogle所需所需的绝大部分数据处理都可以归结为一个简单的并行算法：的绝大部分数据处理都可以归结为一个简单的并行算法：Map and ReduceMap and Reduce（http:/ and ReduceMap and Reduce的另外一大特色是的另外一大特色是它可以利用大批廉价的机器组成功能强大的它可以利用大批廉价的