迈克尔·拉宾 (科学家)

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

相关

  • 六氯苯六氯苯是有6个氯取代基的苯,一开始是被做为榖物防霉菌的使用,但也可以用在工业用途上,不过这个用品在斯德哥尔摩公约中属于被全球禁用的持久性有机污染物。在纯用品是无色细针
  • 四级结构蛋白质四级结构(英语:Protein quaternary structure)是生物化学中用于描述多亚基蛋白质复合物中各个折叠蛋白质亚基的排列组合。许多蛋白质实际上是多个多肽链的组装。 四级结
  • ɦ浊声门擦音(英:voiced glottal fricative)是 /h/ 相应的浊音,亦称“浊喉擦音”。发音时候气流通过声门并且带有声带的振动。此音在国际音标中的符号为⟨ɦ⟩,在X-SAMPA中的符号为
  • 贝乌热茨灭绝营纳粹集中营转移营比利时:布伦东克堡垒 · 梅赫伦转移营法国:居尔集中营 · 德朗西集中营意大利:波尔查诺转移营荷兰:阿默斯福特集中营 · 韦斯特博克转移营挪威:法斯塔德集中营部
  • 爱德华·阿尔比爱德华·阿尔比(英语:Edward Albee,1928年3月12日-2016年9月16日),美国剧作家,最著名的作品有《谁害怕弗吉尼亚·伍尔芙?》、《动物园的故事》、《优美的平衡》、《海景画》等。其作
  • 科德角鳕鱼角(英语:Cape Cod),是美国东北部马萨诸塞州伸入大西洋的一个半岛,面积1033平方公里。1914年,美国在该半岛与大陆连接处开掘鳕鱼角运河,使鳕鱼角实际上成为了一个岛屿。
  • 狩魔猎人《狩魔猎人》(英语:Gabriel Knight)是一系列在九十年代由雪乐山公司(Sierra Entertainment)制作和出版的冒险游戏和小说。本游戏系列环绕书店老板及惊险故事作家Gabriel Knight,一
  • 叱干姓《百家姓》中无此姓叱干姓,是中文姓氏之一。叱干姓为代北复姓,不属于《百家姓》,一说源自鲜卑部落名、一说是羌族姓氏,有说衍生自甘姓。叱干姓虽然在北魏的孝文帝改革中被改为单
  • 里见浩太朗里见浩太朗(日语:里見 浩太朗/さとみ こうたろう ,1936年11月28日-),原名佐野邦俊(日语:佐野 邦俊 ),男,日本演员。1936年出生于日本东京都,原名佐野邦俊,毕业于静冈县立富士宫北高等学
  • 酮基丙二酸二乙酯酮基丙二酸二乙酯(英语:Diethyl oxomalonate)是丙酮二酸(中草酸)的二乙醇酯,其羰基反应活性很高,可发生狄尔斯–阿尔德反应、环加成反应、烯反应。