迈克尔·拉宾

✍ dations ◷ 2024-12-23 09:02:59 #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年,拉宾提出了不经意传输(英语:Oblivious transfer)技术。 1987年,拉宾和理查德·卡普提出了一个著名的字符串搜索算法——拉宾-卡普算法。

相关

  • 中世纪末期中世纪后期 (Late Middle Ages),或称中世纪晚期、中世纪末期、中古后期、中古晚期、中古末期,是历史学者用来描述14世纪至15世纪(约1300年-1499年)欧洲历史的术语。中世纪晚期位
  • 氟可那挫氟康唑(英语:Fluconazole)是一种三唑,可用于医治由真菌引起的病征。常见的商品名称有大扶康(Diflucan)或“Trican”(辉瑞)。在墨西哥的药店则以“Alfumet”为名销售。氟康唑是抗真菌
  • 北弗吉尼亚军团北弗吉尼亚军团(Army of Northern Virginia)是美国内战时南方的一支主要军团,成立于1862年,其主要对手是波多马克军团。北弗吉尼亚军团的活动地区全都是在东线,主要任务为保护
  • 美国军方合众国武装力量(英语:United States Armed Forces),中文通称美军,是美国的联邦武装部队,为目前世界整体军事实力最强的军队,其规模和装备均位于世界第一。美军分为六大军种,即陆军、
  • 清原满族自治县清原满族自治县是辽宁省抚顺市下辖的一个自治县。清原的意思为“大地清平”。面积3921平方千米,人口34万。邮政编码113300。自治县人民政府驻清原镇。下辖9个镇、5个乡:清原镇
  • 自我所有权自我所有权(self-ownership),或称个人主权(individual sovereignty),是一种个人主义概念,主张个人拥有对其自身或生命的最高控制主权。在自我所有权的状态下,个人对其自己的行动拥有
  • 奥林帕斯山 (火星)坐标:18°24′N 226°00′E / 18.4°N 226°E / 18.4; 226 (奥林帕斯山(Olympus Mons))奥林帕斯山(拉丁语:Olympus Mons)是火星上的盾状火山,亦为太阳系中已知最高的山,高于基准面21
  • 冯铨冯铨(1595年-1672年),字伯衡,号鹿菴。直隶涿州(今河北涿州市)人。明末清初政治人物,两朝皆官至大学士。冯铨为蓟辽兵备道冯盛明之子。万历四十一年(1613年)中进士,改庶吉士,授翰林院检讨
  • 珠海公交巴士珠海公交巴士有限公司,简称:珠海公交(英语:Zhuhai City Bus Company Limited),由1979年7月成立的珠海市公共汽车公司和2001年成立的珠海信禾西部公共汽车有限公司合并而成。现时是
  • 国立清华大学物理系坐标:24°47′39″N 120°59′32″E / 24.79417°N 120.99222°E / 24.79417; 120.99222国立清华大学物理系最初成立于1926年,为清华大学早期设立的院系之一。1955年国立清华