迈克尔·拉宾 (科学家)

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

相关

  • 明胶明胶又称鱼胶或吉利丁(从英文名“Gelatin”译音而来,音译基准为粤语),是以动物皮、骨内的蛋白质即胶原蛋白制成,带浅黄色透明,无味的胶质,主要成分为蛋白质。明胶通常用于食物、药
  • H. influenzae流感嗜血杆菌(学名:Haemophilus influenzae),简称嗜血杆菌,前称费佛氏杆菌(或译拜菲尔氏菌)或流感杆菌,是一种没有运动力的革兰氏阴性杆菌。它是于1892年由费佛(英语:Richard Friedric
  • 卡加烟省卡加延省(Cagayan)是菲律宾吕宋卡加延河谷政区的一个省份。首府为土格加劳市(Tuguegarao City),本省位于吕宋岛的最东北端。卡加延省还包括了北边的巴布延群岛。卡加延省西邻北伊
  • 刺参仿刺参(学名:Apostichopus japonicus)为刺参科仿刺参属的动物,俗称刺参、沙噀、灰刺参、灰参、海鼠。中国北方辽宁大连、山东沿海多产。多制成干品,为名贵海珍品。现已开展人工养
  • 诺伯特·李奥·巴茨诺伯特·李奥·巴茨(英语:Norbert Leo Butz,1967年1月30日-)是美国的一位演员和歌手。他主要活跃在百老汇。巴茨是两次托尼奖最佳音乐剧男主角的获得者,并且是九位获此殊荣的演员
  • 张凤翼 (万历进士)张凤翼(?-1636年),山西代州人,明末政治人物,官至兵部尚书。张凤翼为万历四十一年(1613年)进士,授户部主事。崇祯八年(1635年)冬,召拜兵部右侍郎兼右都御史,代杨嗣昌总督宣、大、山西军务。
  • 塞尔维亚社会主义共和国塞尔维亚社会主义共和国( 错误:{{lang-xx}}:文本有斜体标记(帮助))是南斯拉夫社会主义联邦共和国的一个加盟共和国,也是塞尔维亚共和国的前身。
  • 尤哈·瓦伊尼奥尤哈·瓦伊尼奥(芬兰语:Juha "Watt" Vainio,1938年5月5日-1990年10月29日),芬兰歌手,作曲家,音乐剧韵诗翻译家。他创作了100多首歌曲,以及翻译或创作了上千首韵诗,被芬兰的众多歌手所
  • 森本梢子森本梢子(2月27日-)是日本漫画家,熊本县熊本市出身。毕业于真和高等学校和佐贺大学教育学部。血型O型。森本于1985年在《YOU增刊VIVID YOU》(集英社)发表出道作品《抱き寄せてプロ
  • 克鲁佐夫岛克鲁佐夫岛是美国的岛屿,位于太平洋海域,属于亚历山大群岛的一部分,由阿拉斯加州负责管辖,长39公里、宽14公里,面积433平方公里,最高点海拔高度975米,是该国第41大岛屿。坐标:57°10