《计算机应用基础》课程教学资源（推荐书籍）奇思妙想——15位计算机天才及其重大发现

TURING Springer OUT OF THEIR MINDS w 奇思妙想 15位计算机天才及其重大发现 【美】Dennis Shasha Cathy Lazere若向怡宁o译 www.docin.com 近观15位计算机大师的生平与成就 理解现代计算技术的发展轨迹 谱写自已的智慧人生 人民邮电出版慰

奇思妙想：15位计算机天才及其重大发现 图书在版编目(CIP)数据 奇思妙想：15位计算机天才及其重大发现/（美） 萨莎(Shasha,.D.E.),(美)拉瑟(Lazere,C.A.)著： 向怡宁译.一北京：人民邮电出版社，2011.12 书名原文：Out of Their Minds:The Lives and Discoveries of 15 Great Computer Scientists ISBw978-7-115-26881-5 I.①奇？Ⅱ.①萨？②拉？③向？Ⅲ.①计算机 科学-科学家一生平事迹-世界V.①816.16 中国版本图书馆CIP数据核字(2011)第248002号 内容提要 本书立足于现场访谈的第一手记录，介绍了15位当代最伟大的计算机科学 家，描述了他们的生活历程以及工作成果。在书中，他们解释了自己对科学产生 兴趣的缘由，回顾了其成长环境和其他科学家对他们的影响，阐述了各自进行基 础探索和发现的途径，同时也分享了对未来的看法和主张。 本书既适合所有程序员阅读，也适合所有对计算机行业和软件开发感兴趣的 .com 人阅读八八八/ [Dennis E.Shasha Cathy A.Lazere 译 向怡宁 责任编辑王军花 人民邮电出版社出版发行北京市崇文区夕照寺街14号 邮编100061电子邮件315@ptpress.com.cn 网址http:/mw.ptpress.com.cn 北京 印刷 开本：700×10001/16 印张：13.5 字数：319千字2012年1月第1版

印数：1一5000册2012年1月北京第1次印刷 著作权合同登记号图字：01-2011-6293号 ISBN978-7-115-26881-5 定价：39.00元 读者服务热线：(010)51095186转604印装质量热线：(010)67129223 反盗版热线：(010)67171154 译者序 21世纪到今天早已进入第二个十年，计算机与我们的生活已经完全无法分 割。我还记得上中学时用奔腾386玩打字游戏的情景，那时候不管干什么都需要 -张或几张5.25英寸的D0S软盘才行，笨重的显示器屏幕是一个只有256色的球 面。而现在别说软盘，就连CD都已经淘汰过时，计算机上默认的盘符直接以C 开头，运行速度、显示效果与早期相比更是有天壤之别。流行的终端机型已经变 成了便携的笔记本，方寸大小的手机堪比功能强大的个人电脑，其他日新月异的 掌上触摸设备更是层出不穷。除了成为消费品外，计算机强大的能力近可帮助我 们处理日常工作、记录存档，远能探索太空海洋、破解医学难题。这颗星球上每 一秒钟都会产生无数的信息，而它们都在计算机构成的网络中以光的速度穿梭 世界变得更加透明，距离的概念正在消失。 这一切在以前都是无法想象的，而它们又都在短短20年中就完成了进化。更 妙的是，未来的计算机又会发展成什么样，我们同样无法想象。 那么如果我们追根溯源，又会发现什么？是什么样的人为我们人类作出了如 此卓越的贡献？他们是如何与古老的加法器和乘法器进行对话的？我们都知道C 语言（无论你是否掌握），它的始祖又是谁？互联网的雏形是什么？用电脑模拟人 脑这一想法是如何付诸实践的？有心人也许能从历史的倒影中一窥时代变迁的可 能方向，更何况这些风流人物的铁事就像一杯杯淡雅的香茗，令人读来不忍释卷， 品之齿颊留香。 这些风流人物正是计算机发展史上的拓荒者和奠基人，他们是真正意义上的

世界大师，高举科技的火炬和明灯，为广大计算机从业者披荆斩棘、引领方向， 留下了无数的里程碑。如今走上神坛的苹果教主史蒂夫·乔布斯何尝没有受到过 艾伦·凯发明的Dynabook的影响？倘若阿帕网(ARPANET)未曾诞生，马克·扎克 伯格又怎能在互联网独领风骚？ 《南渡北归》一书的作者岳南曾高叹“大师远去再无大师”。所幸在计算机 领域中尚有无数天骄儿女竞相追随前浪。比尔·盖茨、乔布斯、扎克伯格、谢尔 盖·布林和拉里·佩奇以及更多的幕后英雄都在将前辈的薪火传递。也许十几年 后，类似本书中所谈到的下一代大师将会出现。 翻译这本书对我其实是一次朝圣之旅。在翻译过程中随这些大师一起喜笑怒 骂，体验他们在研究生涯中的酸甜苦辣。这些传奇人物对课题孜孜求索的态度、 坚韧不拔的精神，他们甘于冒险、勇于面对嘲笑的不羁和洒脱都给我留下了深刻 的印象。恰值我32岁生日的今天，胡乱挥就此文，是为序。 向怡宁 2011年9月6日晚于湖北武汉 (编者说明：为便于读者理解有关背景知识，译者不辞辛劳，为译文增加了 许多译注。书中脚注除特别说明外，均为译者注。) www.aqcin.com 在许多科学领域中，开创先河的大师们都生活在遥远的过去。要想揭示他价们 真正的丰功伟绩及其前因后果，我们只能深入历史的角落，在尘埃中寻求真相， 从传说中分辨事实。牛顿是否真的被苹果砸中？阿基米德是否高呼着ureka从浴 本序写于9月初。一个月后惊阳乔布斯去世的消息。不鞋壁。特此向策出补如注释。感这位产品大师和精 领袖在天堂安息 2德有在气待书疹些溪新。书种管谈列店名行学家。爱科学家金岳元他的藏弟千王斋汉是本书中史 ,是高之受量托，人工寄使之父，山甲路育发利人支于01年D月24日与世长，李车 84岁粹次补加注秤

缸跳出跑到大街上？欧几里得是否曾经从古埃及祭司那里窃取了几何的秘密？ 计算机科学则与此不同。那些最先研究当前计算方法(computation)的数学 家们，例如 阿兰·图灵、埃米尔·波斯特和阿隆佐·邱奇，都起步于20世纪30年代或40 年代。我们今天的计算机的概念和他们的早期构想相差无几：一个计算引擎 (calculating engine)和一个用于存储指令和数据的存储器(memory)。他们提 出了该领域的基本理论问题：在有限的时间里能够计算什么？对于这些数学家来 说，“computer”这个词既可能指机器，也可能是指人类本身一因为在他们开始 建立相关理论时，世上还没有能够存储指令的计算机器。 到了20世纪40年代末，当计算机成为工程上的现实之后，该领域的重要问 题开始转变到实用主义方向。仅仅知道一个问题最终能被解决是不够的，更重要 的是知道如何高效且优雅地（如果可能的话）解决这个问题。这需要我们为真实 的机器编写指令，需要我们努力寻求更有效的解决方案，需要构建更好的计算机， 以便解决更复杂的问题，此外，有时还需要让计算机也参与到创造过程中来。本 书分为四个部分，它们分别对应了过去数十年来计算机科学家们为之奋斗的4个 基本问题。 ()语言大师：应该怎样与机器交流？ 1(②)算法大师：如何能让计算机更快地解决问题。 (③)架构大师：能否构建更好的计算机？ .com (4)机器智能的雕塑大师：能否编写程序让计算机自己找到解决问题的方 法？ 本书介绍了15位当代最伟大的计算机科学家，描述了他们的生活历程以及工 作成果。他们都是第一流的创新大师，其中有8位是图灵奖得主，其荣誉相当于 ’由于 的方式表述出来，编成《几何原本)(EE 。他对人工智能的发展 1埃米尔·波斯特(Emil Le 0,1897一1954)是类国数学家、逻指学家，制定了利用符号来表示逻辑的推提系 一黄.美团子家子中双南e久对装一 进性。日前图灵奖由英特尔及谷歌公司赞肠，奖金为25万美元

计算机领域的诺贝尔奖。事实上，如果没有他们作出的贡献，现代计算机很难像 今天这样深入平常百姓家。在本书中，他们解释了自己对科学产生兴趣的缘由， 回顾了成长环境和其他科学家对他们产生的影响，闸述了各自进行基础探索和发 现的途径，同时也分享了对未来的看法和主张。 在说明这些思想及其重要性时，本书尽量避开了科学术语，因此读者不需要 任何专业知识，只要对计算机的发展演变，以及这一领域的科学家们的思维方式 感兴趣即可。 设想回到1690年去拜访艾萨克·牛顿。你也许会问他对于惯性力的看法，而 他也可能会讲述自己早年间在伍尔索普的农场生活”。能与计算机学科的艾萨 克·牛顿们当面交流，是我们莫大的荣幸，这也鼓舞我们写出了本书。 关于写作风格与表现形式 本书立足于现场访谈的第一手记录，因为我们相信，这些科学家们的言传身 教更能帮助读者透彻地了解他们的个性和方法，这比经过我们的转述和修饰要好 得多。我们负贵勾画出相应的历史背景，并解释相关的科学和数学原理，但关于 这些科学家是如何提出自己的发现，当时他们都在想些什么，最好还是听他们自 己来说。 考虑到行家里手通常会对技术细节感兴趣，我们把相关部分用补充内容的形 式展现出来。也许读者把书读完一遍之后还会要回头再看看这些部分。我们也为 刚刚接触这个领域的读者们提供了一份基本术语的词汇表。此外我们还在每部分 开篇几页按时间顺序列出了本领域及诸位科学家生平的大事，帮助读者在时间上 进行定位。本书的最后两章“后记”和“结语”，则探索了两个问题：伟大的计算 机科学家在他们的人生和思想上是否存在者家族相似性？25年后，类似本书这 样的著作又将会探讨哪些新的发现？ 第一部分语言大师：如何与机器对话 1 1约翰·巴科斯不断进取的发明家 4 品

2约翰·麦卡锡不走寻常路的常识逻辑学家 16 3艾伦·C.凯清晰的浪漫主义梦想28 第二部分算法大师：如何快速地解决问题 39 4艾兹赫尔·W,戴克斯彻可怕的说明文和最短路径 42 5迈克尔·0.拉宾机会的可能性51 6高德纳（唐纳德·E.克努斯）逐新趣异一线牵 66 7罗伯特·E.陶尔扬寻找优秀的结构 76 8莱斯利·兰伯特时间、空间和计算 89 9史提芬·古克和利奥尼德·列文良解难觅101 第三部分架构大师：如何构建更好的机器115 10弗雷德里克·P.布鲁克斯成功带来的愉悦 117 11伯顿·J.史密斯与光速赛跑 127 12W.丹尼尔·希利斯与生物学的连结 136 第四部分机器智能的雕塑大师：如何让机器更聪明 147 13爱德华·A费根鲍姆知识的力量149 14道格拉斯·B.莱纳特一场二十年的豪赌159 后记：下一个25年173 .巴ocin.C0m 参考文献189 第一部分 语言大师：如何与机器对话 假设现在第二次世界大战刚结束不久，而你是一位总工程师，负贵一项计算 机制造计划。你收集了一堆电线和开关，任务是构建出一台机器，以便预测飞机

在空中的飞行模式。鉴于当时的技术水平，你只能使用一些不可靠的部件，而且 构建的机器要便于装配。这台机器消耗的电力足以供应一个小型工厂。此外你还 为它配各了一个足以容纳几千个字符的存储器、加法器、乘法器，以及一套用于 计算的指令集。 指令是最不需要操心的问题，它们只需表达清楚，能够完成任务即可。 为了提高效率，你需要让各种指令尽可能与工程设计的细节相适应。这台机 器的存储器具有不同的运行速度和能耗，因此你需要设定一个指令组用于在慢速 存储器和快速存储器之间传递数据，设定另一个指令组用于在快速存储器中对数 据进行四则算术运算或其他操作。这种分组方式无疑不利于编写预测飞行模式的 程序，如果将存储器视为一种不分类的资源来进行指令分组，应该会容易不少， 但你并不为此担心。在当时，一毛钱就能雇来一打学数学的编程人员，而相比之 下，机器本身却非常精致、昂贵且罕见。 五年之后，情况发生了根本性的变化。你吃惊地发现，随者对程序的需求高 张以及硬件成本的降低，程序设计的费用要远高于硬件的购买和维护成本。（这种 态势一直延续了下来。到了20世纪90年代中期，在大多数企业的软件开发环节 中，程序设计的开支已经达到了硬件开支的50倍左右.)因此你为自己制定了两 个新的目标：缩短程序第一个版本发布所需要的时间，以及让程序更易于改进， 以适应客户需求的变化。 V你决定修致编程人员与机器沟通所使用的语言。新的语言应当反映出所要解 决问题的结构，而不再是反映存储器的快慢层级和算术运算。每一种行业都会根 据自身的目的而发明某种语言，例如电影导演会用“开拍”(action)这个简单的 术语来表示“摄像师开始拍摄，演员开始表演，其他人员各就各位”。由于在20 世纪50年代中期，计算机主要应用于纯科学和数据处理，因此你更关注的是创造 一种数学语言，包括运算公式、求和以及向量数组。为了开拓思路，你拜访了许 多研究人员，也了解了许多项目，它们允许程序员输入类似(W+门/Z这样的数 学表达式，然后计算机就能自行编译并且进行相应的运算。 到了1958年，有一门科学编程语言脱颖而出，它就是约翰·巴科斯和他在 IBWM公司的同事合作设计的Fortran(取自formula translation的缩写，即公式 n Warner Back 19242007)被称为Forran爵言之父，197年获得图灵奖。本书第1章详

翻译)。这门语言至今仍然是自然科学界使用最为广泛的编程语言。 与此同时，一个研究团队在1956年开辟了计算机的一个崭新领域：人工智能 (artificial intelligence)。这门学科的一个目标是创造出具备人类推理能力 的计算机。由于人类大部分的推理过程都需要进行抽象（例如积木的相对位置、 句子的语法、不同洗衣皂的优缺点)，偏重数学运算的Fortran语言对此并不适用。 卡内基-梅隆大学的艾伦·纽厄尔“和赫伯特·西蒙“建议用符号表(1isto symbols)来表现抽象概念，并且把推理过程视为一种“符号操作”(symbol manipulation). 假设有一块红色积木、一块蓝色积木和一块黄色积木。一个5岁大的小孩也 可以告诉我们，如果红色积木在蓝色积木之上，而黄色积木又在红色积木之上， 那么黄色积木必然也在蓝色积木之上。将前两个事实用符号表来表示，我们可能 会写：(above redblock blueblock)以及(above yellowblock blueblock)。之后 引用符号操作规则，我们便能得出：如果(above x y)和(above z x),则(above z y)。 年轻的约翰·麦卡锡对这一想法印象深刻，但他认为纽厄尔和西蒙的设计过 于复杂。他简化了设计，加入了两个强大的功能，也就是我们所知的递归 (recursion)和求值(eval),并且创造了一门称为Lisp的语言（取自“Iist processing”的缩写，即表处理).isp不仅是人工智能方面的首选语言，且自 1958年诞生起，和Fortran一起不断为计算机语言的设计提供灵感。 这一年的夏天，一个国际计算机科学家小组在苏黎世成立，开始设计纳入 Lisp元素的Fortran语言的继任者.他们的精诚合作产生了里程碑式的A1gol60, 它直接催生了Pascal、C和Ada这些语言，同时也是从PostSeript到Excel等各 种语言的直系祖先。 然而到了20世纪70年代早期，一些研究人员逐渐发现由Fortran、A1gol 和Li即所衍生出来的上百种语言都存在着一个共同的弱点：写出来的程序让人很 难读懂。在实际工作中，人们发现如果想修改程序的行为，往往都需要整个重写。 “赫伯特·西蒙(Herbert lexand Simon,中文名为司马贺，191620O1)是现代一些重要学术领域，如人工智能 的人之一并且获得了很多荣，如1975年 :的堂的20是人工背能方面的务机。191年铁得图现关。参见本书第2苹

