迈克尔·拉宾 (科学家)

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

相关

  • 心内膜炎心内膜炎(英语:Endocarditis)是心脏的心内膜(心腔中的最深层的组织)引发的炎症,通常和心脏瓣膜有关。此外,心内膜炎也可能与室间隔(英语:interventricular septum)、腱索(英语:chordae t
  • 西蒙·纽康西蒙·纽康(英语:Simon Newcomb,1835年3月12日-1909年7月11日),美国籍加拿大天文学家、数学家暨科幻小说作家。虽然他只接受过短期学校教育,却在钟表学(英语:Horology)、经济学及数学
  • 冠轮动物总门参见正文冠轮动物(拉丁语:Lophotrochozoa)是动物界中的一大支,属于两侧对称动物,与蜕皮动物(Ecdysozoa)组成原口动物。原口动物和后口动物(Deuterostomia)并列为两侧对称动物的两个分
  • 俄罗斯联邦直辖市联邦直辖市是俄罗斯的联邦主体的一种。俄罗斯联邦到2014年为止共分为85个联邦主体,其中三个是联邦直辖市。但三个直辖市中的塞瓦斯托波尔市未被国际普遍承认为俄罗斯领土。
  • 僧护 (中观派)龙树、圣天、无著、 世亲、陈那、法称、 释迦光、功德光 【其他】─ 《入中论》 《释量论》 《俱舍论》 《现观庄严论》 《戒律本论》【其他】─ 僧护(梵语:Samgha-rakṣita),
  • 大谷喜久藏大谷喜久藏(1856年2月4日-1923年11月26日),日本陆军军人,华族。历任教育总监、浦盐派遣军司令官、军事参议官、青岛守备军司令官等职,官至陆军大将勲一等功一级男爵。大谷喜久藏生
  • 肯·福莱特肯尼斯·马丁·福莱特,CBE(英语:Kenneth Martin Follett,1949年6月5日-),英国历史小说和悬疑小说家,代表作有《针之眼》、《圣殿春秋》等。他的小说售出了将近1亿5千万本。肯·福莱
  • 弗雷德里克·雷明顿弗雷德里克·雷明顿(Frederic Sackrider Remington 1861年10月4日-1909年12月26日)美国画家,插画家,雕刻家,作家,尤其擅长反映美国西部早期的描绘。由他所绘的早期美国牛仔的形象几
  • 嘻哈女权主义嘻哈女权主义者被定义为1964年后出生的年轻女权主义者,她以一种混合了女权主义和嘻哈情感的嘻哈女权主义方式接近政治团体。嘻哈女权主义这个词是由颇具挑衅性的文化评论家琼
  • 郁达夫传奇郁达夫传奇是1988年上映的剧情电影,以郁达夫生平为题材。该片描述了郁达夫的一生,以及最后1945年二战结束后郁在荷属东印度苏门答腊失踪的故事。