Дж. Д. Ульман

Дж. Д. Ульман (англ. J. D. Ullman, полное имя — Джеффри Дэвид Ульман, англ. Jeffrey David Ullman; род. 22 ноября 1942, Нью-Йорк) — американский учёный в области информатики, профессор Стэнфордского университета. Известен фундаментальными работами в теории баз данных, теории компиляции, алгоритмах и формальных языках. Соавтор ряда классических учебников, включая «Структуры данных и алгоритмы», «Системы баз данных: полный курс» и «Компиляторы: принципы, технологии и инструменты» (также известная как «Книга Дракона»). Лауреат премии Тьюринга (2020, совместно с Альфредом Ахо).

Биография

Джеффри Дэвид Ульман родился 22 ноября 1942 года в Нью-Йорке. В 1963 году получил степень бакалавра по математике в Колумбийском университете. В 1966 году защитил докторскую диссертацию (Ph.D.) по электротехнике в Принстонском университете.

После защиты диссертации Ульман работал в лабораториях Bell Labs (1966–1969), где занимался исследованиями в области теории автоматов и формальных языков. В 1969 году перешёл в Принстонский университет, где проработал до 1979 года, сначала в должности доцента, затем профессора. В 1979 году перешёл в Стэнфордский университет, где стал профессором кафедры компьютерных наук. В Стэнфорде он проработал более 40 лет, воспитав множество учеников, многие из которых стали ведущими специалистами в области информатики.

Ульман является членом Национальной инженерной академии США (1989), Национальной академии наук США (2010), Американской академии искусств и наук (2013). В 2020 году совместно с Альфредом Ахо был удостоен премии Тьюринга «за фундаментальные алгоритмы и теории, лежащие в основе реализации языков программирования, и за синтез этих результатов и результатов других исследователей в их учебниках, которые обучали поколения специалистов в области информатики».

Научные достижения

Теория компиляции

Совместно с Альфредом Ахо и Джеффри Хопкрофтом Ульман разработал ряд фундаментальных алгоритмов для лексического, синтаксического и семантического анализа. В частности, он внёс вклад в теорию LR-анализа (Left-to-right, Rightmost derivation) — метода синтаксического анализа, используемого в большинстве современных компиляторов. Его работы по оптимизации кода и генерации кода заложили основу для создания эффективных компиляторов.

Теория баз данных

Ульман является одним из пионеров реляционной модели данных. Он внёс значительный вклад в теорию нормализации, теорию зависимостей и теорию запросов. В частности, он разработал алгоритмы для проверки эквивалентности запросов, анализа вложенных запросов и оптимизации выполнения запросов в реляционных СУБД. Его учебник «Системы баз данных: полный курс» (совместно с Гектором Гарсиа-Молиной и Дженнифер Уидом) является одним из наиболее цитируемых в этой области.

Алгоритмы и структуры данных

Ульман внёс вклад в разработку алгоритмов для работы с графами, включая алгоритмы поиска в глубину и ширину, алгоритмы нахождения кратчайших путей и алгоритмы для проверки свойств графов. Совместно с Ахо и Хопкрофтом он написал классический учебник «Структуры данных и алгоритмы», который стал стандартом для обучения программированию.

Формальные языки и теория автоматов

Ульман внёс вклад в теорию формальных языков, включая работы по контекстно-свободным грамматикам, автоматам с магазинной памятью и машинам Тьюринга. Его учебник «Теория автоматов, языков и вычислений» (совместно с Хопкрофтом и Мотвани) является одним из основных в этой области.

Основные труды

Ульман является автором или соавтором более 20 книг и более 200 научных статей. Наиболее известные учебники:

• «Компиляторы: принципы, технологии и инструменты» (совместно с Ахо, Сети и Ламом) — известна как «Книга Дракона». Впервые издана в 1977 году, выдержала несколько переизданий и является основным учебником по компиляторам.
• «Структуры данных и алгоритмы» (совместно с Ахо и Хопкрофтом) — издана в 1983 году, переведена на многие языки.
• «Системы баз данных: полный курс» (совместно с Гарсиа-Молиной и Уидом) — издана в 2000 году, является одним из основных учебников по базам данных.
• «Теория автоматов, языков и вычислений» (совместно с Хопкрофтом и Мотвани) — издана в 1979 году, выдержала несколько переизданий.

Педагогическая деятельность

Ульман известен как выдающийся преподаватель. В Стэнфордском университете он читал курсы по компиляторам, базам данных, алгоритмам и теории вычислений. Под его руководством защищено более 30 докторских диссертаций. Многие его ученики стали профессорами ведущих университетов мира или основателями технологических компаний.

Награды и признание

• Премия Тьюринга (2020, совместно с Альфредом Ахо)
• Премия ACM SIGMOD за выдающиеся достижения (1998)
• Премия IEEE John von Neumann Medal (2010)
• Член Национальной инженерной академии США (1989)
• Член Национальной академии наук США (2010)
• Член Американской академии искусств и наук (2013)

Интересные факты

• Ульман является соавтором «Книги Дракона», которая получила своё название из-за изображения дракона на обложке первого издания. Книга считается классикой в области компиляторов.
• Он является одним из самых цитируемых учёных в области информатики, его индекс Хирша превышает 100.
• В 2010 году Ульман был удостоен премии IEEE John von Neumann Medal за «вклад в теорию компиляторов, баз данных и алгоритмов, а также за выдающиеся учебники».

Источники

• Jeffrey D. Ullman. Curriculum Vitae. Stanford University.
• ACM Turing Award 2020: Alfred V. Aho and Jeffrey D. Ullman. Association for Computing Machinery.
• National Academy of Engineering. Dr. Jeffrey D. Ullman.
• Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. 2nd ed. Addison-Wesley, 2006.
• Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom. Database Systems: The Complete Book. 2nd ed. Prentice Hall, 2008.
• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. 3rd ed. Addison-Wesley, 2006.