计算的美丽–1976年图灵奖获得者Michael Rabin

Sina WeiboBaiduLinkedInQQGoogle+RedditEvernote分享




Michael Oser Rabin (1931–)

图灵奖获得时间:

1976年。 第十一位图灵奖(1976年)获得者。

图灵奖引用(Turing Award Citation) :

For their joint paper “Finite Automata and Their Decision Problem,” which introduced the idea of nondeterministic machines, which has proved to be an enormously valuable concept. Their (Scott & Rabin) classic paper has been a continuous source of inspiration for subsequent work in this field.

【笔者译:】

“( 授 予 Michael O. Rabin图 灵 奖 以 表 彰 其 )( (与Dana Steward Scott合作撰写的研究论文)有限自动机与其判定性问题。在该研究论文中,提出了非确定性(自动机)机器的观点。(在计算理论科学研究中,)非确定性被证明是一个非常重要的概念。Rabin和Scott的这篇经典文章成为这个领域后续研究的基石。”

【笔者注:】

Rabin著名论文可参见:有限自动机与其判定性问题(PDF 格式)

自动机理论介绍:

http://en.wikipedia.org/wiki/Automata_theory

http://en.wikipedia.org/wiki/Finite_state_machine

Simulation of an NFA by a DFA

关于DFA和计算理论的书籍:

http://books.google.com/books?q=Finite+Automata+and+Their+Decision+Problem&oi=print

http://books.google.com/books?q=DFA+theory+of+computing&oi=print

Comp.Theory FAQ:

http://www.cs.uwaterloo.ca/~alopez-o/comp-faq/faq.html

Book of “Introduction to the Theory of Computation” from MIT:

http://www-math.mit.edu/~sipser/book.html

Turing Award Lecture(图灵奖演讲文章):

Logic and Programming Languages. Commun. ACM 20(9): 634-641(1977)

Michael O. Rabin 简介:

Michael O. Rabin Wiki: http://en.wikipedia.org/wiki/Michael_O._Rabin

Michael O. Rabin在哈佛大学网站上的个人简历:

http://www.deas.harvard.edu/directory/professionalbio/index.html?id=2542

Answer.com关于Michael O. Rabin的介绍: http://www.answers.com/topic/michael-o-rabin

Michael Oser Rabin生于1931年于Breslau,德国的一个犹太人家庭。Beslau在二战后属于波兰。

Michael在1953年从Hebrew University of Jerusalem( www.huji.ac.il ) 获得其硕士学位;1956年从普林斯顿大学获得其博士学位。

除了其与Danna Scott合作的关于非确定性自动机理论并获得了图灵奖之外,Michael的学术生涯非常丰富,在1975年,Rabin发明了Miller-Rabin primality test; 1979年,发明了Rabin Crytosystem; 1981年发明了Oblivious Transfer; 1987年发明了Rabin-Karp String Search Algorithm。

目前,Rabin是哈佛大学计算机系的教授。可参见:

www.cs.harvard.edu 。 另外,Rabin也是希伯来大学计算机系(www.cs.huji.ac.il ) 的教授。可参见:

http://www.cs.huji.ac.il/people/index.php?id=1&in=t

http://www.cs.huji.ac.il/images/personal_info.gif

关于Micahel的其他著名的算法,可参见:

  • Miller-Rabin primality test
  • Rabin cryptosystem
  • Rabin-Karp string search algorithm
  • Oblivious transfer
  • Michael O. Rabin照片:
    http://images.google.com/images?q=Michael+O.+Rabin&hl=en&lr=&sa=N&tab=wi&sourceid=tipimg
     
     
     

    (没有打分)

    雁过留声

    Comments are closed.