算法+数据结构=程序
影响计算机算法世界的十位大师
本文转自：&
DonE. Knuth（美）高德纳 《计算机程序设计艺术》的作者； Edsger Wybe（荷兰） Dijkstra算法（最短路径算法）发明者； George Dantzing（俄国） 运筹学大师；
（美） FFT（快速傅利叶变换）算法发明者，该算法主要用语数字信号处理技术； John Backus（美） FORTRAN之父，又提出规范描编程语言语法的Backus-Naur Form(BNF)； Jon Bentley（美）?《Programming Pearls》（中文名《编程珠玑》）作者，精于软件工程； Nicklaus Wirth（瑞士） PASCAL之父，提出了&算法+数据结构=程序&，他是创办Borland公司的Philie kahn的老师； Robort Sedgewick（美）　算法讲解者；
（英）　快速排序算法（Quick Sort）发明者，１９９９年加入微软创办了剑桥研究院；
（美）　Google副总裁，首席算法官。
伟大的智者&&Don E.Knuth，中文名：高德纳(1938-)算法和程序设计技术的先驱者。Oh,God!一些国外网站这样评价他。一般说来，不知道此人的程序员是不可 原谅的。其经典著作《计算机程序设计艺术》更是被誉为算法中&真正&的圣经，像KMP和LR(K)这样令人不可思议的算法，在此书比比皆是。难怪连&都说：&如果能做对书里所有的习题，就直接来微软上班吧！&
对于Don E.Knuth本人，一生中获得的奖项和荣誉不计其数，包括图灵奖，美国国家科学金奖，美国数学学会斯蒂尔将（AMS Steel Prize），以及发明先进技术荣获的极受尊重的京都奖（KyotoPrize）等等，写过19部书和160余篇论文，每一篇著作都能用影响深远来形容。 Don E.Knuth也被公认是美国最聪明的人之一。当年他上大学的时候，常写些各种各样的编译器来挣外快，只要是他参加的编程比赛，总是第一名，同时也是世上 少有的编程达到40年以上的程序员之一。他除了是技术与科学上的泰斗外，更是无可非议的写作高手，技术文章堪称一绝，文风细腻，讲解透彻，思路清晰而且没 有学究气，估计这也是《计算机程序设计艺术》被称为圣经的原因之一。
首席算法官Udi Manber&&世界上还有如此奇怪的职位？但是对于Amazon乃至Google来说，这一点也不奇 怪。Udi Manber，这位前Amazon的&首席算法官&，现在是Google负责工程事务的副总裁。他研究WWW的应用程序、搜索以及隐藏在这背后的算法设 计。在此期间，他与其他人共同开发了Agrep、Glimpse和Harvest等Unix上的搜索软件。1998年，Udi成为了Yahoo!的首席科 学家。2002年，Amazon创造性地给了Udi&首席算法官&的职位，和Udi为Amazon的&Search Inside the Book&搜索项目所做的工作相得益彰。
Udi还因为他所著的&&A Creative Approach而被大家称道。
谦逊的长者&&，1930年出生于荷兰阿姆斯特丹，2002年逝世于荷兰纽南。他在祖国荷兰获得数据和物理学学士，理论物理博士学位，2000年退休前 一直是美国Texas大学的计算机科学和数学教授。以发现了图论中的最短路径算法（Dijkstra算法）而闻名于世，1972年因为ALGOL第二代编 程语言而获得图灵奖。&Go To Statement Considered Harmful&(EWD215)也是被广为传颂的经典之作。除了科学研究之外，他最喜欢做的事情就是教学，被人称作&一天教学24小时&的教授。
且 不说Dijkstra算法对计算科学，网络科学发展的深远影响，单从他在1972年获得图灵奖时的演讲&The Humble Programmer&就不得不肃然起敬，在获得计算机科学中至高无上的奖项时，Edgs Wybe Dijkstra仍然称自己不过是一个谦逊普通的程序员，何等胸襟，举世之中几人可比。
运筹学大师&&George Dantizig可谓是由父亲一手培养出的天才。George的父亲是俄国人，曾在法国师从著名的科学家Henri Poincar e。他曾经这样回忆自己的父亲：&在我还是个中学生时，他就让我做几千道几何题&&解决这些问题的大脑训练是父亲给我的最好礼物。这些几何题，在发展我分 析能力的过程中，起了最最重要的作用。&
在伯克利学习的时候，有一天George上课迟到，只看到黑板上写着两个问题，他只当是课堂作业， 随即将问题抄下来并做出解答。六个月后，这门课的老师 &&著名的统计学家Jerzy Neyman&&帮助他把答案整理了一下，发表为论文，George这才发现自己解决了统计学领域中一直悬而未决的两个难题。
George后来在运筹学建树极高，获得了包括&冯诺伊曼理论奖&在内的诸多奖项。他在Linear programming and extensions一书中研究了线性编程模型，为计算机语言的发展做出了不可磨灭的贡献。天妒英才，他于日去世。
推动时代前进的人&&James Cooley(1926-)美国数学家，哥伦比亚大学的数学博士，以他所创造的快速傅立叶变换(FFT)而著名，不能不说是意义极其重大，FFT的数学意 义不光在于使大家明白了傅立叶(Fourier)变换计算起来是多么容易，而且使得数字信号处理技术取得了突破性的进展，对于现在的网络通信，图形图像处 理等等领域的发展与前进奠定了基础。Fourier变化的意义在于将电能变为了工业的命脉，而FFT的意义更是在于他推动了整个社会信息化的进程。在 IBM研究中心中主要从事数字信号处理的研究一直到1992年退休，同时他还是IEEE的数字信号处理委员会的成员。1980年获得ASSP's Meritorious Service Award,1984年获得ASSP Society Award以及IEEE Centennial Medal。
FORTRAN之父&&John?Backus早年在Hill?School学习的时候因为讨厌学习，成绩一踏糊涂而不得不在暑假补课。1943年他在父亲的要求下到维吉尼亚大学学习化学，随后参军、照顾头部受伤的伤员、在医学学校学习治疗，可是最后又都放弃了。不过还好，战后Backus进入纽约哥伦比亚大学学习数学，并于1949年毕业。在毕业前夕，他跑到了麦迪逊大街的IBM计算机中心参观。事情凑巧，和导游聊天的时候Backus谈到自己正在找工作，在导游的鼓励下，他和中心一位主管的面谈，成为了一名IBM?的程序员。??
在IBM，Backus的才华得到了施展，发明了人类历史上第一个高级语言&&FORTRAN。接着，又提出了规范描述编程语言语法的Backus-?Naur?xxxx(BNF)。这位当年的&差生&终于被整个计算机世界肯定&&美国计算机协会于1977年授予John?Backus图灵奖。??
实践探索先锋&&Jon Bentley&1974年获得了斯坦福大学的学士学位，1976年获得北卡罗莱纳大学的硕士和博士学位。毕业后在卡耐基梅隆大学教授了6年计算机科学课程，1982年进 入贝尔实验室。2001年退休后加入了现在的Avaya实验室，他还曾作为访问学者在西点军校和普林斯顿大学工作。他的研究领域包括编程技术、算法设计、 软件工具和界面设计等等。
他写作过三本编程书籍，其中最著名的就是涵盖从算法理论到软件工程各种主题的Programming Pearls(《编程珠玑》)，这其实是他发表过的文章的合集。在这些文章里，Jon从工程实现的角度出发，为程序员们提供了一个个艰难问题的解决方案， 犹如一颗颗闪闪发亮的珍珠。Bentley的珍珠超出了可靠工程学的范畴，利用他的洞察力和创造力为那些恼人的问题提供了独特而巧妙的解决方案。
Pascal之父&&Nicklaus Wirth，如果说有一个人因为一句话而得到了图灵奖，那么这个人应该就是Nicklaus Wirth，这句话就是他提出的著名公式&算法+数据结构=程序&。这个公式对计算机科学的影响程度足以类似物理学中爱因斯坦的&E=MC^2&&&一个 公式展示出了程序的本质。
Nicklaus Wirth，1934年出生于瑞士，1963年在加州大学伯克利分校取得博士学位。取得博士学位后直接被以高门槛著称的斯坦福大学聘到刚成立的计算机科学 系工作。在斯坦福大学成功的开发出Algol W以及PL360后，爱国心极强的Nicklaus Wirth于1967年回到祖国瑞士，第二年在他的母校苏黎世工学院他创建与实现了Pascal语言&&当时世界上最受欢迎的语言之一。后来他的学生 Philipe Kahn毕业后和(Delphi之父)创办了Borland公司靠Turbo Pascal起家，很快成为了将Borland发展成为全球最大的开发工作厂商，这一切都不得不说要归工于PASCAL语言的魅力。PASCAL已经影响 了整整几代的程序员，Nicklaus Wirth的思想还将会继续指引现在和以后的程序员前进的方向。
算法的讲解者&&Robert Sedgewick是普林斯顿大学的计算机科学教授。他还是的一名主管，也曾作为访问学者在Xerox PARC、IDA和INRIA工作。他在斯坦福大学获得博士学位。他的著作包括Algorithm in C、Algorithm in C++、Algorithm in Java等系列书籍，这些都再版多次。&没有人能够将算法和数据结构解释得比Robert Sedgewick更清楚易懂了！&很多读过他著作的程序员这样说。
目前Robert正在研究算法设计、数据结构、算法分析等方面的基础理 论。他善于通过数学方法评估和预测算法性能，设法发现算法、数据结构的通用机制，例如使用逼近方法寻找更快速更高效的算法。另外，他还将算法和图形学结合 起来，例如使用可视化方法评估算法效率，算法的图形化模拟，用于出版物的高质量算法表现方法等等。
计算机领域的爵士&&Tony Hoare，1934年出生于英国，1959年博士毕业于俄罗斯莫斯科国立大学，获得语言机器翻译专业学士学位。1960年发布了使他闻名于世的快速排序算法（Quick Sort），这个算法也是当前世界上使用最广泛的算法之一。
Tony Hoare在取得博士学位后，就职于Elliott Brothers，领导了Algol 60第一个商用编译器的设计与开发，由于其出色的成绩，最终成为该公司首席科学家。从1977年开始，Tony Hoare博士任职于牛津大学，投身于计算系统的精确性的研究、设计及开发。因其对Algol 60程序设计语言理论、互动式系统及APL的贡献，1980年被美国计算机协会授予&图灵奖&。
1999年在牛津大学退学后，Tony Hoare博士被微软剑桥研究院聘请担任高级程序员，从事微软剑桥研究院研究生成果的工业化应用的工作，以及协助其它研究人员进行服务于软件产业及用户的 长期基础研究项目。2000年因为其在计算机科学与教育上做出的贡献被封为爵士。
此外还有两位大师不在此文中，但是也必须提一下他们对计算机算法的贡献。
1986年图灵奖由康乃尔大学机器人实验室主任约翰&霍泼克洛夫特() 和普林斯顿大学计算机科学系教授罗伯特&塔扬()共享，而塔扬曾是霍 泼克洛夫特的学生。这师生两人由于在数据结构和算法的分析和设计方面的许多创造性 贡献而共同获此殊荣，在业界传为美谈。
霍泼克洛夫特 日生于西雅图。1961 年在西雅图大学获得电气工程学士学位以后，进入斯坦福大学研究生院深造，1962年获 得硕士学位，1964年获得博士学位，也就是说只用了3年时间他就拿下了2个学位，霍 泼克洛夫特的勤奋和聪颖由此可见。学成以后，霍泼克洛夫特曾先后在普林斯顿大学、 康乃尔大学、斯坦福大学等著名学府工作，也曾任职于NSF(美国科学基金会)和NRC(美 国国家研究院)，从事对科学研究的规划和行政管理工作，但时间不长。
霍泼克洛夫特成为著名的计算机科学家起源于一个 十分偶然的机会。霍泼克洛夫特学习的专业是电气工程，原先对计算机科学没有多少知 识，只学过一门&开关电路和逻辑设计&算多少有些关系。因此他原打算毕业后去西海 岸的一所大学执教电气工程方面的课程。但就在毕业以前，有一次他偶然经过他的导师、 研究神经网络的先驱和著名学者威德罗()办公室的门口，当时，普林斯顿 大学的麦克卢斯基教授(Edward McCluskey，曾任IEEE计算机协会主席)正为筹建数字系 统实验室打电话给威德罗，请他推荐博士生去那里工作。威德罗一眼瞥见从门口走过的 霍泼克洛夫特，觉得勤奋好学，悟性又高的这位得意门生正是一个值得推荐的人才，当 即把霍泼克洛夫特叫进办公室，并把电话听筒递给了他。霍泼克洛夫特在电话里听了麦 克卢斯基对普林斯顿大学拟建数字系统实验室的情况介绍，以后又前去面谈了一次，实 地了解一番以后，对这一新的学科产生了兴趣，欣然接受了普林斯顿的聘任，从而改变 了他一生的道路。
年青的霍泼克洛夫特来到普林斯顿之 后接受的第一 项任务是开设一门新课：自动机理论。这对他来说是富有挑战性的，因为他之前并未接 触过这个课题。面对挑战，他以极大的热情收集、钻研和消化了大量有关材料，加以分 析、综合和比较。这样，在霍泼克洛夫特的努力下，有关自动机理论的一些分散、复杂 的材料第一次被全面地条理化、系统化，因此他的讲课理所当然地受到了学生极大的欢 迎。后来，霍泼克洛夫特和厄尔曼(J.D.Ullman)又合作编写了《形式语言及其与自动机的 关系》(《Formal Language and Their Relation to Automata》，Addison-Wesley,1969)一书，这 本书被认为是自动机理论中有代表性的一部著作。
然而，霍泼克洛夫特更感兴趣的课题是算法。当时， 算法复杂性理论虽已由哈特马尼斯(J.Hartmanis)、斯坦恩斯(R.Stearns,这两人是1993年图灵 奖获得者)和布鲁姆(M.Blam，1995年图灵奖获得者)等人奠定了基础，但对具体算法的效 率和优劣的判断尚未建立起客观和明确的准则，因此，往往出现下述情况：有人公布了 一个算法，给出对若干样本问题的执行时间；过了一段时间，另外一个人发布&改进算 法&，给出对相同样本问题的执行时间(当然比前者少)。而实际上，这很可能是由于机器 性能提高或(和)语言改进所致，所谓&改进算法&其实不见得比原算法高明。霍泼克洛夫 特对这种情况很不满意，决心加以解决。经过反复研究，他终于提出了一种称为&最坏 情况渐近分析法&(Worst-case asymptotic analysis of algorithm)，这种方法先确定问题和大小 尺度，然后把计算时间当作问题大小尺度的一个函数去算出计算时间的增长率，以此衡 量算法的效率和优劣。这个方法由于与机器性能及所用语言无关，成为测量算法好坏的 数学准则，被学界所广泛认同和接受。
但是导致他和塔 扬共同获得图灵奖的最主要贡献则 是他们解决了图论算法中的一些难题。1970年，霍泼克洛夫特在康乃尔大学获得一年休 假(他是1967年被另一图灵奖获得者哈特马尼斯招至麾下的)。他决定回母校斯坦福大学 到克努特(D.Knuth)教授名下做研究，因为克努特虽然只比他年长一岁，但因在1967年和 1968年连出两卷《计算机程序设计的艺术》(《》)而已名 满天下，成为算法领域的权威。克努特知道霍泼克洛夫特对算法感兴趣并有独到见解， 就把他和自己的得意门生、研究方向也是算法的塔扬安排在一个办公室，为他们的合作 创造了条件。他们选择了图论中与实际应用有很大关系的图的连通性和平面性测试难题 进行攻关。拿平面图来说，它对印刷电路板设计这样一类问题有十分重要的意义。学过 图论的人都知道，平面图的判断问题，在数学上已由波兰数学家库拉托夫斯基(Kuratowski) 于1930年解决。库拉托夫斯基的判据原理看似简单，但实现起来很难。对于有100个顶 点的图，用普通的算法，计算机需要1万亿步才能确定其是否为平面图!因此，寻找高效 的平面图测试算法成为摆在当时计算机科学家面前的一大难题。霍泼克洛夫特和塔扬都 是富有创造性的人，又都善于合作共事，因此当两朵智慧的火花碰在一起时，就很快迸 发出耀眼的光芒!在解决这个难题的过程中，霍泼克洛夫特首先提出了一种新的思路、新 的算法，经过塔扬的反复推敲和完善，一种适于解这类问题的新的算法终于诞生了，这 就是&深度优先搜索算法&(depth-first search algorithm)。利用这种算法对图进行搜索时， 结点扩展的次序是向某一个分枝纵深推进，到底后再回溯，这样就能保证所有的边在搜 索过程中都经过一次，并且只经过一次，从而大大提高了效率。新算法的运行时间是线 性的，也就是说时间与图的大小成正比关系，大小翻一倍，解问题所需的时间也只翻一 倍。相比之下，若用库拉托夫斯基判断的老算法，那么当图的大小翻一倍时，所需时间 要增加60倍以上。利用他们创造的新算法，塔扬用Algolw为一个包含900个结点和2694 条边的图编制了一个测试其平面性的程序，程序只有500行，在IBM 360/67上运行，只 用了12秒就得到了结果。霍泼克洛夫特和塔扬把他们的研究成果写成论文在《Journal of the ACM》上发表，引起学术界很大的轰动。而他们创造的深度优先算法则被推广到信息 检索、国际象棋比赛程序、专家系统中的冲突消解策略等许多方面。在霍泼克洛夫特和 塔扬获得图灵奖的授奖仪式上，当年的计算机象棋程序比赛的优胜者就说，他的程序中 使用了霍泼克洛夫特和塔扬所发明的深度优先搜索算法，这是他的程序所以能出奇制胜 的关键。
在取得辉煌成功之后，霍泼克洛夫特和塔扬并 不满足，他们致力于开发效率更高的算法。不久，他们又提出了一种新的数据结构叫&双堆 栈叠&（pile of twin stacks），这种新的数据结构被深度优先搜索算法的优点更加发扬光 大。塔扬的一个学生用这种新的数据结构和算法编写了一个Algolw程序，只有250行， 在IBM 370/168上测试有8000个结点的图的平面性只用了8秒钟。
霍泼克洛夫特除了和塔扬合作取得上述成果外，在数 据结构和算法方面还有其他一系列创造。比如常用于索引组织的著名数据结构B树(B...
分享这篇日志的人也喜欢
热门日志推荐
人人最热标签
分享这篇日志的人常去
北京千橡网景科技发展有限公司：
文网文[号··京公网安备号·甲测资字
文化部监督电子邮箱：wlwh@··
文明办网文明上网举报电话： 举报邮箱：&&&&&&&&&&&&
请输入手机号，完成注册
请输入验证码
密码必须由6-20个字符组成
下载人人客户端
品评校花校草，体验校园广场【图文】10 公共基础1-数据结构与算法_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
&购买后可评价
您可以上传图片描述问题
联系电话：
请填写真实有效的信息，以便工作人员联系您，我们为您严格保密。
10 公共基础1-数据结构与算法
|0|0|暂无简介
互联网从业者|
总评分4.5|
浏览量722700
大小：46页
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢下载频道&lm_cheng的资源
上传者：zhangzimu88&&&&| 上传时间：&&&&| 下载6757次
程序员面试宝典(pdf全)
上传者：v_JULY_v&&&&| 上传时间：&&&&| 下载5541次
火爆出炉：微软等数据结构+算法面试100题首次完整亮相
---100题V0.1版最终完成
微软等100题系列V0.1版终于结束了。
从日当天最初发表前40题以来，直至此刻，整理这100题，已有近2个月。
上传者：v_JULY_v&&&&| 上传时间：&&&&| 下载7691次
本文件是十三个经典算法研究+红黑树系列的，带目录+标签的PDF文档。在此之前，网上绝无仅有。希望，对你有帮助。博客地址为：http://blog.csdn.net/v_JULY_v。
上传者：v_JULY_v&&&&| 上传时间：&&&&| 下载9734次
作者：July、阿财。
时间：二零一一年十月十三日。
------------------------------
无私分享造就开源的辉煌。
今是二零一一年十月十三日，明日14日即是本人刚好开博一周年。在一周年之际，特此分享出微软面试
全部100题答案的完整版，以作为对本博客所有读者的回馈。
上传者：loulanw&&&&| 上传时间：&&&&| 下载197次
虚拟(模拟)打印机没有打印机也可以实现打印结果
上传者：tchdj&&&&| 上传时间：&&&&| 下载333次
很好的书，美Mark Allen Weiss 著，冯舜玺翻译，最大的特点是每种算法有数学基础复习，翻译语言优美，初学者也能看懂，绝对清晰，感谢电子书制作者。
积&&&&&&&&分：0
上传资源： 3
下载资源：64
总&&排&&名：第&&名(IT互联网猎头)
(江湖人称姐姐)
(副刊游侠)
第三方登录：