Галил, Цви

Материал из Циклопедии
Перейти к навигации Перейти к поиску

Цви Галил

ивр. צבי גליל
Файл:Zvi Galil.png
Галил в 2023 году


Дата рождения
26 июня 1947 года
Место рождения
Тель-Авив, Подмандатная Палестина



Род деятельности





Награды и премии

Цви Галил ([Нет даты!]) — израильско-американский учёный в области информатики. Известен исследованиями в области разработки и анализа алгоритмов, вычислительной сложности и криптографии, а также как соавтор терминов строкология и спарсификация.

Биография[править]

Галил родился в Тель-Авиве в Подмандатной Палестине в 1947 году. Он получил степени бакалавра (1970) и магистра (1971) по прикладной математике с отличием в Тель-Авивском университете. В 1975 году он получил степень доктора философии по информатике в Корнеллском университете под руководством Джона Хопкрофта[1]. Затем он год работал постдоком в Исследовательском центре имени Томаса Уотсона компании IBM в Йорктаун-Хайтс, Нью-Йорк[2].

Карьера[править]

Файл:Zvi Galil Dec 2016.jpg
Галил в Технологическом институте Джорджии в декабре 2016 года

С 1976 по 1995 год он работал на факультете информатики в Тель-Авивском университете, занимая должность заведующего с 1979 по 1982 год. В 1982 году он присоединился к преподавательскому составу Колумбийского университета, где с 1989 по 1994 год был заведующим кафедрой информатики[2]. С 1995 по 2007 год он занимал должность декана Школы инженерии и прикладных наук Фу Колумбийского университета. На этой должности он руководил присвоением школе имени китайского бизнесмена З. Й. Фу после крупного пожертвования. В Колумбийском университете он был назначен профессором математических методов и информатики имени Джулиана Кларенса Леви в 1987 году и деканом инженерии имени Морриса и Альмы А. Шапиро в 1995 году.

В 2007 году Галил сменил Итамара Рабиновича на посту президента Тель-Авивского университета. В 2009 году он ушёл в отставку и вернулся к преподавательской деятельности, а его преемником стал Йосеф Клафтер[3][4]. 9 апреля 2010 года он был назначен деканом колледжа вычислительной техники Технологического института Джорджии[5]. В Технологическом институте Джорджии вместе с основателем Udacity Себастьяном Труном Галил разработал концепцию онлайн-программы магистратуры по информатике (OMSCS) колледжа вычислительной техники и руководил её созданием. OMSCS стала крупнейшей онлайн-программой магистратуры по информатике в США[6]. Программа OMSCS освещалась в сотнях статей, включая статью на первой полосе The New York Times в 2013 году и интервью в The Wall Street Journal и Forbes в 2021 году[7]. Издание Inside Higher Ed отметило, что OMSCS «показывает, что учебные заведения могут успешно предоставлять студентам высококачественные и недорогие степени в больших масштабах»[8]. The Chronicle of Higher Education отметило, что OMSCS «возможно, имеет лучшие шансы изменить стоимость традиционного образования для студентов». В статье Forbes 2023 года под названием «Величайшая программа получения степени в истории» утверждалось, что OMSCS «является — почти по любым меркам — самой успешной программой получения степени в истории»[9]. Галил покинул пост декана и вернулся к обычной преподавательской деятельности в июне 2019 года[10]. В настоящее время он занимает должность заведующего кафедрой вычислительной техники имени Фредерика Г. Стори и исполнительного советника по онлайн-программам в Технологическом институте Джорджии.

Профессиональная деятельность[править]

В 1982 году Галил основал День теории Колумбийского университета и организовывал это мероприятие первые 15 лет. Оно до сих пор существует как День теории Нью-Йорка[11]. С 1983 по 1987 год Галил был председателем ACM SIGACT, организации, способствующей исследованиям в области теоретической информатики[12]. Он был ответственным редактором SIAM Journal on Computing с 1991 по 1997 год и главным редактором Journal of Algorithms с 1988 по 2003 год.

Исследования[править]

