首页 > 知识&问答
哈特马尼斯——复杂性理论的重要奠基人
发布时间:2024-11-06 16:09:26 / 浏览量:
JurisHartmanis是美国杰出的理论计算机科学家。康奈尔大学计算机科学教授。哈特马尼斯是拉脱维亚人,生于1928年。二战期间,为躲避战火,哈特马尼斯一家人背井离乡,沦为“流民”(displacedperson)。
1993年,他和理查德·史坦斯(RichardStearns)因对计算复杂性理论的杰出贡献而获得了图灵奖。
哈特马尼斯于30岁结婚,妻子也是拉脱维亚人,但出生在德国。他们有3个子女。1988年哈特马尼斯60寿辰时,由塞尔曼(A.L.Selman)编辑出版了一本纪念文集《复杂性理论回顾》(ComplexityThe-oryRetrospective,Springer,1988),其中包括若干对哈特马尼斯的生平和成就的介绍文章。
哈特马尼斯的中学学业就是在德国哈瑙(Hanau)的难民营中完成的。之后他进入德国马尔布克大学学习物理(Marburg是一座大学城,离法兰克福不远)。两年半之后的1950年,哈特马尼斯获得资助,来到美国,进入堪萨斯城大学攻读硕士学位。但由于该校没有物理学的研究生课程,哈特马尼斯只得改学数学。他用了一年时间取得硕士学位,并被加利福尼亚理工学院接收为博士研究生,从事格论(latticetheory)的研究。4年后,哈特马尼斯完成博士论文,1955年取得博士学位,进入康乃尔大学数学系任教。但他在那里只工作了一年多,就转入通用电气公司设在纽约州斯克内克塔迪(Schenectady)的研究实验室,因为那里新建立了一个“信息研究部”,主任是理查德·舒伊(RichardShuey)博士,开展有关计算机和信息学的研究,这一新的领域激发起了哈特马尼斯极大的兴趣和热情。
Juris和Audrey当时,香农(ClaudeElwoodShanon)的信息论问世不久,香农给出了一个公式,可以计算在一定的信号和噪声平均功率之下,给定带宽的信道在单位时间内的最大信息传输量(这个公式被叫做“香农公式”)。念过物理的哈特马尼斯受此启发,敏锐地想到,抽象的计算过程也应该有精确的定量法则,以确定为了对每一个问题求得解答,需要多少计算工作量。围绕这一设想哈特马尼斯和曾是普林斯顿大学的研究生,暑假到公司打过工,后来成为他的同事的斯特恩斯合作,开展了深入的研究,其结果就是那篇著名的论文“论算法的计算复杂性”。这篇论文开辟了计算机科学的一个新的研究领域,即“计算复杂性”,并奠定了它的理论基础。
哈特马尼斯还是著名的Spfinger出版社的《计算机科学讲课笔记》(LectureNotesinComputerScience)系列丛书的主编,这套丛书从20世纪70年代问世以来,至今已推出2000多种专著,许多重要的计算机科学理论问题和新概念、新技术、新方法都是由这套丛书首先提出并展开与深入的,对推动计算机科学技术的发展起了重要作用。