迈克尔·拉宾 (科学家)

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

相关

  • 卫星细胞卫星胶质细胞(英语:Satellite glial cells)为神经胶质细胞的一种,包覆于周围神经系统及神经节中神经元的外侧。此种细胞在中枢神经系统中的功能推测可能与星状细胞相似,为提供养
  • 观察仪器观测仪器(viewing instrument)是用于查看或检查物件或场景,或某种电子属性或信号的设备。在某些情况下,查看的可能是抽象的数学。在英许系的地区,许多观测仪器的名称都来自英语的
  • 椒盐卷饼椒盐卷饼,英文为Pretzel ( listen 帮助·信息),德语发音为 (德语:Breze(l)) ( listen 帮助·信息),也被称为扭结饼、蝴蝶饼、普雷结,是一种用面团拿去烘烤的糕饼,通常为绳结的形
  • 小野健斗小野健斗(1989年8月9日─),是一位日本男演员、模特儿,出生于日本东京都,身高187.1cm,体重57kg(之后的身高为185cm,体重63kg),血型O型。
  • 谢南光谢南光(1902年11月18日-1969年7月26日),原名谢春木,笔名追风,出生于彰化,是台湾日治时期著名的社会运动参与者,也是战后著名的中国政治人物。谢春木于1921年毕业于台北师范学校(现国
  • 义顺镇义顺镇(英语:Yishun,泰米尔语:யீஷூன்),是新加坡一个新市镇,位于新加坡共和国北部。下辖五个区域:义顺中、义顺南、义顺东、忠邦城和坎贝拉。 前身为建于1987年的义顺巴士转换
  • 施瑞娅·萨兰施瑞娅·萨兰(英语:Shriya Saran,1982年9月11日-)是印度电影女演员。她主要出现在南印地、宝莱坞和美国电影。她最为人所知的作品包括和南印度巨星Rajinikanth合作的泰米尔电影《
  • 法律实证主义法律实证主义(legal positivism; Rechtspositivismus,为与德国之法律实证主义(Gesetzespositivismus)区分,严格上称为法实证主义),或称法实证论、实证法学、概念法学派,是当代的一种
  • 博克龙属博克龙属(学名:,取名自喜马拉雅神博克孜(英语:Begtse))是一属新角龙类恐龙,生存于白垩纪早期的蒙古。该属仅含一个物种,即孜博克龙(),已知于部分颅骨和一些非常零碎的颅后骨骼(英语:postcr
  • 反转剧《反转剧》是韩国SBS电视台于2004年-2006年在每个星期天晚上在人气综艺节目X-Man播完后播出的短剧,长度约45分钟,由两个故事组成,每个故事大约22分钟左右,每次的内容都是独立的,