Галил, Цви
Цви Галил (род. 26 июня 1947, Тель-Авив, Израиль) — израильско-американский учёный в области информатики. Известен исследованиями в области разработки и анализа алгоритмов, вычислительной сложности и криптографии, а также как соавтор терминов строкология и спарсификация.
Общие сведения
| Цви Галил | |
|---|---|
| ивр. צבי גליל | |
| Дата рождения | 26 июня 1947 (79 лет) |
| Место рождения | Тель-Авив, Подмандатная Палестина |
| Страна | |
| Образование | |
| Род деятельности | |
| Награды и премии |
|
Биография
Галил родился в Тель-Авиве в Подмандатной Палестине в 1947 году. Он получил степени бакалавра (1970) и магистра (1971) по прикладной математике с отличием в Тель-Авивском университете. В 1975 году он получил степень доктора философии по информатике в Корнеллском университете под руководством Джона Хопкрофта[1]. Затем он год работал постдоком в Исследовательском центре имени Томаса Уотсона компании IBM в Йорктаун-Хайтс, Нью-Йорк[2].
Карьера
С 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].
Примечания
Ссылки
- Домашняя страница в Технологическом институте Джорджии
Дополнительно по теме
 | ||||
|---|---|---|---|---|
