Цви Галиль ( иврит : צבי גליל ; родился 26 июня 1947 года) — израильско-американский компьютерный учёный и математик . Он занимал должность декана инженерной школы Колумбийского университета и президента Тель-Авивского университета с 2007 по 2009 год. С 2010 по 2019 год он был деканом вычислительного колледжа Технологического института Джорджии . [3]
Его исследовательские интересы включают разработку и анализ алгоритмов , вычислительную сложность и криптографию . Ему приписывают создание терминов стрингология и разреженность. [4] [5] Он опубликовал более 200 научных работ [6] и указан как высокоцитируемый исследователь ISI . [7]
Галил родился в Тель-Авиве в Подмандатной Палестине в 1947 году. Он получил степень бакалавра наук (1970) и магистра наук (1971) в области прикладной математики , обе с отличием , в Тель-Авивском университете . В 1975 году он получил степень доктора философии в области компьютерных наук в Корнеллском университете под руководством профессора компьютерных наук Корнелла Джона Хопкрофта . [1] Затем он провел год, работая в качестве постдокторанта в исследовательском центре IBM Thomas J. Watson в Йорктаун-Хайтс, Нью-Йорк . [8]
С 1976 по 1995 год он работал на кафедре компьютерных наук в Тель-Авивском университете , занимая должность заведующего кафедрой с 1979 по 1982 год. В 1982 году он присоединился к факультету Колумбийского университета , занимая должность заведующего кафедрой компьютерных наук с 1989 по 1994 год. [2] [8] С 1995 по 2007 год он был деканом Школы инженерии и прикладных наук Фонда Фу Колумбийского университета. [9] На этой должности он курировал присвоение школе имени китайского бизнесмена З.И. Фу после того, как на его имя было сделано крупное пожертвование. [10] В Колумбийском университете он был назначен профессором математических методов и компьютерных наук имени Джулиана Кларенса Леви в 1987 году и деканом инженерного факультета имени Морриса и Альмы А. Шапиро в 1995 году. [2]
В 2007 году Галил сменил Итамара Рабиновича на посту президента Тель-Авивского университета. [11] В 1909 году он ушел в отставку и вернулся на факультет, а его преемником стал Джозеф Клафтер . [12] [13] 9 апреля 2010 года он был назначен деканом факультета вычислительной техники Технологического института Джорджии. [3] В Технологическом институте Джорджии вместе с основателем Udacity Себастьяном Труном Галил задумал онлайн-программу магистра наук в области компьютерных наук (OMSCS) колледжа вычислительной техники и руководил созданием программы на факультете. [14] OMSCS впоследствии стала крупнейшей онлайн-программой магистра наук в области компьютерных наук в Соединенных Штатах. [15] OMSCS была представлена в сотнях статей, включая статью на первой странице 2013 года в The New York Times и интервью 2021 года в The Wall Street Journal и Forbes . [14] [16] [17] Inside Higher Education отметил, что OMSCS «предполагает, что учреждения могут успешно предоставлять высококачественные и недорогие степени студентам в больших масштабах». [18] Chronicle of Higher Education отметил, что OMSCS «может иметь наилучшие шансы изменить то, сколько студенты платят за традиционную степень». [19] В статье Forbes за 2023 год под названием «Величайшая программа получения степени из когда-либо существовавших» говорилось, что OMSCS «является — практически по всем меркам — самой успешной программой получения степени в истории». [20] Галил ушел с поста декана и вернулся на постоянную должность преподавателя в июне 2019 года. [21] [22] Сейчас он занимает должность заведующего кафедрой Фредерика Г. Стори по вычислительной технике и исполнительного советника по онлайн-программам в Технологическом институте Джорджии.
В 1982 году Галил основал День теории Колумбийского университета и организовывал это мероприятие в течение первых 15 лет. Он до сих пор существует как День теории в районе Нью-Йорка. [23] С 1983 по 1987 год Галил был председателем ACM SIGACT , организации, которая содействует исследованиям в области теоретической информатики . [24] Он занимал должность управляющего редактора журнала SIAM Journal on Computing с 1991 по 1997 год и главного редактора журнала Journal of Algorithms с 1988 по 2003 год.
Исследования Галила находятся в области алгоритмов , в частности строковых , графовых алгоритмов , сложности и криптографии . Он также проводил исследования в области экспериментального проектирования с Джеком Кифером .
Алгоритмы Галила в реальном времени являются самыми быстрыми из возможных для сопоставления строк и распознавания палиндромов, и они работают даже на самой простой компьютерной модели, многоленточной машине Тьюринга . В более общем плане, он сформулировал условие «предсказуемости», которое позволяет преобразовать любой соответствующий онлайн-алгоритм в алгоритм реального времени. [25] [26] С Джоэлом Сейферасом Галил улучшил оптимальные по времени алгоритмы, сделав их также оптимальными по пространству (логарифмическому пространству). [27]
Галил работал с Дэни Бреслауэром над разработкой линейного параллельного алгоритма O(loglogn) для сопоставления строк [28] , и позже они доказали, что он имеет наилучшую возможную временную сложность среди линейных алгоритмов. [29] Совместно с другими специалистами по информатике он разработал постоянный по времени линейный рандомизированный алгоритм поиска, который должен использоваться, когда задана предварительная обработка шаблона. [30]
Вместе со своими учениками Галил разработал более дюжины самых быстрых на сегодняшний день алгоритмов для точного или приблизительного, последовательного или параллельного, а также одномерного или многомерного сопоставления строк.
Галил работал с другими специалистами по информатике, чтобы разработать несколько самых быстрых на данный момент алгоритмов графов. Примерами являются: максимально взвешенное соответствие; [31] трехвалентный изоморфизм графов; [32] и остовные деревья минимального веса. [33]
Вместе со своими учениками Галил разработал технику, которую он назвал «разрежением» [34], и метод, который он назвал «разреженным динамическим программированием». [35] Первый использовался для ускорения динамических графовых алгоритмов . Второй использовался для ускорения вычислений различных расстояний редактирования между строками.
В 1979 году совместно с Офером Габбером Галил решил ранее открытую задачу построения семейства графов-расширителей с явным коэффициентом расширения [36] , полезных при разработке быстрых графовых алгоритмов.
В 1995 году Галил был избран членом Ассоциации вычислительной техники за «фундаментальный вклад в разработку и анализ алгоритмов и выдающиеся заслуги перед сообществом теоретической информатики» [37] , а в 2004 году он был избран в Национальную инженерную академию за «вклад в разработку и анализ алгоритмов и за лидерство в области компьютерной науки и техники» [38] [39] .
В 2005 году он был избран членом Американской академии искусств и наук . [40]
В 2008 году Колумбийский университет учредил премию имени Цви Галила за студенческую жизнь. [41] В 2009 году Колумбийское общество выпускников наградило его премией «Великий учитель». [42]
В 2012 году Университет Ватерлоо присвоил Галилу почетную степень доктора математики за его «фундаментальный вклад в области графовых алгоритмов и сопоставления строк». [43] В 2020 году Academic Influence включил Галила в список 10 самых влиятельных ученых-компьютерщиков последнего десятилетия, а консультативный совет Колледжа вычислительной техники Технологического института Джорджии собрал более 2 миллионов долларов от более чем 130 спонсоров для создания кафедры имени Галила. [44] [45]