迈克尔·拉宾

✍ dations ◷ 2025-07-04 15:44:37 #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年,拉宾提出了不经意传输(英语:Oblivious transfer)技术。 1987年,拉宾和理查德·卡普提出了一个著名的字符串搜索算法——拉宾-卡普算法。

相关

  • span style=color:black;b冰河时期/b/span大冰期(英语:Ice Age),又称“冰川期”或“冰川期”,是指地球大气和地表长期低温导致极地和山地冰盖大幅扩展甚至覆盖整个大陆的时期。大冰期内部又分为几次冰期(glacial period、g
  • 月角距月角距是月球和另一个天体之间的角度,是在天文导航中使用的术语。领航员可以利用月角距 (也称为月球) 和航海年历计算格林尼治时间。然后,领航员不需要航海钟就可以确定经度。
  • 歧化反应歧化反应又名“自身氧化还原反应”,为化学反应的一种。在歧化反应中,两个一样的反应物或元素,其一之氧化数(化合价)会上升,另一则会下降。氯气中氯的化合价为0。氯离子中氯的化合
  • 角状胶角耳角状胶角耳(学名:Calocera cornea)是属于花耳目花耳科胶角耳属的一种真菌,生长在阔叶树或针叶树朽木上。该种分布于中国、日本、巴西、匈牙利、丹麦、比利时、爪哇、乌干达、加
  • 龚书铎龚书铎(1929年3月-2011年11月9日),福建泉州市人。中国历史学家、教育家,国务院学位委员会历史学科评议组原召集人,中国史学会原副会长,北京市历史学会原会长,北京师范大学历史学院原
  • 高文华高文华可以指:
  • 撒哈拉地区撒哈拉地区,泛指位于撒哈拉沙漠的非洲,常与撒哈拉以南非洲相对。撒哈拉沙漠是世界上最大的沙漠,有数个国家位于其范围内。本区气候恶劣,降水稀少,是世界上最不适合人类居住的地区
  • 尼俄伯尼俄伯(英语:Niobe),古希腊神话女性人物之一。父为坦塔罗斯。曾多次吹嘘其子女,后为勒托之子阿波罗所尽杀其子女而悲痛化为石头,后移至弗里吉亚之西皮洛斯山。其事迹常反映于相关
  • 联邦议会 (奥地利)联邦议会(德语:Bundesrat)是奥地利议会的上议院,和奥地利国民议会共同组成了奥地利议会。联邦议会的议员按奥地利各州的人口比例分配。每个州最少可拥有3名议员,最多可拥有12名议
  • 何敏枫何敏枫(1951年1月7日-)是一名美国籍华裔的童话作家。何敏枫出生于缅甸仰光,父亲是经济学家及外交官,母亲是一名化学家。她从很小的时候就已经去到泰国生活及读书,直至大学时代去了