迈克尔·拉宾 (科学家)

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

相关

  • 鱼肝油鱼肝油(也称“肝油”)是一种从鳕鱼等海洋鱼类肝脏中提取的油,通常为黄色到橙红色的透明油状液体,带有鱼腥味。1848年挪威开始用水蒸汽加热法制造鱼肝油。1880年日本采用水煮法制
  • CV-2 列星顿号坐标:15°20′00″S 155°30′00″E / 15.33333°S 155.50000°E / -15.33333; 155.50000列克星敦号航空母舰 (CV-2)又名列克星顿或李克星顿是列克星敦级航空母舰的一号舰。
  • CBO戏剧频道中国电视剧频道(英语:CBO Channel)是新加坡新电信拥有的频道,专为播出内地电视剧,连续6小时。
  • 银楼银楼为一种珠宝店,常见于华人文化区的通俗称呼,银楼不同于百货公司专柜的品牌珠宝专柜(如:卡地亚、蒂芬妮)而是单独开设于社区的个人经营型态,贩售的珠宝为自制或是家庭工厂、中小
  • HoneyHoney可以指:
  • 阻力危机阻力危机是一种流体力学的现象,是流场的雷诺数增加到一定程度时,其阻力系数突然下降的现象。针对圆形物体(例如球或是圆柱)的阻力危机现象已有详尽的研究。当雷诺数增加到大约30
  • 李承烨 (政治人物)李承烨(朝鲜语:리승엽,1905年2月8日-1954年7月30日),朝鲜民主主义人民共和国政治人物、共产主义者。李承烨1905年生于京畿道富平郡,生于一个贫穷的家庭。1924年加入朝鲜共产党。曾
  • 迷走建筑迷走建筑(英语:construct city)是在台湾宜兰县开始的自我学习的非营利团体的特殊活动,在当地是一个带有对都市建筑与环境关注的社群活动,宣扬互助和集体以及乐观精神,反思环境对立
  • 栾克勇栾克勇(1970年9月23日-),台湾音乐制作人,作品涵盖华语、闽南语、客语流行音乐。2011年获得第22届金曲奖最佳客语专辑奖、最佳客语歌手奖,也是首位非客家人获得此奖项者(父亲是外省
  • 霞光霞光(或天空辉光)是部分来自夜空本身的光照,而最常见的来源自人造光源发出的光污染。这些累积在高空中的大片霞光,可以来自数公里外城市无用的光照。来自人造灯光的霞光在全世界