迈克尔·拉宾 (科学家)

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

相关

  • 苏联共产党中央委员会总书记苏联共产党中央委员会总书记(俄语:Генеральный секретарь ЦК КПСС)是苏联共产党领袖的头衔。在俄国历史上,这个职位往往是苏联最高领导人的代名词。
  • 毛鼻水獭毛鼻水獭(学名:Lutra sumatrana,英语:Hairy-nosed Otter)也叫苏门答腊水獭,是一种分布在东南亚的水獭,栖息在淡水环境。该物种已经严重濒危,在1990年代,就被以为已经灭绝,但是后来又在
  • 开城特别市开城特别市(朝鲜语:개성특별시/開城特別市 Kaesŏng T'ŭkpyŏlsi */?),又名松都(송도)、松岳(송악)、开京(개경)、松京(송경),是朝鲜民主主义人民共和国的城市,近郊所产的高丽人参驰名国
  • 伦敦大轰炸(第二次世界大战)伦敦轰炸(The Blitz)是指在第二次世界大战中纳粹德国对英国首都伦敦实施的战略轰炸。德国对英国的轰炸发生在1940年9月7日至1941年5月10日间,轰炸范围遍及英国
  • 金秀璟金秀经(韩语:김수경;英语:Kim Soo Kyung;2001年10月6日-),是一名韩国女歌手及演员。为韩国女子团体Weki Meki成员之一,团中担任领舞、副唱以及反转魅力担当,所属经纪公司为Fantagio。2
  • 新吉工业区新吉工业区,位于台南市安南区与安定区交界的工业区,为台南县市合并后开发的首座工业区。因位于曾文溪附近,为避免工业排水影响下游的湿地生态,新吉工业区限制进驻厂商的类型,并标
  • 加塔尔加塔尔(Ghatal),是印度西孟加拉邦Medinipur县的一个城镇。总人口51586(2001年)。该地2001年总人口51586人,其中男性26869人,女性24717人;0—6岁人口5815人,其中男3001人,女2814人;识字
  • 柬英关系柬埔寨王国-联合王国关系是指柬埔寨与英国之间的双边关系。 柬埔寨脱离法国印度支那独立后,柬英于1953年建立了外交关系。 1978年,英国是第一个谴责柬埔寨共产党人权记录的国
  • 黄吉站黄吉站(朝鲜语:황길역/黃吉驛  */?)是位于韩国全罗南道光阳市黄吉洞的一座铁路站,属于光阳制铁线和光阳港线。
  • 鼓楼大街站鼓楼大街站是一个位于中国北京市西城区德胜街道、什刹海街道与东城区安定门街道、和平里街道交界北二环路、安定门西大街、德胜门东大街、旧鼓楼大街、旧鼓楼外大街交叉口鼓