精华区文章阅读

发信人: Lerry (坐壮:望苗:思汉@贵族与猫族斗争到底), 信区: Algorithm
标  题: ['93]Richard Edwin Stearns
发信站: 哈工大紫丁香 (2002年04月26日07:53:13 星期五), 站内信件

[1993]斯坦恩斯--"打工"带来的机遇 (吴鹤龄)
(Ref: http://it.sohu.com/itpeople/Stearns.html
      http://www.acm.org/awards/turing_citations/stearns.html)
=============================================================================
   斯坦恩斯是学数学出身的。1958年他在卡尔顿学院(Carlton College)取得数学
   学士学位后进入普林斯顿大学研究生院，用了3年时间就取得博士学位，其博士
   论文课题是关于博奕论的。

   斯坦恩斯跨进计算机科学的大门并成为一个出色的计算机科学家是十分偶然的
   。1960年暑假，他到通用电气公司打工，被分配到研究实验室新成立的"信息研
   究部"，这使他有缘与已成为那里正式职工的哈特马尼斯一起工作。学过物理而
   后改行数学的哈特马尼斯和专攻数学的斯坦恩斯相结合，双方取长补短，相得益
   彰，使他们的合作富有成果。他们的第一个合作课题是"关于时序机的状态分派
   问题"。这项研究进行得十分顺利，暑假打工结束时，他们已经完成了第一篇合
   作论文，这就是第二年发表的"On the state assignment problem for
   sequential machines"，(刊载于《IRE Trans.Electr.Comput》杂志，EC10
   ，P593～603，Dec.1961。)暑期临时工的经历虽然十分短暂，但通用电气公司研
   究人员的素质和才能，那里浓郁、自由、活泼的学术空气，以及新的、充满机会
   的学科领域给斯坦恩斯留下了十分深刻的印象。因此，一年后他一拿到学位，
   就毫不犹豫地应聘到通用电气公司工作，与哈特马尼斯再度携手，终于再创辉煌
   ，很快完成了奠定"计算复杂性"理论基础的那篇著名论文。

   说来有趣，哈特马尼斯和斯坦恩斯在通用电气公司研究计算复杂性的最初几年，
   实验室里并无计算机可用。他们当时完全是依靠严密的理论分析提出有关"计算
   复杂性"的一系列问题，并给出了科学的解释的。祆1964年，实验室才配了一
   台GE300，斯坦恩斯这才开始用BASIC编程，通过电传打字机接口使用计算机。在
   科学技术的发展史上，开创复杂而重要的学科领域并取得巨大成功的学者，最初
   往往在十分困难的条件下工作，这种情况是屡见不鲜的。

   斯坦恩斯和哈特马尼斯在研究"计算复杂性"理论的过程中，还有一个细节值得一
   提。据斯坦恩斯本人回忆，他们首次明确提出"计算复杂性"这一名词的论文有过
   三个版本：最早是1963年4月实验室内部的一个研究报告，没有公开发表；然后
   是在1964年于普林斯顿举行的IEEE第五届开关电路理论和逻辑设计学术年会上提
   交瑶蚺□A题为("递归序列的计算复杂性")("Computational complexity of
   recursive sequences")，刊于会议论文集82～90 页。第三个版本是发表于美国
   数学会汇刊1965年5月上的("论算法的计算复杂性")("On the computational
   complexity of algorithms")。这三个版本中，会议版本虽然早于杂志版本发表
   ，但实际上却是最后一个版本。因为在此之前，他们对布卢姆M.Blum(见"图灵奖
   得主简介")在 MIT博士论文研究的是同样问题并无所知；会议之前他们偶然获知
   这一情况，便立即去MIT拜访了Blum，双方进行了交流。当时，哈特马尼斯和斯
   坦恩斯已是国际知名大公司的研究人员，而布卢姆则不过是来自南美洲的小国委
   内瑞拉的青年学子。但哈特马尼斯和斯坦恩斯并不因此而对布卢姆有任何轻视，
   并且发现布卢姆在对"复杂性类"等方面的研究比自己还深入一些，因此对布卢
   姆十分推崇，并把他的博士论文列入了他们自己的会议论文的参考文献之中，虽
   然该博士论文当时尚未公开与发表。他们这种在学术上平等待人，互相尊重，善
   于交流的作风是很可贵和值得尽 □满C

   斯坦恩斯后来除了在"计算复杂性"理论上继续有建树并发表了许多论文外，还对
   编译器的设计与理论进行深入的研究并取得了成果。1976年，斯坦恩斯最先提出
   将上下文无关之法的理论应用于编译器的设计，推动了编译器技术的发展。他
   和P.M.Lewis以及D.J.Rosenkraty合著的《CompilerDesignTheory》一书
   (ADDISONwESLEY，1976)被软件界认为是"编译器设计理论"方面最出色的专著之
   一。

   斯坦恩斯在接受图灵奖时发表了题为 "是重新考虑时间这个问题的时候
   了"("It's Time to Recons ider Time")的演说。演说中概括了他和哈特马尼斯
   以及布卢姆共同奠定了计算复杂性理论的基础以来，这一重要领域所取得的主要
   进展。关心这一领域的读者不妨一阅。演说全文刊载于1994年11月的
   《Communications of ACM》，95～99页。

   斯坦恩斯现为奥尔马尼纽约州立大学计算机科学系教授，其电子信箱为
   ：res@cs.albany.edu
=============================================================================
Richard E. Stearns

   Citation
          In recognition of their seminal paper which established the
          foundations for the field of computational complexity theory.
=============================================================================

--

--
当一个女孩儿觉得她不太容易了解那个男人的时候，她会爱他。

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 218.7.32.75]
※ 修改:·Lerry 於 04月26日07:56:00 修改本文·[FROM: 218.7.32.75]

Algorithm 版 (精华区)