stringtranslate.com

Zvi Galil

Zvi Galil ( hebreo : צבי גליל ; nacido el 26 de junio de 1947) es un informático y matemático israelí-estadounidense . Se desempeñó como decano de la Escuela de Ingeniería de la Universidad de Columbia y como presidente de la Universidad de Tel Aviv de 2007 a 2009. De 2010 a 2019, fue decano de la Facultad de Informática del Instituto Tecnológico de Georgia . [3]

Sus intereses de investigación incluyen el diseño y análisis de algoritmos , la complejidad computacional y la criptografía . Se le atribuye la creación de los términos stringología y esparsificación. [4] [5] Ha publicado más de 200 artículos científicos [6] y figura como investigador altamente citado por el ISI . [7]

Vida temprana y educación

Galil nació en Tel Aviv, en el Mandato Británico de Palestina , en 1947. Completó su licenciatura (1970) y su maestría (1971) en matemáticas aplicadas , ambas con honores , en la Universidad de Tel Aviv . En 1975, obtuvo su doctorado en informática en la Universidad de Cornell bajo la supervisión del profesor de informática de Cornell, John Hopcroft . [1] Luego pasó un año trabajando como investigador postdoctoral en el Centro de Investigación Thomas J. Watson de IBM en Yorktown Heights, Nueva York . [8]

Carrera

Galil en Georgia Tech en diciembre de 2016

Desde 1976 hasta 1995, trabajó en el departamento de informática de la Universidad de Tel Aviv , donde fue presidente desde 1979 hasta 1982. En 1982, se unió a la facultad de la Universidad de Columbia , donde fue presidente del departamento de informática desde 1989 hasta 1994. [2] [8] De 1995 a 2007, se desempeñó como decano de la Escuela de Ingeniería y Ciencias Aplicadas de la Fundación Fu de la Universidad de Columbia. [9] En este puesto, supervisó el nombramiento de la escuela en honor al empresario chino ZY Fu después de que se hiciera una gran donación en su nombre. [10] En Columbia, fue nombrado profesor Julian Clarence Levi de Métodos Matemáticos y Ciencias de la Computación en 1987, y decano de Ingeniería Morris y Alma A. Schapiro en 1995. [2]

En 2007, Galil sucedió a Itamar Rabinovich como presidente de la Universidad de Tel Aviv. [11] En 1009, renunció y regresó a la facultad, y fue sucedido por Joseph Klafter . [12] [13] Fue nombrado decano de la facultad de informática de Georgia Tech el 9 de abril de 2010. [3] En Georgia Tech, junto con el fundador de Udacity, Sebastian Thrun , Galil concibió el programa de Maestría en Ciencias de la Computación en línea de la facultad de informática (OMSCS), y dirigió la creación del programa por parte de la facultad. [14] OMSCS se convirtió en el programa de maestría en línea en ciencias de la computación más grande de los Estados Unidos. [15] OMSCS ha aparecido en cientos de artículos, incluido un artículo de portada de 2013 en The New York Times y entrevistas de 2021 en The Wall Street Journal y Forbes . [14] [16] [17] Inside Higher Education señaló que OMSCS "sugiere que las instituciones pueden ofrecer con éxito títulos de alta calidad y bajo costo a los estudiantes a gran escala". [18] The Chronicle of Higher Education señaló que OMSCS "puede tener la mejor oportunidad de cambiar lo que los estudiantes pagan por un título tradicional". [19] Un artículo de Forbes de 2023 , titulado "El mejor programa de grado de la historia", afirmó que OMSCS "es, en casi cualquier medida, el programa de grado más exitoso de la historia". [20] Galil renunció como decano y regresó a un puesto regular en la facultad en junio de 2019. [21] [22] Ahora se desempeña como presidente de la Cátedra Frederick G. Storey en Informática y asesor ejecutivo de programas en línea en Georgia Tech.

Servicio profesional

En 1982, Galil fundó el Día de la Teoría de la Universidad de Columbia y organizó el evento durante los primeros 15 años. Todavía existe como el Día de la Teoría del Área de Nueva York. [23] De 1983 a 1987, Galil se desempeñó como presidente de ACM SIGACT , una organización que promueve la investigación en ciencias de la computación teórica . [24] Se desempeñó como editor en jefe de SIAM Journal on Computing de 1991 a 1997 y editor en jefe de Journal of Algorithms de 1988 a 2003.

Investigación

La investigación de Galil se centra en las áreas de algoritmos , en particular algoritmos de cadenas y de grafos , complejidad y criptografía . También ha realizado investigaciones en diseño experimental con Jack Kiefer .

