|
数学算法能统治世界？ 软件正在统治世界，而软件的核心是算法；互联网即将统治世界，其管理、使用的核心也是算法；算法统治着软件和互联网，所以说“算法统治世界”这句话应是有一定道理的。 算法决定了你用Google搜索的结果，算法决定了新浪微博向你展示的话题，算法决定了Netflix向你推荐的电影，算法决定了你QQ对话窗弹出的横幅广告等等，这些都意味着“算法在统治世界”。 我们花费了大量时间、巨大的投资来研究新算法，调整、改善旧算法，寻找更好的算法以便集成到应用中去，但是有些现成的算法却罕有人知晓，最后却是“众里寻她千百度，那人却在灯火阑珊处”——往往答案就在眼前，但很多别人已经研究多年的算法自己却从未听说过。这里，从千千万万算法中，整理出统治世界的十大算法的小型列表，排名不分先后，供参考。 哪个排序算法最好？这取决于需求，也是为什么要将归并排序、快速排序和堆排序算法这三个使用频率较高的排序算法置于一处的原因。你可能比较偏爱其中的一个，但它们都是同等重要的。 归并排序算法是目前为止我们拥有的最重要的算法之一。它是一种基于比较的排序算法，使用分治法解决那些原本复杂度为O(N2)的问题。归并排序是由数学家John von Neumann于1945年提出的。 快速排序是解决排序问题的另一种途径，它使用就地分解算法，同时它也是一种分治算法。这个算法的问题在于它是不稳定的排序算法，但它在基于内存的数组排序上确实非常高效。 最后，堆排序算法使用一个优先队列降低数据的查找时间，它也是一种就地排序算法，同样也是不稳定的排序算法。 相较于曾经使用的其他排序算法（如冒泡排序），上述算法带来了显著的改进。事实上，多亏了它们，今天我们才有了数据挖掘、人工智能、链接分析，以及世界上大部分的计算机工具，也包括网络在内。 整个数字世界都在使用这一简单而又强大的算法，将信号从频域转换为时域，反之亦然。互联网、你的WIFI、智能手机、电话、计算机、路由器、卫星，几乎所有内置计算机的东西都会以各种方式使用这些算法实现各自的功能。 毫无夸张地说，如果没有这个算法，当今互联网将无法有效工作。这是一种图搜索算法，它被广泛应用在能够建模为图的问题中，用以找出两个节点之间的最短路径。 目前，即便我们已经拥有了解决最短路径问题的更好方法，Dijkstra算法依然在那些重视稳定性的系统中得到应用。 如果没有信息加密和网络安全，互联网不会像现在那么重要。在信息加密领域，有一个算法始终是世界上最重要的算法之一，它就是RSA算法。这个算法是由RSA公司的创始人建立，它使信息加密惠及千家万户，奠定了当今信息加密的运作基础。RSA算法用来解决一个简单而又复杂的问题：怎样在不同平台和终端用户之间共享公钥，继而实现信息加密。其实，这个问题也没完全解决，还需要做更多工作。 准确地说，它不能称之为算法，它是美国国家标准暨技术学会定义的加密散列函数族中的一员，但是这族算法对整个世界的运作至关重要。从你的应用商店，你的邮件，你的杀毒软件，到你的浏览器等等，所有这些都在使用安全哈希算法，它能判断你是否下载了你想要的东西，也能判断你是否是中间人攻击或网络钓鱼攻击的受害者。 这是在计算机领域被大量使用的数学算法，没有这个算法，信息加密会更不安全。该算法定义了一系列步骤，得到将一合数分解为更小因子的质数分解式。这被认为是一种FNP问题，它是NP分类问题的延伸，极其难以解决。 许多加密协议（如RSA算法）都基于这样一个原理：对大的合数作因式分解是非常困难的。如果一个算法能够快速地对任意整数进行因式分解，RSA的公钥加密体系就会失去其安全性。 量子计算的诞生使我们能够更容易地解决这类问题，同时它也打开了一个全新的领域，使得我们能够利用量子世界中的特性来保证系统安全。 在互联网时代，分析不同实体间的关系是相当重要的。从搜索引擎，社交网络，到营销分析工具，每个人都在不停寻找互联网的真正结构。 链接分析背后的理念非常简单，以矩阵形式描绘出一张图，将问题转换为特征值问题。特征值是一种很好的渠道，它有助于展现图的结构以及每个节点的相对重要性。该算法是由Gabriel Pinski和Francis Narin于1976年建立的。 谁在使用这个算法？Google的Page Rank算法，Facebook向你展示的新闻提要（这就是为什么Facebook的新闻提要不是算法，只是使用算法的结果而已），Google 和Facebook的推荐，LinkedIn的工作和联系人推荐，Netflix和Hulu的电影，YouTuBe的视频，等等。虽然每个都有不同的目标和参数，但它们背后的数学理念是相同的。 你是否曾经用过飞机、汽车、卫星服务或手机网络？你是否曾经在工厂工作或是看见过机器人？如果回答是肯定的，那么你应该已经见识过这个算法了。 大体上，这个算法使用一种控制回路反馈机制，将期望输出信号和实际输出信号之间的错误最小化。无论何处，只要你需要进行信号处理，或者你需要一套电子系统，用来自动化控制机械、液压或热力系统，这个算法都会有用武之地。可以这样说，如果没有这个算法，现代文明将不复存在。 要判断哪种数据压缩算法最为重要是很困难的，因为它取决于不同的应用环境。它们可以应用在zip和mp3上，也可以应用在JPEG和MPEG-2上。但众所周知，在所有结构中这些算法都极其重要。 除了显而易见的zip文件，在哪我们能够找到这些算法？在电子游戏、视频、音乐、数据存储、云计算、数据库等等地方都能找到这些算法。可以说，数据压缩算法处处可见，它们使系统成本更低、效率更高。 现在我们还没有一个“真正的”随机数生成器，但我们已经有了一些伪随机数生成器，这就够用了。随机数生成器的用途非常广泛，从互联联络、数据加密、安全哈希算法、电子游戏、人工智能、优化分析，到问题的初始条件、金融等等，都有它们的身影。 最后再强调一下，上面这个列表仅供参考，它并不完整。因为在机器学习、矩阵乘法、分类化等领域也有一些算法，它们对我们的世界同样重要，但在这里还没有提到。 张建中，一个毕业于北京大学数学力学系，在中国科学院计算所、计算中心和网络中心工作过，在澳大利亚科工组织DMS、香港浸会学院数学系和中国21世纪议程管理中心等处工作过，多次获国家和中科院科技奖并享受政府特殊津贴的退休老头。 另一篇： 影响计算机算法世界的十位大师 1、伟大的智者——Don E.Knuth，中文名：高德纳 (1938-)算法和程序设计技术的先驱者。Oh,God！一些国外网站这样评价他。一般说来，不知道此人的程序员是不可原谅的。其经典著作《计算机程序设计艺术》更是被誉为算法中“真正”的圣经，像KMP和LR(K)这样令人不可思议的算法，在此书比比皆是。难怪连Bill Gates都说：“如果能做对书里所有的习题，就直接来微软上班吧！” 对于Don E.Knuth本人，一生中获得的奖项和荣誉不计其数，包括图灵奖，美国国家科学金奖，美国数学学会斯蒂尔将（AMS Steel Prize），以及发明先进技术荣获的极受尊重的京都奖（KyotoPrize）等等，写过19部书和160余篇论文，每一篇著作都能用影响深远来形容。 Don E.Knuth也被公认是美国最聪明的人之一。当年他上大学的时候，常写些各种各样的编译器来挣外快，只要是他参加的编程比赛，总是第一名，同时也是世上 少有的编程达到40年以上的程序员之一。他除了是技术与科学上的泰斗外，更是无可非议的写作高手，技术文章堪称一绝，文风细腻，讲解透彻，思路清晰而且没 有学究气，估计这也是《计算机程序设计艺术》被称为圣经的原因之一。 2、首席算法官Udi Manber 世界上还有如此奇怪的职位？但是对于Amazon乃至Google来说，这一点也不奇怪。Udi Manber，这位前Amazon的“首席算法官”，现在是Google负责工程事务的副总裁。他研究WWW的应用程序、搜索以及隐藏在这背后的算法设 计。在此期间，他与其他人共同开发了Agrep、Glimpse和Harvest等Unix上的搜索软件。1998年，Udi成为了Yahoo!的首席科 学家。2002年，Amazon创造性地给了Udi“首席算法官”的职位，和Udi为Amazon的“SearchInside the Book”搜索项目所做的工作相得益彰。 Udi还因为他所著的Introduction to Algorithms——A Creative Approach而被大家称道。 3、谦逊的长者——Edsger Wybe Dijkstra 1930年出生于荷兰阿姆斯特丹，2002年逝世于荷兰纽南。他在祖国荷兰获得数据和物理学学士，理论物理博士学位，2000年退休前一直是美国Texas大学的 计算机科学和数学教授。以发现了图论中的最短路径算法（Dijkstra算法）而闻名于世，1972年因为ALGOL第二代编程语言而获得图灵奖。“Go To StatementConsidered Harmful”(EWD215)也是被广为传颂的经典之作。除了科学研究之外，他最喜欢做的事情就是教学，被人称作“一天教学24小时”的教授。 且不说Dijkstra算法对计算科学，网络科学发展的深远影响，单从他在1972年获得图灵奖时的演讲“The Humble Programmer”就不得不肃然起敬，在获得计算机科学中至高无上的奖项时，Edgs Wybe Dijkstra仍然称自己不过是一个谦逊普通的程序员，何等胸襟，举世之中几人可比。 4、运筹学大师——George Dantizig 可谓是由父亲一手培养出的天才。George的父亲是俄国人，曾在法国师从著名的科学家Henri Poincare。他曾经这样回忆自己的父亲：“在我还是个中学生时，他就让我做几千道几何题……解决这些问题的大脑训练是父亲给我的最好礼物。这些几何 题，在发展我分析能力的过程中，起了最最重要的作用。” 在伯克利学习的时候，有一天George上课迟到，只看到黑板上写着两个问题，他只当是课堂作业，随即将问题抄下来并做出解答。六个月后，这门课的老师——著名的统计学家Jerzy Neyman——帮助他把答案整理了一下，发表为论文，George这才发现自己解决了统计学领域中一直悬而未决的两个难题。 George后来在运筹学建树极高，获得了包括“冯诺伊曼理论奖”在内的诸多奖项。他在Linearprogramming and extensions一书中研究了线性编程模型，为计算机语言的发展做出了不可磨灭的贡献。天妒英才，他于2005年5月13日去世。 5、推动时代前进的人——James Cooley (1926-) 美国数学家，哥伦比亚大学的数学博士，以他所创造的快速傅立叶变换(FFT)而著名，不能不说是意义极其重大，FFT的数学意义不光在于使大家明白了傅立 叶(Fourier)变换计算起来是多么容易，而且使得数字信号处理技术取得了突破性的进展，对于现在的网络通信，图形图像处理等等领域的发展与前进奠定 了基础。Fourier变化的意义在于将电能变为了工业的命脉，而FFT的意义更是在于他推动了整个社会信息化的进程。在IBM研究中心中主要从事数字信 号处理的研究一直到1992年退休，同时他还是IEEE的数字信号处理委员会的成员。1980年获得ASSP’s Meritorious Service Award,1984年获得ASSP Society Award以及IEEE Centennial Medal。 6、FORTRAN 之父——John Backus 早年在Hill School学习的时候因为讨厌学习，成绩一踏糊涂而不得不在暑假补课。1943年他在父亲的要求下到维吉尼亚大学学习化学，随后参军、照顾头部受伤的伤 员、在医学学校学习治疗，可是最后又都放弃了。不过还好，战后Backus进入纽约哥伦比亚大学学习数学，并于1949年毕业。在毕业前夕，他跑到了麦迪 逊大街的IBM计算机中心参观。事情凑巧，和导游聊天的时候Backus谈到自己正在找工作，在导游的鼓励下，他和中心一位主管的面谈，成为了一名 IBM?的程序员。 在IBM，Backus的才华得到了施展，发明了人类历史上第一个高级语言——FORTRAN。接着，又提出了规范描述编程语言语法的BNF。这位当年的“差生”终于被整个计算机世界肯定——美国计算机协会于1977年授予John Backus图灵奖。 7、实践探索先锋——Jon Bentley 1974年获得了斯坦福大学的学士学位，1976年获得北卡罗莱纳大学的硕士和博士学位。毕业后在卡耐基梅隆大学教授了6年计算机科学课程，1982年进入贝尔实 验室。2001年退休后加入了现在的Avaya实验室，他还曾作为访问学者在西点军校和普林斯顿大学工作。他的研究领域包括编程技术、算法设计、软件工具 和界面设计等等。 他写作过三本编程书籍，其中最著名的就是涵盖从算法理论到软件工程各种主题的Programming Pearls(《编程珠玑》)，这其实是他发表过的文章的合集。在这些文章里，Jon从工程实现的角度出发，为程序员们提供了一个个艰难问题的解决方案， 犹如一颗颗闪闪发亮的珍珠。Bentley的珍珠超出了可靠工程学的范畴，利用他的洞察力和创造力为那些恼人的问题提供了独特而巧妙的解决方案。 8、Pascal之父——Nicklaus Wirth 如果说有一个人因为一句话而得到了图灵奖，那么这个人应该就是NicklausWirth，这句话就是他提出的著名公式“算法+数据结构=程序”。这个公式对计算机科学的影响程度足以类似物理学中爱因斯坦的“E=MC^2”——一个公式展示出了程序的本质。 Nicklaus Wirth，1934年出生于瑞士，1963年在加州大学伯克利分校取得博士学位。取得博士学位后直接被以高门槛著称的斯坦福大学聘到刚成立的计算机科学 系工作。在斯坦福大学成功的开发出Algol W以及PL360后，爱国心极强的Nicklaus Wirth于1967年回到祖国瑞士，第二年在他的母校苏黎世工学院他创建与实现了Pascal语言——当时世界上最受欢迎的语言之一。 后来他的学生Philipe Kahn毕业后和Anders Hejlsberg(Delphi之父)创办了Borland公司靠Turbo Pascal起家，很快成为了将Borland发展成为全球最大的开发工作厂商，这一切都不得不说要归工于PASCAL语言的魅力。PASCAL已经影响 了整整几代的程序员，Nicklaus Wirth的思想还将会继续指引现在和以后的程序员前进的方向。 9、算法的讲解者——Robert Sedgewick 是普林斯顿大学的计算机科学教授。他还是Adobe Systems的一名主管，也曾作为访问学者在Xerox PARC、IDA和INRIA工作。他在斯坦福大学获得博士学位。他的著作包括Algorithm in C、Algorithm in C++、Algorithm in Java等系列书籍，这些都再版多次。“没有人能够将算法和数据结构解释得比Robert Sedgewick更清楚易懂了！”很多读过他著作的程序员这样说。 目前Robert正在研究算法设计、数据结构、算法分析等方面的基础理 论。他善于通过数学方法评估和预测算法性能，设法发现算法、数据结构的通用机制，例如使用逼近方法寻找更快速更高效的算法。另外，他还将算法和图形学结合 起来，例如使用可视化方法评估算法效率，算法的图形化模拟，用于出版物的高质量算法表现方法等等。 10、计算机领域的爵士——Tony Hoare 1934年出生于英国，1959年博士毕业于俄罗斯莫斯科国立大学，获得语言机器翻译专业学士学位。1960年发布了使他闻名于世的快速排序算法（Quick Sort），这个算法也是当前世界上使用最广泛的算法之一。 Tony Hoare在取得博士学位后，就职于Elliott Brothers，领导了Algol 60第一个商用编译器的设计与开发，由于其出色的成绩，最终成为该公司首席科学家。从1977年开始，Tony Hoare博士任职于牛津大学，投身于计算系统的精确性的研究、设计及开发。因其对Algol 60程序设计语言理论、互动式系统及APL的贡献，1980年被美国计算机协会授予“图灵奖”。 1999年在牛津大学退学后，Tony Hoare博士被微软剑桥研究院聘请担任高级程序员，从事微软剑桥研究院研究生成果的工业化应用的工作，以及协助其它研究人员进行服务于软件产业及用户的长期基础研究项目。2000年因为其在计算机科学与教育上做出的贡献被封为爵士。
|
|
|
