Algorithm 版 (精华区)

发信人: ssos (存在与虚无·戒酒戒网), 信区: Algorithm
标  题: 斯坦恩斯--"打工"带来的机遇 　　吴鹤龄
发信站: 哈工大紫丁香 (2001年08月23日17:33:50 星期四), 站内信件

----
斯坦恩斯是学数学出身的。1958年他在卡尔顿学院(Carlton College)取 得数学学士学
位后进入普林斯顿大学研究生院，用了3年时间就 取得博士学位，其博士论文课题是关
于博奕论的。
斯坦恩斯跨进计算机科学的大门并成 为一个出色的计算机科学家是十分偶然的。1960年
暑假，他到通用 电气公司打工，被分配到研究实验室新成立的"信息研究部"，这 使他
有缘与已成为那里正式职工的哈特马尼斯一起工作。学过 物理而后改行数学的哈特马尼
斯和专攻数学的斯坦恩斯相结 合，双方取长补短，相得益彰，使他们的合作富有成果。
他们的第 一个合作课题是"关于时序机的状态分派问题"。这项研究进行得 十分顺利，
暑假打工结束时，他们已经完成了第一篇合作论文，这 就是第二年发表的"On the sta
te assignment problem for sequential machines"，(刊载 于《IRE Trans.Electr.C
omput》杂志，EC10，P593～603，Dec.1961。)暑期临时工 的经历虽然十分短暂，但通
用电气公司研究人员的素质和才能， 那里浓郁、自由、活泼的学术空气，以及新的、充
满机会的学科领 域给斯坦恩斯留下了十分深刻的印象。因此，一年后他一拿到学 位，
就毫不犹豫地应聘到通用电气公司工作，与哈特马尼斯再度 携手，终于再创辉煌，很快
完成了奠定"计算复杂性"理论基础的 那篇著名论文。
说来有趣，哈特马尼斯和斯坦恩斯在 通用电气公司研究计算复杂性的最初几年，实验室
里并无计算 机可用。他们当时完全是依靠严密的理论分析提出有关"计算复 杂性"的一
系列问题，并给出了科学的解释的。直到1964年，实验室 才配了一台GE300，斯坦恩斯
这才开始用BASIC编程，通过电传打字 机接口使用计算机。在科学技术的发展史上，开
创复杂而重要的 学科领域并取得巨大成功的学者，最初往往在十分困难的条件 下工作
，这种情况是屡见不鲜的。
斯坦恩斯和哈特马尼斯在研究"计算 复杂性"理论的过程中，还有一个细节值得一提。据
斯坦恩斯本人 回忆，他们首次明确提出"计算复杂性"这一名词的论文有过三个 版本：
最早是1963年4月实验室内部的一个研究报告，没有公开发 表；然后是在1964年于普林
斯顿举行的IEEE第五届开关电路理论 和逻辑设计学术年会上提交的论文，题为("递归序
列的计算复杂 性")("Computational complexity of recursive sequences")，刊于会
议论文集82～90 页。第三个版本是发表于美国数学会汇刊1965年5月上的("论算法 的计
算复杂性")("On the computational complexity of algorithms")。这三个版本 中，
会议版本虽然早于杂志版本发表，但实际上却是最后一个版 本。因为在此之前，他们对
布卢姆M.Blum(见"图灵奖得主简介")在 MIT博士论文研究的是同样问题并无所知；会议
之前他们偶然获 知这一情况，便立即去MIT拜访了Blum，双方进行了交流。当时，哈 特
马尼斯和斯坦恩斯已是国际知名大公司的研究人员，而布卢 姆则不过是来自南美洲的小
国委内瑞拉的青年学子。但哈特马 尼斯和斯坦恩斯并不因此而对布卢姆有任何轻视，并
且发现布 卢姆在对"复杂性类"等方面的研究比自己还深入一些，因此对布 卢姆十分推
崇，并把他的博士论文列入了他们自己的会议论文 的参考文献之中，虽然该博士论文当
时尚未公开与发表。他们这 种在学术上平等待人，互相尊重，善于交流的作风是很可贵
和值 得学习的。
斯坦恩斯后来除了在"计算复杂性"理 论上继续有建树并发表了许多论文外，还对编译器
的设计与理 论进行深入的研究并取得了成果。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.alba
ny.edu

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]