Los algoritmos en tiempo real de Galil son los más rápidos posibles para la comparación de cadenas y el reconocimiento de palíndromos, y funcionan incluso en el modelo informático más básico, la máquina de Turing de múltiples cintas . En términos más generales, formuló una condición de "predictibilidad" que permite que cualquier algoritmo en línea que cumpla con las normas se convierta en un algoritmo en tiempo real. [25] [26] Con Joel Seiferas, Galil mejoró los algoritmos óptimos en el tiempo para que también fueran óptimos en el espacio (espacio logarítmico). [27]

Galil trabajó con Dany Breslauer para diseñar un algoritmo paralelo de trabajo lineal O(loglogn) para la comparación de cadenas, [28] y más tarde demostraron que tenía la mejor complejidad temporal posible entre los algoritmos de trabajo lineal. [29] Con otros científicos informáticos, diseñó un algoritmo de búsqueda aleatoria de trabajo lineal de tiempo constante para usar cuando se proporciona el preprocesamiento de patrones. [30]

Con sus estudiantes, Galil diseñó más de una docena de algoritmos actualmente más rápidos para correspondencia de cadenas exacta o aproximada, secuencial o paralela, unidimensional o multidimensional.

Galil trabajó con otros científicos informáticos para desarrollar varios de los algoritmos de gráficos más rápidos en la actualidad. Algunos ejemplos incluyen: correspondencia ponderada máxima; [31] isomorfismo de gráficos trivalente; [32] y árboles de expansión de peso mínimo. [33]

Con sus estudiantes, Galil ideó una técnica que llamó "esparsificación" [34] y un método que llamó "programación dinámica dispersa". [35] La primera se utilizó para acelerar los algoritmos de gráficos dinámicos . El segundo se utilizó para acelerar los cálculos de varias distancias de edición entre cadenas.

En 1979, junto con Ofer Gabber , Galil resolvió el problema previamente abierto de construir una familia de gráficos expansores con una relación de expansión explícita, [36] útil en el diseño de algoritmos de gráficos rápidos.

Premios y honores

En 1995, Galil fue incluido como miembro de la Association for Computing Machinery por "contribuciones fundamentales al diseño y análisis de algoritmos y servicio sobresaliente a la comunidad de ciencias de la computación teórica", [37] y en 2004, fue elegido miembro de la Academia Nacional de Ingeniería por "contribuciones al diseño y análisis de algoritmos y por liderazgo en ciencias de la computación e ingeniería". [38] [39]

En 2005, fue seleccionado como miembro de la Academia Estadounidense de las Artes y las Ciencias . [40]

En 2008, la Universidad de Columbia estableció el premio Zvi Galil a la vida estudiantil. [41] En 2009, la Sociedad de Graduados de Columbia le otorgó el Premio al Gran Maestro. [42]

En 2012, la Universidad de Waterloo le otorgó a Galil un doctorado honorario en matemáticas por sus "contribuciones fundamentales en las áreas de algoritmos de gráficos y correspondencia de cadenas". [43] En 2020, Academic Influence incluyó a Galil en la lista de los 10 científicos informáticos más influyentes de la última década, y el consejo asesor de la Facultad de Informática de Georgia Tech recaudó más de 2 millones de dólares de más de 130 donantes para establecer una cátedra financiada con el nombre de Galil. [44] [45]

