迈克尔·拉宾 (科学家)

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

相关

  • 出生出生,或者出世,是指令后代降生于世的行为或过程。在哺乳动物中,这一过程由荷尔蒙控制,使得子宫壁肌肉收缩,并在胎儿具备呼吸、进食能力的时候将其排出。部分物种的子嗣较为早成(英
  • 投石党乱投石党动乱(法语:Fronde),或称福隆德运动(1648年-1653年),一场紧随着法西战争(1635-1659年)而爆发的法国内战。该运动源自投石器(Fronde),此系源于当时的摄政,马萨林枢机主教的支持者遭巴
  • 神圣的人神圣之人(拉丁语:Homo sacer,字面意为“分别的人”)是罗马法中的一个刑法概念。这样的人,一方面被驱逐出人类社会,因此不受法律保护,任何人都可以杀死他而不构成犯罪。但另一方面他
  • EViewsEViews是为Windows设计的统计分析软件,主要应用于计量经济分析。 EViews是由Quantitative Micro Software(QMS)开发的。1.0版于1994年3月推出,代替了原先的MicroTSP软件,目前最新
  • 凡内谷站凡内谷站(朝鲜语:범내골역/범내골驛  */?)是釜山广域市釜山镇区凡川洞,属于釜山都市铁道1号线的地铁站。邻近釜山交通公社东海线凡一站,但不作客运站。1面2线岛式月台的地下车站
  • 乔治敦 (南卡罗来纳州)乔治敦(英文:Georgetown),是美国南卡罗来纳州下属的一座城市。城市类型是“City”。其面积大约为7.52平方英里(19.47平方公里)。根据2010年美国人口普查,该市有人口9,163人,人口密度
  • 秦瑛秦瑛,浙江山阴人,明朝政治人物。同进士出身。正统元年,登丙辰科进士,授翰林院检讨。
  • BankuBanku是一道加纳料理,为白色、平滑的面团,由玉米粉和木薯粉以一定比例和水混合成生面团后,经发酵后烹煮而成,常与汤、炖菜、辣椒酱与鱼一起食用。这道菜特别盛行于加纳南部的埃
  • 银铃会银铃会,台湾的民间文艺团体,该会创于1943年,由张彦勋跟台中一中那些爱好文学的同班同学发起。该会原本只有台湾人,国府接收台湾以后,陆续有几位从中国大陆来的人加入。成员有张彦
  • 私立夏葛医学院私立夏葛医学院(The Hackett Medical College),前身为广东女医学堂(The Canton Woman Medical College),是中国最早的女子医学院和第二所医科大学,于清光绪二十五年(1899年)由基督教