Исследования Галила лежат в области алгоритмов, в частности строковых и графовых алгоритмов, сложности и криптографии. Он также проводил исследования в области планирования экспериментов совместно с Джеком Кифером.

Алгоритмы реального времени Галила являются самыми быстрыми для поиска строк и распознавания палиндромов, и они работают даже на самой базовой компьютерной модели — многоленточной машине Тьюринга. В более общем плане он сформулировал условие «предсказуемости», которое позволяет преобразовать любой соответствующий онлайн-алгоритм в алгоритм реального времени. Совместно с Джоэлом Сейферасом Галил улучшил оптимальные по времени алгоритмы, сделав их также оптимальными по памяти (логарифмическая память).

Галил работал с Дэни Бреслауэром над созданием параллельного алгоритма поиска строк с линейной работой O(loglogn)[13], и позже они доказали, что он имеет наилучшую возможную временную сложность среди алгоритмов с линейной работой. Совместно с другими учёными он разработал рандомизированный алгоритм поиска с линейной работой за константное время, который используется при заданной предварительной обработке шаблона[14].

Вместе со своими студентами Галил разработал более десятка самых быстрых на сегодняшний день алгоритмов для точного или приближённого, последовательного или параллельного, одномерного или многомерного поиска строк.

Галил работал с другими учёными над разработкой нескольких самых быстрых на сегодняшний день графовых алгоритмов. Примеры включают изоморфизм трёхвалентных графов и минимальные остовные деревья[15].

Вместе со своими студентами Галил разработал метод, который он назвал «спарсификацией», и метод, который он назвал «разреженным динамическим программированием». Первый использовался для ускорения динамических графовых алгоритмов. Второй использовался для ускорения вычислений различных расстояний редактирования между строками.

В 1979 году совместно с Офером Габбером Галил решил ранее открытую проблему построения семейства графов-экспандеров с явным коэффициентом расширения, полезных при разработке быстрых графовых алгоритмов.

Награды и почести[править]

В 1995 году Галил был избран членом Ассоциации вычислительной техники за «фундаментальный вклад в разработку и анализ алгоритмов и выдающиеся заслуги перед сообществом теоретической информатики»[16], а в 2004 году он был избран в Национальную инженерную академию за «вклад в разработку и анализ алгоритмов и за лидерство в области информатики и инженерии»[17][18].

В 2005 году он был избран членом Американской академии искусств и наук[19].

В 2008 году Колумбийский университет учредил премию Цви Галила за студенческую жизнь[20]. В 2009 году Общество выпускников Колумбийского университета присудило ему премию «Великий учитель»[21].

В 2012 году Университет Уотерлу присвоил Галилу почётную степень доктора математики за его «фундаментальный вклад в области графовых алгоритмов и поиска строк»[22]. В 2020 году Academic Influence включил Галила в список 10 самых влиятельных учёных в области информатики последнего десятилетия, а консультативный совет Колледжа вычислительной техники Технологического института Джорджии собрал более 2 миллионов долларов от более чем 130 доноров для учреждения именной кафедры в честь Галила[23][24]. В 2024 году Колумбийский университет присвоил Галилу почётную докторскую степень[25], а в 2025 году Ассоциация выпускников инженерии Колумбийского университета наградила его медалью Майкла Пупина за заслуги перед нацией в области науки, технологий или инженерии[26].

