迈克尔·拉宾 (科学家)

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

相关

  • 土壤土壤(德语:Boden,英语:soil)是一种自然体,由数层不同厚度的土层(德语:Bodenhorizont,英语:soil horizon)所构成,主要成分是矿物质。土壤和母质(岩石)的差异主要是表现在形态特征或物理、化
  • 阳明病阳明病,中医病名,伤寒论六经辨证之一。阳明,指的是足阳明胃经。两阳合明曰阳明。阳明主里,指胃肠的受纳消化功能。阳明病是燥热之邪内攻,烧灼津夜,与肠胃中食物的糟粕结合,形成燥屎
  • 细胞信号细胞信息传递(英语:cell signaling)是一个主管细胞基本活动并协调细胞行为的复杂沟通系统。细胞对周遭微环境进行感知与正确回应的能力是其发展、修复组织、免疫以及体内正常动
  • 溴化铜溴化铜是一种无机化合物,为二价铜的溴化物,化学式CuBr2。溴化铜可由氧化铜和氢溴酸反应得到:在固态,CuBr2有着聚合结构,其中平面单元对侧链接以形成链。CuBr2晶体属单斜晶系,空间
  • 阿拔斯阿拔斯(英语:Abbas、阿拉伯语:عباس‎),或译为阿巴斯,是常见的中东名称:
  • 多鳞白鱼多鳞白鱼(学名:)为辐鳍鱼纲鲤形目鲤科白鱼属的淡水鱼类,被IUCN列为濒危保育类动物,分布于中国云南省,为中国特有物种。体长可达13公分,栖息在中底层水域。 维基物种中有关多鳞白鱼
  • 丁是娥丁是娥(1923年11月12日-1988年7月9日),原名潘永华,小名“银男”,祖籍浙江吴兴,生于上海,中国沪剧表演艺术家,沪剧“丁派”艺术的创始人。丁是娥鲜活塑造了小飞娥、林佩芬、繁漪、阿庆
  • 老男孩老男孩可以指:
  • 褐伞残孔菌折伞残孔菌,分布于世界各地,属多孔菌科一种,色通常为浅肉至茶褐色。另外,该种野菇也是常见木栖寄生生的中型菇类。
  • 葫芦岛港葫芦岛港是辽宁省葫芦岛市的港口,位于渤海辽东湾沿岸。葫芦岛港的历史开始于1908年,清政府大员徐世昌聘请英国技师在此开港。1910年,葫芦岛开始兴建,但后因辛亥革命而中止。1930