Michael Oser Rabin
(nascut el
1931
a
Breslau
,
Alemanya
, avui dia part de
Polonia
) es un notable
cientific de la computacio
i guanyador del
Premi Turing
, el guardo mes prestigios en aquest camp.
Michael Oser Rabin es fill d'un
Rabi
, i va neixer a la ciutat que es coneixia llavors com
Breslau
(que va passar a dir-se Wrocław, despres de la Segona Guerra Mundial). Va rebre el seu grau de
master
en ciencies a la
Universitat Hebrea de Jerusalem
el 1953, i el seu
doctorat
a la
Universitat de Princeton
el
1956
.
[1]
Premi Turing
[
modifica
]
El text en el qual es concedeix el
Premi Turing
de
1976
conjuntament a Rabin i
Dana Scott
per un article escrit el
1959
, afirma que el guardo va ser concedit:
[1]
Pel seu article "Finite Automata and Their Decision Problem" (de l'angles, "Automats Finits i el Problema de la seva Decisibilitat"), que va introduir la idea de les maquines no deterministiques, un concepte enormement valuos, com es provaria mes endavant. El seu classic article ha estat una continua font d'inspiracio per a posteriors treballs en el camp.
[2]
Les maquines no deterministiques s'han convertit en un concepte clau en la teoria de la
complexitat computacional
, particularment per descriure les classes de complexitat P i NP.
Altres invents
[
modifica
]
El
1975
, Rabin tambe va inventar el
Test de primalitat de Miller-Rabin
, un algorisme aleatori que determina molt rapidament (pero amb una probabilitat d'error minuscula) si un nombre es
primer
o no. Les proves de primalitat rapides son fonamentals per a la correcta implementacio de molts algorismes de
criptografia de clau publica
.
[3]
[4]
El
1979
, Rabin va inventar el criptosistema Rabin, que va ser el primer criptosistema asimetric la seguretat del qual es va poder provar equivalent a la
factoritzacio d'enters
, un problema
intractable
computacionalment.
[5]
El
1981
, Rabin va inventar la tecnica coneguda com a
transferencia inconscient
, que permet a l'emissor transmetre un missatge que el receptor te una probabilitat de captar entre 0 i 1, mentre que l'emissor es inconscient de l'exit de la transmissio.
[6]
El
1987
, Rabin, juntament amb
Richard Karp
, va crear un dels algorismes de cerca de cadenes eficients mes coneguts, l'algorisme de cerca de cadenes Rabin-Karp, conegut per l'us d'un hash giratori.
[7]
El treball mes recent de Rabin es concentra en la seguretat computacional. Actualment ocupa la placa de professor
Thomas J. Watson
Sr. de
Ciencies de la Computacio
a la
Universitat Harvard
sent tambe professor a la
Universitat Hebrea de Jerusalem
.
[1]
- ↑
1,0
1,1
1,2
Shasha, Dennis
,
"An Interview with Michael O. Rabin"
,
Communications of the ACM
, Vol. 53 No. 2, Pages 37-42, February 2010.
- ↑
Scott
, Dana;
Rabin
, Michael
≪
Finite Automata and Their Decision Problems
≫.
IBM Journal of Research and Development
, 3, 2, 1959, pag. 114?125.
DOI
:
10.1147/rd.32.0114
.
- ↑
Rabin, MO (1976). "Probabilistic algorithms".
Algorithms and Complexity, Proc. Symp
- ↑
Rabin
, MO ≪Probabilistic algorithm for testing primality≫.
Journal of Number Theory
, 12, 1, 1980, pag. 128?138.
DOI
:
10.1016/0022-314X(80)90084-0
.
- ↑
Rabin
, MO ≪
Digitalized signatures and public-key functions as intractable as factorization
≫.
MIT Laboratory of Computer Science Technical Report
, gener 1979 [Consulta: 15 marc 2007].
- ↑
Rabin
, Michael O.
How to exchange secrets by oblivious transfer (Technical Report TR-81)
(PDF). Harvard University, 1981.
- ↑
Karp
, RM; Rabin, MO ≪
Efficient randomized pattern-matching algorithms
≫.
IBM Journal of Research and Development
, 31, 2, marc 1987, pag. 249?260.
DOI
:
10.1147/rd.312.0249
[Consulta: 15 marc 2007].
Enllacos externs
[
modifica
]