迈克尔·拉宾 (科学家)

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

相关

  • 加权平均数加权平均数与算术平均数类似,不同点在于,数据中的每个点对于平均数的贡献并不是相等的,有些点要比其他的点更加重要。加权平均数的概念在描述统计学中具有重要的意义,并且在其他
  • 英伦航空|G1=地名英伦航空(英文:British Midland International,营业名称:bmi。中文亦有译名:英国中部航空、米德兰航空)是英国的一家航空公司,以伦敦希斯罗国际机场及曼彻斯特国际机场为枢
  • 马里奥·贺历马里奥·贺历(捷克语:Mario Holek;1986年10月28日-)是一位捷克足球运动员。在场上的位置是中后卫和防守型中场。他现在效力于捷克足球甲级联赛球队巴洛克斯巴达足球俱乐部。他也
  • 邵虚白邵虚白(1906年-1940年)字全品,浙江鄞县人。民国时期记者、政治人物、烈士。大清光绪三十二年(1906年) 生。1922年,毕业于江苏南京金陵初级中学。后任职于宁绍轮船公司之新宁绍轮,加
  • 迈克尔·艾斯纳迈克尔·丹曼·艾斯纳(Michael Dammann Eisner,1942年3月7日-)是一位美国的企业家。他在1984至2005年间担任华特迪士尼公司的执行长。艾斯纳出生在纽约州基斯科山 (纽约州)(英语:M
  • 中国李中国李(学名:),通常称李子,又名毛梗李,为蔷薇科梅属(即李属)下的一个种,原产自中国,现在朝鲜半岛、日本、美国、澳大利亚也有种植。李子树可长至10米高,叶子有6至12厘米长,2.5至5厘米宽
  • 马里斯·扬颂斯马里斯·伊瓦尔斯·乔治·扬颂斯(拉脱维亚语:Mariss Ivars Georgs Jansons,1943年1月14日-2019年11月30日)生于里加,拉脱维亚指挥家。其父亲阿尔维兹·杨松斯(英语:Arvīds Jansons)
  • 夏风杨贵媚、黄西田、何以奇、侯彦宇蒲公英电影事业有限公司《夏风》(英语: ),2016年公视人生剧展,由杨贵媚、黄西田、何以奇、侯彦宇领衔主演。公视HD台于2016年4月2日播出、公视主
  • 刃物会馆前站刃物会馆前站(日语:刃物会館前駅/はものかいかんまええき  */?)是位于岐阜县关市平和通,长良川铁道的越美南线车站。车站编号是5。车站是一座地面车站,设有1面1线单式月台。月台
  • 利森瑟费讷科格尔山坐标:47°05′N 11°06′E / 47.083°N 11.100°E / 47.083; 11.100利森瑟费讷科格尔山(德语:Lüsener Fernerkogel),是奥地利的山峰,位于该国西部,由蒂罗尔州负责管辖,属于斯图拜阿