迈克尔·拉宾 (科学家)

✍ dations ◷ 2025-12-05 09:15:06 #1931年出生,在世人物,图灵奖获得者,计算机科学家,以色列科学家,犹太科学家,普林斯顿大学校友,耶路撒冷希伯来大学校友,耶路撒冷希伯来大学教师,以色列犹太人,

迈克尔·O·拉宾(Michael Oser Rabin希伯来语:מִיכָאֵל אֹשֶׁר רַבִּין‎,1931年9月1日- )是一名以色列计算机科学家,1976年图灵奖得主。

拉宾出生于德国布雷斯劳(二战后成为波兰弗罗茨瓦夫),父亲是一个拉比。

1953年,他获得希伯来大学的理学硕士,1956年获普林斯顿大学博士学位。

1959年,拉宾和达纳·斯科特共同发表了“有限自动机与其判定性问题”()的论文,提出了非确定自动机的观点。他们也因此获得了1976年的图灵奖,并做“计算机复杂性”(Complexity of Computations)的演讲。图灵奖的引文是:

因他们的合著论文“有限自动机与其判定性问题”。论文中引入了非确定自动机的概念,被证明是(计算理论科学研究中的)一个非常重要的概念。拉宾和斯科特的这篇经典论文成为了这个领域后续研究的源泉。

非确定自动机已经成为计算复杂度理论中的一个重要概念,特别是在描述P与NP问题的复杂度类时。

1969年,拉宾证明N successors的二阶逻辑是可判定的。证明的关键部分暗示了奇偶游戏(英语:Parity game)的确定性。1975年,拉宾发明了米勒-拉宾检验,这是一个相当快速的随机化算法(有较小的可能性错误),用于判断一个大数是否是素数。 快速素数检验是目前大部分公钥密码体系的关键。1979年,拉宾发明了第一个非对称密码系统——拉宾密码系统(英语:Rabin cryptosystem)。它的安全性被证明和整数因式分解的复杂度相同。1981年,拉宾提出了不经意传输技术。 1987年,拉宾和理查德·卡普提出了一个著名的字符串搜索算法——拉宾-卡普算法。

相关

  • 伊特内斯省伊特内斯省是玻利维亚的省份,位于该国东北部,属于贝尼省的一部分,首府设于玛格达莱娜,面积36,576平方公里,2006年人口20,190,人口密度每平方公里0.55人。坐标:13°30′00″S 63°19
  • 米歇尔·阿弗拉克米歇尔·阿弗拉克(阿拉伯语:ميشيل عفلق‎,1910年1月9日-1989年6月23日)是一位叙利亚哲学家、社会学家和阿拉伯民族主义者。他的理论对复兴社会主义的发展及其政治运动产
  • 图罗尤语图罗尤语是亚拉姆语的一种现代方言,是叙利亚语的西部方言,在叙利亚东北部及土耳其东部的叙利亚正教会信徒使用。“图罗尤语”的名字来自“图罗”()是土耳其东南部图尔阿布丁(英
  • 安纳塔汉岛安纳塔汉岛(英语、查莫罗语:Anatahan),是一座位于美属北马里亚纳群岛中的小岛。岛上的复式火山推断为于全新世所产生。安纳塔汉岛的面积为31.21平方公里,岛上的覆盖着许多热带植
  • 杜铁环杜铁环(1938年-),辽宁鞍山人,中国人民解放军上将。1955年,其加入中国人民解放军。历任班长、团政治处宣传股文化教员、师政治部组织科、青年科干事,军政治部干部处干事、师长、集团
  • 稳定性理论数学中的稳定性理论是指微分方程的解以及动态系统的轨迹在初始条件有小扰动时的稳定性。像热传导方程式就是稳定的偏微分方程,因为初始值的小扰动只会造成之后温度的小幅变化
  • 朝日电视控股株式会社朝日电视控股(日语:株式会社テレビ朝日ホールディングス),简称朝视控股(日语:テレ朝ホールディングス)、朝日电视HD(日语:テレビ朝日HD)或朝视HD(日语:テレ朝HD),是日本的一家以大
  • 国王十字车站 (悉尼)国王十字车站(英语:Kings Cross railway station)是悉尼城市铁路辖下的一个车站,位于国王十字地底。它是随着东郊线在1979年开幕,拥有一个岛式月台,并且设有升降机。每天每小时会
  • 洛朗·施瓦茨洛朗-莫伊兹·施瓦茨(Laurent-Moïse Schwartz,1915年3月5日-2002年7月4日),法国数学家,毕业于巴黎高等师范学院。他获得1950年的菲尔兹奖,以嘉许他的分布论的工作。分布论给予诸如
  • 上海蔡元培故居上海蔡元培故居位于上海市静安区华山路303弄16号,是蔡元培在上海的最后一处住所,1984年被列为上海市文物保护单位,也是上海市爱国主义教育基地。房屋是一幢独立式花园洋房,有红