拥有生物学背景的艾伦·凯认为应该把程序构建成像活的生物那样：由独立 自主的“细 胞”构成，彼此通过讯息传递进行合作。他认为通过自主的单元来构建程序，将 会使这些单元能够融入新的上下文情境。对于这种“细胞”，他使用了“对象 (object))一词来称呼，并且将这种方式称为“面向对象”(objectrientation). 对象的行为取决于它得到的州忌。 第一部分语言大师：如何与机器对话 比如说，在与图片有关的程序中，可以用“旋转30度”、“开始打印”这样的 讯息或命令来描述常用行为。而如果是操控登月机器人的程序，则可能是“收集 岩石样本”或者“找到高度超过1米的石块”。20世纪70年代中期，艾伦·凯带 领他在施乐公司的团队设计出了首个面向对象 的语言Smalltalk。大批年轻人在数年间加入了它的用户群。由此开始，Smalltalk 深刻地影响了C+等日趋成熟的编程语言，其自身也衍生了一批专业的追随者。 过去四十年间，世界上诞生了成百上千种编程语言，约有60种在今天仍然被 广泛使用，其中包括文字处理、电子表格、图形设计和动画设计等领域的专用语 言。就像工具帮助木匠解决问题一样，一门好的编程语言也能帮助我们解决计算 机的问题。而且编程人员也正如木匠习惯于自己的工具那样习惯于自己钟爱的语 言。 1语言学家本杰明·沃尔夫"曾经说过：“语言塑造了我们思考的方式，决定 了我们思考的内容。”他这番话是针对人类语言所言，而计算机语言则进一步印 证了这一主张，尤其是那些灵感来源于巴科斯、麦卡锡和凯的成果的计算机语言。 制的若人类的思哈模武