Referencias

  1. ^ abc Zvi Galil en el Proyecto de Genealogía Matemática
  2. ^ abcdEppstein , David ; Italiano, Giuseppe F. (marzo de 1999). "PREFACIO: Festschrift de Zvi Galil". Revista de Complejidad . 15 (1): 1–3. doi : 10.1006/jcom.1998.0492 .
  3. ^ ab "El instituto nombra al próximo decano de la Facultad de Informática" (Comunicado de prensa). Instituto Tecnológico de Georgia . 2010-04-09 . Consultado el 2010-04-09 .
  4. ^ "Introducción a la cuerdalogía". Club de cuerdalogía de Praga . Universidad Técnica Checa de Praga . Consultado el 14 de mayo de 2012 .
  5. ^ Zvi, Galil; David Eppstein; Giuseppe F. Italiano; Amnon Nissenzweig (septiembre de 1997). "Esparcimiento: una técnica para acelerar algoritmos de grafos dinámicos". Revista de la ACM . 44 (5): 669–696. doi : 10.1145/265910.265914 . S2CID  340999.
  6. ^ "Zvi Galil". Bibliografía informática del DBLP . Proyecto de biblioteca y bibliografía digital . Consultado el 24 de marzo de 2016 .
  7. ^ "Investigadores altamente citados del ISI versión 1.1: Zvi Galil". ISI Web of Knowledge . Consultado el 27 de junio de 2011 .
  8. ^ ab "Zvi Galil nombrado decano de la Facultad de Ingeniería de Columbia" (Comunicado de prensa). Universidad de Columbia. 14 de julio de 1995. Consultado el 5 de junio de 2019 .
  9. ^ McCaughey, Robert (2014). Una palanca lo suficientemente larga: Una historia de la Escuela de Ingeniería y Ciencias Aplicadas de Columbia desde 1864. Columbia University Press. p. 240. ISBN 9780231166881.
  10. ^ Arenson, Karen W. (1 de octubre de 1997). "Un magnate chino le da a Columbia 26 millones de dólares". The New York Times . Consultado el 20 de abril de 2010 .
  11. ^ "Experto en informática nominado para la presidencia de la UTA". The Jerusalem Post . 5 de noviembre de 2006.
  12. ^ Basch_Interactive (1980-01-01). "Presidentes de la Universidad de Tel Aviv | Universidad de Tel Aviv | Universidad de Tel Aviv". English.tau.ac.il . Consultado el 18 de febrero de 2020 .
  13. ^ Ilani, Ofri; Kashti, o (2 de julio de 2009). "El presidente de la Universidad de Tel Aviv dimite / Fuentes: Galil fue obligado a dejar el cargo". Haaretz . Consultado el 27 de junio de 2011 .
  14. ^ ab Lewin, Tamar (18 de agosto de 2013). "La maestría es la nueva frontera del estudio en línea". The New York Times . ISSN  0362-4331 . Consultado el 2 de enero de 2023 .
  15. ^ Galil, Zvi. "OMSCS: La revolución se digitalizará". cacm.acm.org . Consultado el 27 de julio de 2020 .
  16. ^ Varadarajan, Tunku (2 de abril de 2021). «Opinión | El hombre que hizo que la universidad en línea funcionara». Wall Street Journal . ISSN  0099-9660 . Consultado el 1 de noviembre de 2021 .
  17. ^ Nietzel, Michael T. "La maestría en línea en ciencias de la computación de Georgia Tech sigue prosperando. Por qué es importante para el futuro de los MOOC". Forbes . Consultado el 25 de marzo de 2022 .
  18. ^ "El análisis muestra que la maestría en línea en informática de Georgia Tech amplió el acceso | Inside Higher Ed". www.insidehighered.com . 20 de marzo de 2018 . Consultado el 25 de marzo de 2022 .
  19. ^ "Lo que el título en línea en Ciencias de la Computación de Georgia Tech significa para los programas de bajo costo". www.chronicle.com . 6 de noviembre de 2014 . Consultado el 25 de marzo de 2022 .
  20. ^ Busteed, Brandon. "El mejor programa de grado de la historia". Forbes . Consultado el 17 de noviembre de 2023 .
  21. ^ "La creciente estatura de la universidad y su impacto global resaltan el legado de Galil". Facultad de Informática de Georgia Tech . 16 de abril de 2019. Consultado el 5 de junio de 2019 .
  22. ^ "Georgia Tech Alumni Magazine, vol. 95 n.º 3, otoño de 2019". Issuu . 11 de octubre de 2019 . Consultado el 21 de abril de 2020 .
  23. ^ "Día de la teoría en el área de Nueva York". www.cs.columbia.edu . Consultado el 3 de junio de 2020 .
  24. ^ "Presentación preliminar". ACM SICACT News . 19 (1). Otoño de 1987.
  25. ^ Galil, Zvi (1 de enero de 1981). "Correspondencia de cadenas en tiempo real". Revista de la ACM . 28 (1): 134–149. doi : 10.1145/322234.322244 . ISSN  0004-5411. S2CID  9164969.
  26. ^ Galil, Zvi (1978-04-01). "Reconocimiento de palíndromos en tiempo real mediante una máquina de Turing multicinta". Journal of Computer and System Sciences . 16 (2): 140–157. doi : 10.1016/0022-0000(78)90042-9 . ISSN  0022-0000.
  27. ^ Galil, Zvi; Seiferas, Joel (1983-06-01). "Correspondencia de cadenas óptima en tiempo y espacio". Journal of Computer and System Sciences . 26 (3): 280–294. doi : 10.1016/0022-0000(83)90002-8 . hdl : 1802/10578 . ISSN  0022-0000.
  28. ^ Breslauer, Dany; Galil, Zvi (1990-12-01). "Un algoritmo de correspondencia de cadenas paralelas en tiempo $O(\log\log n)$ óptimo". Revista SIAM de Computación . 19 (6): 1051–1058. doi :10.1137/0219072. ISSN  0097-5397.
  29. ^ Breslauer, Dany; Galil, Zvi (1992-10-01). "Un límite inferior para la correspondencia de cadenas paralelas". Revista SIAM de Computación . 21 (5): 856–862. doi :10.1137/0221050. ISSN  0097-5397.
  30. ^ Crochemore, Maxime; Galil, Zvi; Gasieniec, Leszek; Park, Kunsoo; Rytter, Wojciech (1997-08-01). "Correspondencia de cadenas paralelas aleatorias en tiempo constante". SIAM Journal on Computing . 26 (4): 950–960. doi :10.1137/S009753979528007X. ISSN  0097-5397.
  31. ^ Galil, Zvi; Micali, Silvio; Gabow, Harold (1986-02-01). "Un algoritmo $O(EV\log V)$ para encontrar una correspondencia ponderada máxima en grafos generales". Revista SIAM de Computación . 15 (1): 120–130. doi :10.1137/0215009. ISSN  0097-5397. S2CID  12854446.
  32. ^ Galil, Zvi; Hoffmann, Christoph M.; Luks, Eugene M.; Schnorr, Claus P.; Weber, Andreas (1 de julio de 1987). "Una prueba de isomorfismo de Las Vegas O(n3log n) determinista y O(n3) para grafos trivalentes". Revista de la ACM . 34 (3): 513–531. doi : 10.1145/28869.28870 . ISSN  0004-5411. S2CID  18031646.
  33. ^ Gabow, Harold N.; Galil, Zvi; Spencer, Thomas; Tarjan, Robert E. (1 de junio de 1986). "Algoritmos eficientes para encontrar árboles de expansión mínimos en grafos dirigidos y no dirigidos". Combinatorica . 6 (2): 109–122. doi :10.1007/BF02579168. ISSN  1439-6912. S2CID  35618095.
  34. ^ Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Nissenzweig, Amnon (1997-09-01). "Esparcimiento: una técnica para acelerar algoritmos de grafos dinámicos". Revista de la ACM . 44 (5): 669–696. doi : 10.1145/265910.265914 . ISSN  0004-5411. S2CID  340999.
  35. ^ Eppstein, David; Galil, Zvi; Giancarlo, Raffaele; Italiano, Giuseppe F. (1 de julio de 1992). "Programación dinámica dispersa I: funciones de costo lineal". Revista de la ACM . 39 (3): 519–545. doi : 10.1145/146637.146650 . ISSN  0004-5411. S2CID  17060840.
  36. ^ Gabber, Ofer; Galil, Zvi (1 de junio de 1981). "Construcciones explícitas de superconcentradores de tamaño lineal". Revista de Ciencias de la Computación y de Sistemas . 22 (3): 407–420. doi : 10.1016/0022-0000(81)90040-4 . ISSN  0022-0000.
  37. ^ Premio ACM Fellow / Zvi Galil
  38. ^ "Dr. Zvi Galil". Miembros de la NAE . Academia Nacional de Ingeniería . Consultado el 11 de mayo de 2012 .
  39. ^ "Zvi Galil elegido miembro de la Academia Nacional de Ingeniería". Noticias de Columbia . Universidad de Columbia . Consultado el 11 de mayo de 2012 .
  40. ^ La Academia elige a la 225.ª clase de becarios y miembros honorarios extranjeros, Asociación Estadounidense para el Avance de la Ciencia , 26 de abril de 2005
  41. ^ "Premio Zvi Galil". Colegio de Columbia . Consultado el 5 de junio de 2019 .
  42. ^ "Quigley y Galil recibirán premios a los mejores maestros". Columbia College Today . Septiembre de 2009 . Consultado el 5 de junio de 2019 .
  43. ^ Smyth, Pamela. "La Universidad de Waterloo otorgará ocho títulos honorarios en la convocatoria de primavera". Waterloo Communications . Universidad de Waterloo . Consultado el 11 de mayo de 2012 .
  44. ^ Larson, Erik J.; PhD (19 de marzo de 2020). "Los científicos informáticos más influyentes de la actualidad". academicinfluence.com . Consultado el 5 de mayo de 2021 .
  45. ^ "Nueva cátedra premia la inclusión y la diversidad". Facultad de Informática . 2021-06-02 . Consultado el 2021-06-09 .

Enlaces externos