迈克尔·拉宾 (科学家)

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

相关

  • 印度支那战争印度支那战争(越南语:Chiến tranh Đông Dương),是指1947年至1979年发生于印度支那半岛上的战争。以越南为主,牵涉到老挝、柬埔寨等东南亚多国。包括以下几场战争。
  • 赵炳玉赵炳玉 (조병옥) 1894年5月21日-1960年2月15日),号维石(유석),韩国独立运动家、经济学者、政治家。他是驻朝鲜美军政厅时期的警务部长和大韩民国内务部第5任部长(1950年7月-1951年5月
  • 孝康皇后 (明朝)孝康皇后常氏(1355年-1378年),开平王常遇春之女,明朝明兴宗朱标的正妻,追封皇后。洪武四年(1371年)四月,明太祖朱元璋亲册为皇太子妃。1374年,常氏生长子朱雄英,亦是朱标长子。1378年,生
  • 富里市富里市(日语:富里市/とみさとし  */?)是千叶县北部中央的一市。富里拥有广大的原野,台地上是放牧地。1583年(天正11年),北条氏康命千叶邦胤(日语:千葉邦胤)在两总原野设置放牧地。江
  • 朗道-利夫希兹方程在物理学上,朗道-利夫希兹-吉尔伯特方程(Landau–Lifshitz–Gilbert),是以列夫·达维多维奇·朗道、叶夫根尼·利夫希茨和T·L·吉尔伯特命名的物理方程,以差分方程为基础阐述一
  • 平泉澄平泉澄(1895年2月15日-1984年2月18日)是一位日本历史学家。1895年出生于日本福井县大野郡 (福井县),1918年毕业于东京大学,之后进入大学院留校任教,1926年升任助教授,1935年升任教
  • 永定河引水渠永定河引水渠位于北京市西部,是北京市的一项引水工程,自北京城西门头沟区三家店处永定河设拦河闸引水向东进入市区,利用南旱河引入玉渊潭后,于西便门汇入护城河。渠道全长25.13
  • 国境以南 太阳以西《国境之南 太阳之西》是日本作家村上春树的一本小说。这篇小说和村上以前的小说基调基本相同,叙事方式也采用第一人称口吻,主人翁是中年男子。这部小说主要讲述了男主人公如
  • 逢魔时刻逢魔时(おうまがとき),或大祸时(おおまがとき),即黄昏时刻,此时天色渐暗,昼夜交错,在日本文化中被说是会遭逢灾祸,或是容易遇到魔物(妖怪、幽灵)的时刻。如同字面意义,逢魔时刻即是遭遇魔
  • 檀香山巴士檀香山巴士(英语:TheBus)是美国夏威夷州瓦胡岛的公共巴士交通系统。在2012至2013的财务年度,该系统拥有110条线路、518辆运营车辆,客运量约为7,550万人次。该巴士系统由瓦胡公交