迈克尔·拉宾 (科学家)

✍ dations ◷ 2025-12-05 00:29:41 #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年,拉宾和理查德·卡普提出了一个著名的字符串搜索算法——拉宾-卡普算法。

相关

  • 2012年中东呼吸综合征爆发2012年中东呼吸综合征爆发指2012年起于中东地区爆发的中东呼吸综合征(MERS)疫情。2012年,世界卫生组织表示正“忙于更进一步的描述这种新型冠状病毒”,并且“立即警告与此病毒相
  • 鼻音 (辅音)鼻音是按发音方法分类的一类辅音。发音时,口腔中的气流通路被阻塞,软颚下垂,气流通过鼻腔,与气流从口腔流出的口腔辅音相对。 (少数的挤喉音可能同时具有口腔辅音与鼻音的性质。)
  • 名称名称(或名字)即对一切事物,概念,感觉给定的标签,以便区分不同事物、同一事物的不同个体,分为人名和事物名称。姓名为姓氏和人名的合称,雅称“尊姓大名”。事物名称指对自然界一切
  • 法国共和国卫队法国共和国卫队(法语:Garde républicaine)是法国的一支亲卫队,属国家宪兵管辖,主要负责政府机构的警卫工作。此外法国共和国卫队还负责保护要人及国宾。法国共和国卫队由第1步兵
  • 约瑟夫·基希涅夫斯基约瑟夫·基希涅夫斯基(罗马尼亚语:Iosif Chişinevschi),原名雅各布·罗伊特曼(罗马尼亚语:Jakob Roitman;1905年12月26日-1963年),犹太人,莫斯科派,罗马尼亚共产党中央政治执行委员会委
  • 多彩环塔螺多彩环塔螺(学名:)是小塔螺科小塔螺属的一种。主要分布于台湾,常栖息在浅海沙底。
  • 不老温泉坐标:23°03′58″N 120°41′06″E / 23.066062°N 120.685058°E / 23.066062; 120.685058不老温泉位于台湾高雄市六龟区荖浓溪的支流溪谷中,依地质分类属于台湾中央山脉板
  • 南山站 (青海省)南山站位于青海省海西蒙古族藏族自治州天峻县南山村,是青藏铁路的一座车站,距离西宁站333公里,于1979年启用,由青藏铁路公司营运。车站曾为五等站,承担货运业务,2014年因新关角隧
  • 敬 (儒家)在儒家思想中,敬,是一种内心的修养,保持戒慎恐惧的谨慎心态。在理学中,敬是一个重要的讨论课题,程朱学派主张应持敬,陆王学派则以主敬为主,形成长期的争议。在先秦时代,敬就是儒家强
  • 特伦德冰原岛峰坐标:78°49′S 27°25′W / 78.817°S 27.417°W / -78.817; -27.417特伦德冰原岛峰(英语:Tailend Nunatak),是南极洲的冰原岛峰,位于科茨地,处于塞隆山脉北端,海拔高度535米,在1957