Примечания[править]

  1. ↑ Шаблон:Mathgenealogy
  2. ↑ 2,0 2,1 Zvi Galil Named Dean of Columbia's Engineering School. Columbia University (July 14, 1995). Проверено 16 июля 2026.
  3. ↑ Basch_Interactive Presidents of Tel Aviv University | Tel Aviv University | Tel Aviv University. English.tau.ac.il (1980-01-01). Проверено 16 июля 2026.
  4. ↑ Tel Aviv University president quits / Sources: Galil was forced out of office, Haaretz (2 июля 2009 года).
  5. ↑ Institute names next College of Computing Dean. Georgia Institute of Technology (2010-04-09). Архивировано из первоисточника 27 мая 2015.[недоступная ссылка] Проверено 9 апреля 2010.
  6. ↑ Galil, Zvi OMSCS: The Revolution Will Be Digitized. cacm.acm.org. Проверено 16 июля 2026.
  7. ↑ Nietzel, Michael T.. Georgia Tech's Online MS In Computer Science Continues To Thrive. Why That's Important For The Future of MOOCs.
  8. ↑ Analysis shows Georgia Tech's online master's in computer science expanded access | Inside Higher Ed. www.insidehighered.com (20 March 2018). Проверено 16 июля 2026.
  9. ↑ Busteed, Brandon The Greatest Degree Program Ever. Forbes. Проверено 16 июля 2026.
  10. ↑ College's Skyrocketing Stature, Global Impact Highlight Galil's Legacy. Georgia Tech College of Computing (April 16, 2019). Архивировано из первоисточника 5 июня 2019.[недоступная ссылка] Проверено 5 июня 2019.
  11. ↑ New York Area Theory Day. www.cs.columbia.edu. Проверено 16 июля 2026.
  12. ↑ Front matter // ACM SIGACT News. — 1987. — том 19. — № 1.
  13. ↑ Breslauer, Dany An Optimal $O(\log\log n)$ Time Parallel String Matching Algorithm // SIAM Journal on Computing. — 1990. — том 19. — № 6. — С. 1051–1058. — DOI:10.1137/0219072
  14. ↑ Crochemore, Maxime Constant-Time Randomized Parallel String Matching // SIAM Journal on Computing. — 1997. — том 26. — № 4. — С. 950–960. — DOI:10.1137/S009753979528007X
  15. ↑ Gabow, Harold N. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs // Combinatorica. — 1986. — том 6. — № 2. — С. 109–122. — DOI:10.1007/BF02579168
  16. ↑ ACM Fellow Award / Zvi Galil
  17. ↑ Dr. Zvi Galil. NAE Members. National Academy of Engineering. Проверено 16 июля 2026.
  18. ↑ Zvi Galil Elected to National Academy of Engineering. Columbia News. Columbia University. Проверено 16 июля 2026.
  19. ↑ Academy Elects 225th Class of Fellows and Foreign Honorary Members. American Association for the Advancement of Science (April 26, 2005). Архивировано из первоисточника 15 августа 2006.[недоступная ссылка] Проверено 9 ноября 2007.
  20. ↑ Zvi Galil Award. Columbia College. Проверено 16 июля 2026.
  21. ↑ Quigley, Galil To Receive Great Teacher Awards. Columbia College Today (September 2009). Архивировано из первоисточника 26 июня 2017.[недоступная ссылка] Проверено 5 июня 2019.
  22. ↑ Smyth, Pamela University of Waterloo to award eight honorary degrees at spring convocation. Waterloo Communications. University of Waterloo. Проверено 16 июля 2026.
  23. ↑ Top Influential Computer Scientists Today. academicinfluence.com (19 March 2020). Проверено 16 июля 2026.
  24. ↑ New Endowed Chair Honors Inclusion and Diversity. College of Computing (2021-06-02). Проверено 16 июля 2026.
  25. ↑ Columbia Announces 2024 Commencement Honorary Degree Recipients - Bwog. Bwog - Columbia Student News (2024-04-10). Проверено 16 июля 2026.
  26. ↑ Distinguished Alumni Recognized with 2025 Engineering Medals | Columbia Engineering. www.engineering.columbia.edu (2025-05-01). Проверено 16 июля 2026.

Ссылки[править]

Рувики

Одним из источников, использованных при создании данной статьи, является статья из википроекта «Рувики» («ruwiki.ru») под названием «Галил, Цви», расположенная по адресу:

—https://ru.ruwiki.ru/wiki/Галил,_Цви

Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC-BY-SA 4.0 и более поздних версий.

Всем участникам Рувики предлагается прочитать материал «Почему Циклопедия?».

Источник — http://cyclowiki.org/w/index.php?title=Галил,_Цви&oldid=2703745