Michael Oser Rabin
Michael Oser Rabin (hebreu: מִיכָאֵל עוזר רַבִּין) (Breslau, 1 de setembre de 1931 - Jerusalem, 14 d'abril de 2026) va ser un científic de la computació i guanyador del premi Turing.
Biografia
[modifica]Michael Oser Rabin era fill d'un rabí i va néixer a la ciutat que es coneixia llavors com a Breslau (que va passar a dir-se Wrocław, després de la Segona Guerra Mundial). Va rebre el seu grau de màster en ciències 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 guardó va ser concedit:[1]
Pel seu article "Finite Automata and Their Decision Problem" (de l'anglès, "Autòmats Finits i el Problema de la seva Decisibilitat"), que va introduir la idea de les màquines no determinístiques, un concepte enormement valuós, com es provaria més endavant. El seu clàssic article ha estat una contínua font d'inspiració per a posteriors treballs en el camp.[2]
Les màquines no determinístiques 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 també va inventar el Test de primalitat de Miller-Rabin, un algorisme aleatori que determina molt ràpidament (però amb una probabilitat d'error minúscula) si un nombre és primer o no. Les proves de primalitat ràpides són fonamentals per a la correcta implementació de molts algorismes de criptografia de clau pública.[3][4]
El 1979, Rabin va inventar el criptosistema Rabin, que va ser el primer criptosistema asimètric la seguretat del qual es va poder provar equivalent a la factorització d'enters, un problema intractable computacionalment.[5]
El 1981, Rabin va inventar la tècnica coneguda com a transferència inconscient, que permet a l'emissor transmetre un missatge que el receptor té una probabilitat de captar entre 0 i 1, mentre que l'emissor és inconscient de l'èxit de la transmissió.[6]
El 1987, Rabin, juntament amb Richard Karp, va crear un dels algorismes de cerca de cadenes eficients més coneguts, l'algorisme de cerca de cadenes Rabin-Karp, conegut per l'ús d'un hash giratori.[7]
El treball més recent de Rabin es concentra en la seguretat computacional. Actualment ocupa la plaça de professor Thomas J. Watson de ciències de la computació a la Universitat Harvard essent també professor a la Universitat Hebrea de Jerusalem.[1]
Referències
[modifica]- 1 2 3 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, p. 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, p. 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, 1-1979 [Consulta: 15 març 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, 3-1987, p. 249–260. DOI: 10.1147/rd.312.0249 [Consulta: 15 març 2007].
Enllaços externs
[modifica]
- Curta descripció en el Saló de la Fama de les Ciències de la Informació, Universitat de Pittsburgh
- Raó per la qual li va ser concedit el Premi Turing de l'ACM
- Cites d'algunes classes del Professor Rabin
Guardonats amb el Premi Turing |
|---|
Perlis (1966) • Wilkes (1967) • Hamming (1968) • Minsky (1969) • Wilkinson (1970) • McCarthy (1971) • Dijkstra (1972) • Bachman (1973) • Knuth (1974) • Newell / Simon (1975) • Rabin / Scott (1976) • Backus (1977) • Floyd (1978) • Iverson (1979) • Hoare (1980) • Codd (1981) • Cook (1982) • Thompson / Ritchie (1983) • Wirth (1984) • Karp (1985) • Hopcroft / Tarjan (1986) • Cocke (1987) • Sutherland (1988) • Kahan (1989) • Corbató (1990) • Milner (1991) • Lampson (1992) • Hartmanis / Stearns (1993) • Feigenbaum / Reddy (1994) • Blum (1995) • Pnueli (1996) • Engelbart (1997) • Gray (1998) • Brooks (1999) • Yao (2000) • Dahl / Nygaard (2001) • Rivest / Shamir / Adleman (2002) • Kay (2003) • Cerf / Kahn (2004) • Naur (2005) • Allen (2006) • Clarke / Emerson / Sifakis (2007) • Liskov (2008) • Thacker (2009) • Valiant (2010) • Pearl (2011) • Micali / Goldwasser (2012) • Lamport (2013) • Stonebraker (2014) • Hellman / Diffie (2015) • Berners-Lee (2016) • Hennessy / Patterson (2017) • Bengio / Hinton / LeCun (2018) • Hanrahan / Catmull (2019) • Aho / Ullman (2020) • Dongarra (2021) • Metcalfe (2022) • Wigderson (2023) • Barto / Sutton (2024) |
- Premiats amb el Premi Turing
- Jueus israelians
- Lògics
- Membres de l'Acadèmia Nacional de Ciències dels Estats Units
- Alumnes de la Universitat de Princeton
- Alumnes de la Universitat Hebrea de Jerusalem
- Doctors honoris causa per l'Institut Weizmann
- Científics israelians
- Científics de Breslau
- Jueus polonesos
- Filòsofs jueus
- Filòsofs polonesos
- Científics jueus
- Filòsofs asiàtics
- Naixements del 1931
- Morts el 2026
- Morts a Jerusalem
- Filòsofs nascuts al segle XX
- Filòsofs morts al segle XXI