迈克尔·拉宾 (科学家)

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

相关

  • 美国食品和药物管理局美国食品药品监督管理局(英语:U.S. Food and Drug Administration,缩写为FDA)为美国卫生与公众服务部直辖的联邦政府机构,其主要职能为负责对美国国内生产及进口的食品、膳食补充
  • 体积(英语:Volume)是物件占有多少空间的量。体积的国际单位制是立方米。一件固体物件的体积是一个数值用以形容该物件在空间所占有的空间。一维空间物件(如线)及二维空间物件(如正
  • 佐治亚州行政区划乔治亚州共有159个县,在众多州份中名列第二,仅次于德克萨斯州(254个县)。根据乔治亚州宪法(英语:Georgia State Constitution),所有的县都拥有地方自治权,并且能够自行处理县内地方性
  • 软舌螺软舌螺动物(学名:Hyolitha)是生活在古生代的一类神秘动物,具有小圆锥形的螺壳。这些物种目前都已全部灭绝;其化石一般只能保存锥壳、口盖和附肢三个部分,外壳为钙质成分,两侧对称。
  • 酰化反应酰化反应或称(酰基化反应),为有机化学中,氢或者其它基团被酰基取代的反应,而提供酰基的化合物,称为酰化剂。酰化反应,可依攻击的亲核试剂不同,可分为:氧酰化反应、氮酰化反应、碳酰
  • 眼镜熊眼镜熊(学名:),也叫安第斯熊,是南美洲特产的一种熊科动物,当地人称为“朱库马利”(艾马拉语)。它是南美唯一的一种熊,也是最后一种短脸熊(这种面部结构被认为主要食肉,不过现在眼镜熊偏
  • 刘涞刘涞(1522年-1574年),字子东,四川省嘉陵邻水县人,明朝政治人物。万历襄阳府追赠推官文林郎。刘涞,字子东,蜀嘉陵之邻水县人,因他的三子(刘三才)中乡试第一名,癸未年中三甲一百零八名进士
  • 白时中白时中(11世纪-1127年),字蒙亨,北宋寿州寿春(今安徽寿县)人。进士出身,累官为吏部侍郎,因事出知郓州。不久又得召用。政和六年(1116年),拜尚书右丞、中书门下侍郎。宣和六年(1124年),担任太
  • 冯嘉怡冯嘉怡(1969年7月10日-),出生于北京,中国大陆男演员,商人。已移民澳大利亚。
  • 雷神之锤II《雷神之锤II》(Quake II),是id Software于1997年冬发布的一款划时代的第一人称射击游戏作品。这个游戏是id Software在其创始人之一、著名游戏策划设计师约翰·罗梅洛(John Rom