Michael Rabin

Michael Rabin Bild in der Infobox. Biografie
Geburt 1 st September Jahre 1931
Breslau
Name in der Muttersprache Michael Oser Rabin
Staatsangehörigkeit israelisch
Ausbildung Hebräische Universität Jerusalem
Hebräische Reali-Schule ( in )
Princeton University
Aktivitäten Informatiker , Mathematiker , Kryptograf , Pädagoge , Universitätsprofessor
Papa Israel Abraham Rabin ( d )
Geschwister Miriam Ben-Peretz ( en )
Chaim Rabin ( en )
Andere Informationen
Arbeitete für Harvard University , New York University , California Institute of Technology , Technion , Massachusetts Institute of Technology , Columbia University , University of California in Berkeley , Eidgenössisches Technologieinstitut Zürich
Feld Informationswissenschaft ( in )
Mitglied von Amerikanische Akademie der Künste und Wissenschaften
Amerikanische Philosophische Gesellschaft
Akademie der Wissenschaften
Israelische Akademie der Wissenschaften und Briefe
Amerikanische Akademie der Wissenschaften (1984)
Royal Society (2007)
Supervisor Alonzo Kirche
Auszeichnungen Turing-Preis (1976)

Michael Oser Rabin , geboren am1 st September Jahre 1931in Breslau in Deutschland , jetzt Wrocław in Polen ) ist ein israelischer Informatiker und Logiker . Er erhielt den Turing-Preis , die renommierteste Auszeichnung in der Informatik.

Biografie

Rabin wurde als Sohn eines Rabbiners geboren . Er erhielt eine Master-Abschluss von der Hebrew University of Jerusalem in 1953 und einem Doktortitel von der Universität Princeton in 1956 .

Das Zitat für den Turing-Preis, das 1976 gemeinsam an Michael Rabin und Dana Scott für einen Artikel aus dem Jahr 1959 verliehen wurde , besagt, dass der Preis verliehen wurde:

„In ihrem Artikel„  Endliche Automaten und ihr Entscheidungsproblem  “wird die Idee nicht deterministischer endlicher Automaten vorgestellt, die sich als ein Konzept von enormem Wert erwiesen hat. Ihr klassischer Artikel war eine ständige Inspirationsquelle für die folgenden Arbeiten in diesem Bereich. ""

Nicht deterministische Maschinen sind zu einem Schlüsselbegriff in der Komplexitätstheorie geworden , insbesondere bei der Beschreibung der Komplexitätsklassen P und NP .

Funktioniert

In den Jahren 1957 und 1958 zeigte Rabin, dass verschiedene Probleme theoretischer Gruppen unentscheidbar sind (dies sind die ersten ihrer Art nach denen von Sergei Adian im Jahr 1955).

In 1969 zeigten , dass Rabin zweiter Ordnung monadisch arithmetischen (mit k Nachfolger) entscheidbar ist. Dies ist Rabins Satz über Bäume .

In 1974 zeigte Rabin mit Michel Fischer , dass Presburger Arithmetik super-exponentielle Komplexität hat.

In 1975 wurde Rabin ein Pionier der probabilistischen Algorithmen . Insbesondere erfand er einen randomisierten Algorithmus , den Miller-Rabin-Primalitätstest , der sehr schnell, aber mit einer geringen Fehlerwahrscheinlichkeit bestimmt, ob eine Zahl eine Primzahl ist. Dieser Algorithmus ist für die Implementierung der meisten asymmetrischen Kryptografiealgorithmen wesentlich . Er schrieb auch einen der ersten probabilistischen geometrischen Algorithmen, um die beiden nächsten Punkte zu finden .

In 1979 erfand Rabin das Rabin - Kryptosystem , das die erste asymmetrische Kryptosystem , dessen Sicherheit auf der Schwierigkeit , reduziert der eine ganze Zahl faktorisieren .

In 1981 erfand Rabin die Technik der unbewusste Übertragung , so dass ein Absender eine Nachricht an einen Empfänger zu senden , so dass dieser eine gewisse Wahrscheinlichkeit für das Erlernen der Nachricht hat, während der Sender nichts über den Erfolg des Empfängers kennt..

In 1987 , Rabin und Richard Karp hat eine effizienten Algorithmen , um die bekanntesten erstellt Suche Zeichenfolge , der Rabin-Karp - Algorithmus .

Rabins aktuelle Forschung konzentriert sich auf die Sicherheit von Computersystemen und ist derzeit Professor für den Computer-Lehrstuhl Thomas J. Watson Sr. an der Harvard University und Professor für Informatik an der Hebrew University of Jerusalem .

Auszeichnungen und Anerkennung

Anmerkungen und Referenzen

(fr) Dieser Artikel stammt teilweise oder vollständig aus dem englischen Wikipedia- Artikel "  Michael O. Rabin  " ( siehe Autorenliste ) .
  1. kostenlos Übersetzung von: (en) Zitat des ACM Turing Award .
  2. (in) Michael O. Rabin , "  Entscheidbarkeit von Theorien zweiter Ordnung und Automaten sind unendliche Bäume  " , Bulletin der American Mathematical Society , vol.  74, n o  5,September 1968, p.  1025–1029 ( ISSN  0002-9904 und 1936-881X , online gelesen , abgerufen am 19. September 2018 )
  3. (en) Rajeev Motwani und Prabhakar Raghavan , Randomized Algorithms , Cambridge; New York, Cambridge University Press ( repr.  1997, 2000) ( 1 st ed. 1995), 476  p. ( ISBN 9780521474658 ) , Kap.  9, p.  273    

Siehe auch

Zum Thema passende Artikel

Externe Links