迈克尔·拉宾 (科学家)

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

相关

  • 法兰西王国法兰西王国(法语:Royaume de France)为西欧法国的一个君主制国家,存在时间为987年至1792年,并在1814年至1815年及1815年至1848年间复辟。987年,法兰西公爵雨果·卡佩被贵族推举为
  • 汉斯·奥斯特汉斯·克海斯提安·奥斯特(丹麦语:Hans Christian Ørsted,1777年8月14日-1851年3月9日),丹麦物理学家、化学家和文学家。在物理学领域,他首先发现载流导线的电流会产生作用力于磁
  • 居民点人类聚居地(英语:Human settlement)。以美国地质调查局的定义来看的话,它是一个有人口聚居的地方或地区(视人口普查结果而定),并根据经纬度分析某一范围聚集或散落的建筑物与该地长
  • 利川市利川市在中国湖北省西南部,清江上游,邻接重庆市,是隶属于恩施土家族苗族自治州的县级市。总面积4603平方千米,总人口94万人(2016年末)。境内主要居住民族除了汉族以外,还有土家族、
  • 电阻温度计电阻温度计,也称为电阻温度探测器(RTDs),是一种使用已知电阻随温度变化特性的材料所制成温度传感器。因为他们几乎无一例外地由铂制造而成,所以他们通常被称为铂电阻温度计。在许
  • 2005年8月逝世人物列表2005年逝世人物列表:1月 - 2月 - 3月 - 4月 - 5月 - 6月 - 7月 - 8月 - 9月 - 10月 - 11月 - 12月下面是2005年12月逝世的知名人士列表:
  • 安德烈·拉勒曼德安德烈·拉勒曼德(法语:André Lallemand,1904年9月29日-1978年3月24日),法国天文学家,巴黎天体物理研究所所长。拉勒曼德曾为天文研究所用的光电倍增管以及“电子望远镜”(或称拉勒
  • 基于规则集的访问控制以规则集为基础的访问控制,(英语:Rule Set Based Access Control),是资讯安全领域中,一种开放源码的访问控制机制,用于Linux核心,其会依据系统安全策略的选择,提供所能允许的权限。
  • 贝雷塔8000半自动手枪贝雷塔8000“美洲狮”(英语:Beretta 8000 Cougar)是一系列由意大利枪械制造商贝雷塔所研制及生产的半自动手枪。贝雷塔8000系列手枪在1994年首次在市场上推出,作为全尺寸的贝雷
  • 方信翔方信翔(1990年3月15日-2016年5月1日)是台湾一位身心障碍者权益自我倡议者。出生罹患先天性罕见疾病“脊髓性肌肉萎缩症”,不良于行。但其性格刻苦学习,克服诸多学习障碍与困难。