Michael Rabin

Michael Rabin Bilde i infoboks. Biografi
Fødsel 1 st September 1931
Wrocław
Navn på morsmål Michael Oser Rabin
Nasjonalitet Israelsk
Opplæring Hebrew University of Jerusalem
Hebrew Reali School ( in )
Princeton University
Aktiviteter Datavitenskapsmann , matematiker , kryptograf , pedagog , universitetsprofessor
Pappa Israel Abraham Rabin ( d )
Søsken Miriam Ben-Peretz ( en )
Chaim Rabin ( en )
Annen informasjon
Jobbet for Harvard University , New York University , California Institute of Technology , Technion , Massachusetts Institute of Technology , Columbia University , University of California at Berkeley , Swiss Federal Institute of Technology Zurich
Felt Informasjonsvitenskap ( in )
Medlem av American Academy of Arts and Sciences
American Philosophical Society
Academy of Sciences
Israeli Academy of Sciences and Letters
American Academy of Sciences (1984)
Royal Society (2007)
Veileder Alonzo kirke
Utmerkelser Turing-prisen (1976)

Michael Oser Rabin , født den1 st September 1931i Breslau i Tyskland , nå Wrocław i Polen ) er en israelsk informatiker og logiker . Han mottok Turing-prisen , den mest prestisjefylte prisen innen informatikk.

Biografi

Rabin ble født som sønn av en rabbin . Han oppnådde en mastergrad fra det hebraiske universitetet i Jerusalem i 1953 og en doktorgrad fra Princeton University i 1956 .

Sitatet for Turing-prisen, tildelt i 1976 sammen til Michael Rabin og Dana Scott for en artikkel skrevet i 1959 , sier at prisen ble gitt:

"For artikkelen"  Finite Automata and Their Decision Problem  "som presenterer ideen om ikke-deterministisk Finite Automata, som har vist seg å være et begrep av enorm verdi. Deres klassiske artikkel var en kontinuerlig inspirasjonskilde for arbeidet som fulgte på dette området. "

Ikke-deterministiske maskiner har blitt et nøkkelbegrep i kompleksitetsteori , særlig med beskrivelsen av kompleksitetsklassene P og NP .

Virker

I 1957 og 1958 , Rabin vist at ulike problemer med teori grupper er undecidable (disse er den første i sitt slag etter at de av Sergei Adian i 1955).

I 1969 demonstrerte Rabin at andreordens monadiske aritmetikk (med k etterfølgere) kan avgjøres. Dette er Rabins setning på trær .

I 1974 demonstrerte Rabin med Michel Fischer at Presburgers aritmetikk har supereksponentiell kompleksitet.

I 1975 var Rabin en pioner innen sannsynlighetsalgoritmer . Spesielt oppfant han en randomisert algoritme , Miller-Rabin primality test , som avgjør veldig raskt, men med liten sannsynlighet for feil, om et tall er et primtall. Denne algoritmen er viktig for implementeringen av de fleste asymmetriske kryptografi- algoritmer . Han skrev også en av de første sannsynlige geometriske algoritmene for å finne de to nærmeste punktene .

I 1979 oppfant Rabin Rabin-kryptosystemet , som er det første asymmetriske kryptosystemet hvis sikkerhet kommer ned på vanskeligheten med å ta et helt tall .

I 1981 oppfant Rabin teknikken med ubevisst overføring , slik at en avsender kunne overføre en melding til en mottaker slik at sistnevnte har en viss sannsynlighet for å lære meldingen, mens avsenderen ikke vet noe om suksessen til mottakeren.

I 1987 , Rabin og Richard Karp , har skapt en effektiv algoritmer den mest kjente søkestrengen av tegn , Rabin-Karp algoritmen .

Rabins nåværende forskning fokuserer på sikkerheten til datasystemer og er for tiden professor i datastol Thomas J. Watson Sr. til Harvard University og professor i informatikk ved Hebrew University of Jerusalem .

Priser og anerkjennelse

Merknader og referanser

(fr) Denne artikkelen er helt eller delvis hentet fra den engelske Wikipedia- artikkelen med tittelen "  Michael O. Rabin  " ( se listen over forfattere ) .
  1. gratis oversettelse av: (no) Sitat av ACM Turing-prisen .
  2. (in) Michael O. Rabin , "  Avgjørbarhet av andreordens teorier og automater er uendelige trær  " , Bulletin of the American Mathematical Society , vol.  74, n o  5,September 1968, s.  1025–1029 ( ISSN  0002-9904 og 1936-881X , lest online , åpnet 19. september 2018 )
  3. (en) Rajeev Motwani og Prabhakar Raghavan , Randomized Algorithms , Cambridge; New York, Cambridge University Press ( repr.  1997, 2000) ( 1 st ed. 1995), 476  s. ( ISBN 9780521474658 ) , kap.  9, s.  273    

Se også

Relaterte artikler

Eksterne linker