当前位置 主页 > 站长资源大全 > iis7百科 > 最大化 缩小

    理查德·卡普——发明“分支界限法”的三栖学者

    栏目:iis7百科 时间:2019-11-14 09:37

      理查德·卡普教授现在是美国加州大学伯克利分校计算机科学讲座教授,担任美国科学院会刊(PNAS)等多个国际著名刊物编委。还是美国科学院、美国工程院、美国艺术与科学院、欧洲科学院院士。在计算机科学领域的基础贡献曾获图灵奖、冯诺依曼奖、美国国家科学勋章、哈佛大学百年奖章等奖项。
      卡普于1935年1月3日出生于波士顿,自那时以来一直对各种各样的兴趣感兴趣。他在哈佛大学学习过文科。他于1955年获得文学学士学位,第二年获得了理学硕士学位。然后,他继续在哈佛大学计算机实验室学习并获得博士学位。 1959年获得应用数学博士学位。
      卡普在IBM期间,主要是深入研究了与实际应用有密切联系的一系列数学问题,如路径问题、背包问题、覆盖问题、匹配问题、分区问题、调度问题等,取得了许多出色的成果。这些问题有一个共同的特点,即如果用图来表示问题,那么当图中增加一个结点时,需要考察的可能的解的数目就急剧增加,形成所谓“组合爆炸”(combinatorial explosion),使计算机的计算工作量大大增加,到一定程度就根本无法实现。以路径问题中最著名的旅行推销员问题为例,在卡普以前,最好的结果是Rand公司的丹齐格(George Benard Dantzig)、福格申(R.Fulkerson)和约翰逊(S.Johnson)用手工和计算机相结合的办法,求出了包含49个城市的旅行推销员的最佳路线。卡普和他的同事海尔特(M.Held)经过反复研究,终于提出了一种称为“分枝限界法”(branch—and—bound method)的新方法,用这种新方法实现的算法使旅行推销员能周游的城市数达到65个,从而打破了由Rand公司保持的记录。
      1968年,卡普离开IBM到加州大学伯克利分校工作。这里是计算机科学理论的又一个研究中心,库克(S.Cook,1982年图灵奖获得者)、布卢姆(M.Blum,1995年图灵奖获得者)等一批知名学者当时都在那里,学术气氛十分浓厚。布卢姆是计算复杂性理论的主要奠基人之一,库克则于1971年最早提出“NP完全性”问题。在这样的环境下,卡普对计算复杂性问题的研究日益深入。