Algorithm 版 (精华区)

发信人: ssos (存在与虚无·戒酒戒网), 信区: Algorithm
标  题: 哈特马尼斯--从难民营中成长 　　吴鹤龄
发信站: 哈工大紫丁香 (2001年08月23日17:29:26 星期四), 站内信件

----
1993年度的图灵奖授予合作奠定了计算复杂性理论基础的两 位学者朱利斯·哈特马尼斯
(Juris　Hartmanis)和理查德·斯坦恩斯 (RichardE.Stearns)。
哈特马尼斯是拉脱维亚人，生于1928 年。二战期间，为躲避战火，哈特马尼斯一家人背
井离乡，沦为"流 民"(DisplacedPerson)。哈特马尼斯的中学学业就是在哈瑙(Hanau)的
难民 营中完成的。之后，他进入德国马尔布克大学学习物理(Marburg是 一座大学城，
离法兰克福不远)。两年半之后的1950年，哈特马尼斯 获得资助，来到美国，进入堪萨
斯城大学攻读硕士学位。但由于该 校没有物理学的研究生课程，哈特马尼斯只得与数学
结缘。哈特 马尼斯只用了一年时间就取得硕士学位，并被加里福尼亚理工 学院接收为
博士生，从事格论(lattice)的研究。哈特马尼斯用了4年 时间完成博士论文，于1955年
取得博士学位，进入康乃尔大学数 学系任教。但他在那里只工作了一年多，就转入通用
电气公司设 在纽约州斯克内克塔迪(Schenectady)的研究实验室。因为那里新建 立了一
个"信息研究部"(Information　Studies　Section)，开展有关计算机和信 息学的研究
，这一新的领域激发起了哈特马尼斯极大的兴趣和 热情。
当时，香农(Claude　Elwood　Shanon)的信息论 问世不久，香农公式给出了确定的信号
和噪声平均功率之下，给 定带宽的信道在单位时间内的最大信息传输量。念过物理学的
 哈特马尼斯受此启发，敏锐地想到，抽象的计算过程也应该有精 确的定量法则，以确
定为了对每一个问题求得答案，需要多少计 算工作量。围绕这一设想哈特马尼斯和斯坦
恩斯合作开展了研 究，其结果就是那篇著名的论文"On　the　computational　comple
xity　of algorithms"(《论算法的计算复杂性》TransAmer　Math.Soc,177(1965)，28
5～306 页)。这篇论文开辟了计算机科学的一个新的研究领域，即"计算 复杂性"，并奠
定了它的理论基础。
由于计算复杂性的重要性及"复杂性 "(学过有关课程的人大概都有此体会)，这个领域吸
引着许许多 多的学者，提出了许多有趣而复杂的问题。到目前为止，在"计算 复杂性理
论"中已提出与国民经济发展有密切联系的2000多个难 题，如货郎担问题、哈密尔顿回
路问题、装箱问题、整数规划问题、 子图同构问题、平面铺砖问题，等等。对其中任一
问题如果能找到 一个多项式时间的算法，也就找到了所有这些问题的多项式时 间算法
；而如果能证明其中任一问题不存在多项式时间算法，也 就证明了所有这些问题都不存
在多项式时间算法。
哈特马尼斯于1965年离开GE，重返康乃 尔大学，但他不是回到数学系，而是负责筹建计
算机科学系。由于 他的眼光和魄力，也由于他的民主作风，康乃尔大学的计算机科 学
系吸引了一批著名学者加盟，成为美国大学中水平最高、影响 最大的计算机科学系之一
。这些学者中包括我们将要介绍的另 一位图灵奖得主J.Hopcroft以及D.Gries，E.Horo
wity，P.Wegner，A.Shaw等。
1990年4月，美国科学研究委员会(National ResearchCouncil)的计算机科学与技术部(
现已改为计算机科学与通 信部，缩写CSTB)建立了一个由16名专家组成的委员会，负责
对计 算机科学与技术在21世纪的发展方向和研究领域进行评估 (Committee　to　Asse
ss　the　Scopeand　Direction　of　Computer　Scienceand　Technology)。哈特马 
尼斯受命担任该委员会主席。委员中包括我们已经介绍过的另 外两名图灵奖获得者J.G
ray和R.Reddy。哈特马尼斯组织委员会委员 和来自全美的120余名学者共同努力，于19
92年编写出版了《未来 的计算计算机科学与技术的广泛议题》(《Computing　the　Fu
ture　A　Broader Agenda for Computer Scienceand Engineering》)一书。本书对21
世纪计算机科学 与工程的研究、教育等重大课题进行了分析，对政府、产、学、研 各
部门如何适应新形势提出了一系列重要意见，很值得我国科 研管理部门重视和借鉴。
哈特马尼斯还是著名的Springer出版社 的《计算机科学讲课笔记》(《Lecture Notesi
n Computer Science》)系列丛书的 主编，这套丛书自70年代问世以来，至今已推出20
00多种专著，对 推动计算机科学的发展起了重要作用。
哈特马尼斯于30岁结婚，妻子也是拉 脱维亚人，但出生在德国。他们有3个子女。
哈特马尼斯论著极多，除大量发表于 杂志和会议的论文外，出版的主要著作有：
《时序机的代数结构理论》(《Algebraic Structure Theory of Sequential Machines
》，PrenticeHall,Inc.1966)
《可行计算和可证明的复杂性性质》 (《Feasible Computations and Provable Compl
exity Properties》，SIAM，1978)
《计算复杂性理论》(《ComputationalComplexity Theory》，AMS，1989)。1988年，为
纪念哈特马尼斯60寿辰，由A.L.Selman编 辑出版了一本纪念文集：《复杂性理论回顾》
(《ComplexityTheory Retrospective》，SpringerVerlag，1988)。本书收集了若干对
哈特马尼斯的生 平和成就的介绍性文章。
哈特马尼斯在接受图灵奖时发表了题 为"论计算复杂性及计算机科学的性质"("On Comp
utational Complexity and the Natureof Computer Science")的演说，刊载于Comm.A
CM，37(10)：P37～ 43(Oct.1994)。
哈特马尼斯的电子信箱为 jh@cs.cornell.edu。

--

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

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