Nacimiento |
1 st de septiembre de 1931 Breslavia |
---|---|
Nombre en idioma nativo | Michael Oser Rabin |
Nacionalidad | israelí |
Capacitación |
Universidad Hebrea de Jerusalén Escuela Hebrea Reali ( en ) Universidad de Princeton |
Ocupaciones | Científico informático , matemático , criptógrafo , educador , profesor universitario |
Padre | Israel Abraham Rabin ( d ) |
Hermanos |
Miriam Ben-Peretz ( en ) Chaim Rabin ( en ) |
Trabajé para | Universidad de Harvard , Universidad de Nueva York , Instituto de Tecnología de California , Technion , Instituto de Tecnología de Massachusetts , Universidad de Columbia , Universidad de California en Berkeley , Instituto Federal Suizo de Tecnología de Zúrich |
---|---|
Campo | Ciencias de la información ( en ) |
Miembro de |
Academia Estadounidense de Artes y Ciencias Sociedad Filosófica Estadounidense Academia de Ciencias Academia Israelí de Ciencias y Letras Academia Estadounidense de Ciencias (1984) Real Sociedad (2007) |
Director de tesis | Iglesia de Alonzo |
Premios |
Premio Turing (1976) |
Michael Oser Rabin , nacido el1 st de septiembre de 1931en Breslau en Alemania , ahora Wrocław en Polonia ) es un científico informático y lógico israelí . Recibió el Premio Turing , el premio más prestigioso en informática.
Rabin nació hijo de un rabino . Obtuvo una maestría de la Universidad Hebrea de Jerusalén en 1953 y un doctorado de la Universidad de Princeton en 1956 .
La mención para el Premio Turing, otorgado en 1976 conjuntamente a Michael Rabin y Dana Scott por un artículo escrito en 1959 , afirma que el premio fue otorgado:
“Por su artículo“ Autómatas finitos y su problema de decisión ”presentando la idea de autómatas finitos no deterministas que ha demostrado ser un concepto de enorme valor. Su artículo clásico fue una fuente continua de inspiración para el trabajo que siguió en esta área. "
Las máquinas no deterministas se han convertido en un concepto clave en la teoría de la complejidad , en particular con la descripción de las clases de complejidad P y NP .
En 1957 y 1958 , Rabin demostró que varios problemas de los grupos teóricos son indecidibles (estos son los primeros de su tipo después de los de Sergei Adian en 1955).
En 1969 , Rabin demostró que la aritmética monádica de segundo orden (con k sucesores) es decidible. Este es el teorema de Rabin sobre árboles .
En 1974 , Rabin demostró con Michel Fischer que la aritmética de Presburger tiene una complejidad superexponencial.
En 1975 , Rabin fue un pionero de los algoritmos probabilísticos . En particular, inventó un algoritmo aleatorio , la prueba de primalidad de Miller-Rabin , que determina muy rápidamente, pero con una mínima probabilidad de error, si un número es un número primo. Este algoritmo es esencial para la implementación de la mayoría de los algoritmos de criptografía asimétrica . También escribió uno de los primeros algoritmos geométricos probabilísticos para encontrar los dos puntos más cercanos .
En 1979 , Rabin inventó el criptosistema Rabin , que es el primer criptosistema asimétrico cuya seguridad se reduce a la dificultad de factorizar un entero .
En 1981 , Rabin inventó la técnica de la transferencia inconsciente , que permite que un remitente transmita un mensaje a un receptor para que este último tenga alguna probabilidad de aprender el mensaje, mientras que el remitente no sabe nada sobre el éxito del receptor.
En 1987 , Rabin y Richard Karp , crearon un algoritmo eficiente de la cadena de búsqueda de caracteres más conocida , el algoritmo Rabin-Karp .
La investigación actual de Rabin se centra en la seguridad de los sistemas informáticos y actualmente es profesor de la cátedra de informática Thomas J. Watson Sr. en la Universidad de Harvard y profesor de informática en la Universidad Hebrea de Jerusalén .