迈克尔·O·拉宾希伯来语מִיכָאֵל אֹשֶׁר רַבִּין‎,英语:Michael Oser Rabin,1931年9月1日 )是一名以色列计算机科学家,1976年图灵奖得主。

Quick Facts 迈克尔·拉宾Michael Oser Rabin, 出生 ...
迈克尔·拉宾
Michael Oser Rabin
Thumb
出生 (1931-09-01) 1931年9月1日93岁)
德国魏玛共和国布雷斯劳(今波兰弗罗茨瓦夫
知名于米勒-拉宾素数检验
拉宾密码系统英语Rabin cryptosystem
不经意传输
拉宾-卡普字符串搜索算法
非确定有限状态自动机
随机化算法
奖项图灵奖 (1976)
Paris Kanellakis Award英语Paris Kanellakis Award (2003)
以色列奖
艾迈特艺术科学与文化奖英语EMET Prize
哈维奖
丹·大卫奖
戴克斯特拉奖英语Dijkstra Prize
IEEE计算机协会查尔斯-巴贝奇奖英语International Parallel and Distributed Processing Symposium#IEEE Computer Society Charles Babbage Award
科学生涯
研究领域计算机科学
机构哈佛大学
希伯来大学
哥伦比亚大学
Close

生平

拉宾出生于德国布雷斯劳二战后成为波兰弗罗茨瓦夫),父亲是一个拉比

1953年,他获得希伯来大学理学硕士,1956年获普林斯顿大学博士学位

1959年,拉宾和达纳·斯科特共同发表了“有限自动机与其判定性问题”(Finite Automata and Their Decision Problems)的论文,提出了非确定自动机的观点。他们也因此获得了1976年的图灵奖,并做“计算机复杂性”(Complexity of Computations)的演讲。图灵奖的引文是:

非确定自动机已经成为计算复杂度理论中的一个重要概念,特别是在描述P与NP问题复杂度类时。

1969年,拉宾证明N successors的二阶逻辑可判定的[2]证明的关键部分暗示了奇偶游戏英语Parity game的确定性。1975年,拉宾发明了米勒-拉宾检验,这是一个相当快速的随机化算法(有较小的可能性错误),用于判断一个大数是否是素数[3][4] 快速素数检验是目前大部分公钥密码体系的关键。1979年,拉宾发明了第一个非对称密码系统——拉宾密码系统英语Rabin cryptosystem。它的安全性被证明和整数因式分解的复杂度相同。[5]1981年,拉宾提出了不经意传输技术。[6] 1987年,拉宾和理查德·卡普提出了一个著名的字符串搜索算法——拉宾-卡普算法[7]

参考

外部链接

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.