亚洲国产区中文,国产精品91高清,亚洲精品中文字幕久久久久,亚洲欧美另类久久久精品能播放

簡介

拉賓出生于德國布雷斯勞（二戰(zhàn)后成為波蘭弗羅茨瓦夫），父親是一個拉比。

1953年，他獲得希伯來大學(xué)的理學(xué)碩士，1956年獲普林斯頓大學(xué)博士學(xué)位。

1959年，拉賓和達(dá)納·斯科特共同發(fā)表了“有限自動機(jī)與其判定性問題”（ Finite Automata and Their Decision Problems ）的論文，提出了非確定自動機(jī)的觀點。他們也因此獲得了1976年的圖靈獎，并做“計算機(jī)復(fù)雜性”（ Complexity of Computations ）的演講。圖靈獎的引文是：

“ 因他們的合著論文“有限自動機(jī)與其判定性問題”。論文中引入了非確定自動機(jī)的概念，被證明是（計算理論科學(xué)研究中的）一個非常重要的概念。拉賓和斯科特的這篇經(jīng)典論文成為了這個領(lǐng)域后續(xù)研究的源泉。 ”

非確定自動機(jī)已經(jīng)成為計算復(fù)雜度理論中的一個重要概念，特別是在描述P與問題的復(fù)雜度類時。

1969年，拉賓證明N successors的二階邏輯是可判定的。 證明的關(guān)鍵部分暗示了parity game的確定性。1975年，拉賓發(fā)明了米勒-拉賓檢驗，這是一個相當(dāng)快速的隨機(jī)算法（有較小的可能性錯誤），用于判斷一個大數(shù)是否是素數(shù)。 快速素數(shù)檢驗是目前大部分公鑰密碼體系的關(guān)鍵。1979年，拉賓發(fā)明了第一個非對稱密碼系統(tǒng)——拉賓密碼系統(tǒng)。它的安全性被證明和整數(shù)因式分解的復(fù)雜度相同。 1981年，拉賓提出了不經(jīng)意傳輸（oblivious transfer）技術(shù)。 1987年，拉賓和理查德·卡普提出了一個著名的字符串搜索算法——拉賓-卡普算法。

免責(zé)聲明：以上內(nèi)容版權(quán)歸原作者所有，如有侵犯您的原創(chuàng)版權(quán)請告知，我們將盡快刪除相關(guān)內(nèi)容。感謝每一位辛勤著寫的作者，感謝每一位的分享。