迈克尔·拉宾 (科学家)

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

相关

  • 莫达非尼莫达非尼(英文名Modafinil)是一种觉醒促进剂(英语:Wakefulness-promoting agent),被用于对发作性嗜睡病、轮班工作睡眠紊乱以及与阻塞性睡眠呼吸暂停相关的白天过度嗜睡(英语:Excess
  • 抽象机器抽象机器(英语:Abstract machine),又称抽象电脑(abstract computer),利用自动机理论,创建出电脑硬件或软件的理论模型。把运算过程抽象化,一般来说是采用离散时间模型,可应用于计算机
  • 罗纳德·费希尔罗纳德·艾尔默·费希尔爵士,FRS(英语:Sir Ronald Aylmer Fisher,1890年2月17日-1962年7月29日,英语发音.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux L
  • 古宁头战史馆坐标:24°28′58.89″N 118°19′15.88″E / 24.4830250°N 118.3210778°E / 24.4830250; 118.3210778 古宁头战史馆位于中华民国福建省金门县西北部,1984年(民国73年)由陆军金
  • 不承认主义不承认主义,又名史汀生主义,为1931年(民国二十年)日本关东军与中国东北军在中国东北爆发九一八事变后,美国国务卿亨利·刘易斯·史汀生于次年一月所宣示的美国官方立场。该主义主
  • 夏季奥林匹克运动会篮球比赛篮球自1936年以来一直是夏季奥运会比赛项目之一。美国包揽了1936年到1968年7届男子冠军。
  • 郑机城际铁路.mw-parser-output .RMbox{box-shadow:0 2px 2px 0 rgba(0,0,0,.14),0 1px 5px 0 rgba(0,0,0,.12),0 3px 1px -2px rgba(0,0,0,.2)}.mw-parser-output .RMinline{float:non
  • 温德姆·霍尔斯韦勒温德姆·霍尔斯威尔(英语:Wyndham Halswelle,1882年5月30日-1915年3月31日),英国男子田径运动员。他在1908年夏季奥运会田径比赛男子400米比赛的重赛中不战而胜,获得金牌。除此之外
  • 温特斯 (加利福尼亚州)温特斯(英文:Winters),是美国加利福尼亚州优洛县下属的一座城市。建市于1898年2月9日,面积 大约为2.91平方英里 (7.5平方公里)。根据2010年美国人口普查,该市有人口6,624人。
  • 纹影法纹影法是一门主要用于测量速度,拉伸率等物理量的物理测量方法。纹影法测量的是从光源发出的光线在通过不均匀折射率场时,受扰动的光线对于未扰动光线的偏转角。纹影法测量偏转