迈克尔·拉宾

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

相关

阿蒙霍特普四世阿蒙霍特普四世（按不同的时间体系估计，去世于前1351年-前1334年之间），后改名埃赫那吞（Akhenaten，亦译做埃赫那顿），古埃及第十八王朝法老。阿蒙霍特普四世是第十八王朝全盛时期的法老
深度学习深度学习（英语：deep learning）是机器学习的分支，是一种以人工神经网络为架构，对数据进行表征学习的算法。深度学习是机器学习中一种基于对数据进行表征学习的算法。观测值（例如一
本地星际云本地星际云也称为本星际云，是太阳系正运行在其中的星际云（大约30光年大小）。太阳系至少在大约44,000年至15万年前进入其中，并且还会继续在里面运行一万至二万年，甚至更久。这个云
篇章分析言谈分析（discourse analysis，简称 DA）是一套广泛应用于语言学、社会学、认知心理学、口语传播等学科的分析方式，讲求在语境中分析口语、书面语言、手语、肢体语言等等不同的语
中文上网官方版软件中文上网官方版软件是中国互联网络信息中心（CNNIC）开发的互联网辅助软件。软件开发单位宣称，该软件作用为体现中文网站域名的重定向，但该软件因被指为属流氓软件而惹来争议。通
王个簃王个.mw-parser-output ruby>rt,.mw-parser-output ruby>rtc{font-feature-settings:"ruby"1}.mw-parser-output ruby.large{font-size:250%}.mw-parser-output ruby.larger
丹增当却丹增当却（1916年－？年），汉名邓奎，曾任行宪第一届国民大会代表，行宪后第一届立法委员。
卡布努尔卡布努尔（Kabnur），是印度马哈拉施特拉邦Kolhapur县的一个城镇。总人口28223（2001年）。该地2001年总人口28223人，其中男性14946人，女性13277人；0—6岁人口3547人，其中男1937人，女1610人
Josep Ferrer BujonsJosep Ferrer Bujons （圣马蒂Maçana ，卢比奥），在1959年5月12日）是加泰罗尼亚加泰罗尼亚语语言学诗人，作家，语言学家，教授的程度。他曾任教语言艺术中学和校正器和编辑器在每周的L
吴静吉吴静吉(1939年5月3日─)，台湾宜兰县壮围乡东港村人，教育心理学学者、作家、演说家、企业管理顾问、表演艺术工作者。美国明尼苏达大学教育心理学博士、国立政治大学教育学系文