Введение

Американский учёный в области компьютерных наук Роберт Седжвик (родился 20 декабря 1946 года) — американский учёный в области компьютерных наук. Он является основателем и профессором имени Уильяма О. Бейкера в области компьютерных наук в Принстонском университете и входил в состав совета директоров Adobe Systems (1990–2016). Ранее он преподавал в Университете Брауна и занимал позиции приглашённого исследователя в Xerox PARC, Институте оборонного анализа и INRIA. Его область научных интересов — алгоритмы, структуры данных и аналитическая комбинаторика. Он также активно участвует в разработке учебных программ по информатике для высших учебных заведений.

Ранние годы

Седжвик родился 20 декабря 1946 года в Виллимантике, штат Коннектикут. В детстве он жил в Сторрсе, штат Коннектикут, где его родители, Чарльз Хилл Уоллес Седжвик и Роуз Уилан Седжвик, преподавали в Университете Коннектикута. В 1958 году он переехал с родителями в Уиттон, штат Мэриленд, пригород Вашингтона, округ Колумбия, и окончил Уиттонскую среднюю школу в 1964 году.

Образование

Седжвик получил степень бакалавра наук (1968) и степень магистра наук (1969) в области прикладной математики в Университете Брауна, где был учеником Андриса ван Дама. Затем он продолжил обучение в аспирантуре в Стэнфордском университете, где его научным руководителем был Дональд Э. Кнут, и получил степень доктора философии в 1975 году. Его диссертация называлась «Quicksort» и была признана выдающейся диссертацией в области компьютерных наук.

Исследования

Седжвик разработал красно-чёрные деревья (совместно с Леонидом Дж. Гибасом), троичные поисковые деревья (совместно с Джоном Бентли) и парные кучи (совместно с Р. Э. Тарьяном и Майклом Фредманом). Он решил нерешённые задачи, поставленные Дональдом Кнутом в анализе быстрой сортировки, сортировки Шелла, сортировки кучей (совместно с Р. Шаффером) и сортировки Батчера. Его книги по алгоритмам содержат множество новых реализаций классических алгоритмов и научных исследований, сравнивающих их, на языках Pascal, C, C++, Modula 3 и Java (см. Библиографию). Он известен тем, что подчёркивает научный подход к анализу алгоритмов, основанный на проверке математических моделей экспериментальными данными, полученными на реалистичных наборах данных. Вместе с Филиппом Флажоле он разработал область математики, известную как аналитическая комбинаторика. Он организовывал исследовательские встречи и конференции по структурам данных, алгоритмической науке и аналитической комбинаторике по всему миру, включая семинары Dagstuhl по анализу алгоритмов и структур данных. В частности, в 1993 году совместно с Райнером Кемпом, Филиппом Флажоле и Гельмутом Продингером он инициировал успешную серию семинаров и конференций, сыгравших ключевую роль в развитии исследовательского сообщества в области анализа алгоритмов, которая впоследствии превратилась в Международную встречу AofA по комбинаторным, вероятностным и асимптотическим методам анализа алгоритмов. Роберт Седжвик также был главным инициатором и организатором первых выпусков конференций SIAM Meetings on Analytic Algorithmics and Combinatorics (ANALCO), которые ежегодно проводились с 2004 по 2019 год совместно с Симпозиумом по дискретным алгоритмам (SODA).

Издательство

Седжвик – автор двадцати книг. Наиболее известен он благодаря книге «Алгоритмы», впервые опубликованной в 1983 году и существующей уже в четвертом издании. Его книга 2008 года, написанная в соавторстве с Филиппом Флажоле, «Аналитическая комбинаторика», была удостоена премии Лероя П. Стила за выдающуюся математическую экспозицию от Американского математического общества. Его последняя книга, написанная совместно с Кевином Уэйном, называется «Информатика: междисциплинарный подход».

Онлайн-обучение

Седжвик – пионер в разработке массовых открытых онлайн-курсов, предлагая в настоящее время шесть MOOC. Вместе с Кевином Уэйном он разработал масштабируемую модель, объединяющую учебник, профессионально записанные онлайн-лекции и обширный онлайн-материал. Их два MOOC и онлайн-материалы по алгоритмам – одни из самых популярных в сети, и они дали возможность более чем миллиону зарегистрированных пользователей учиться у них бесплатно. Он активно выступает за расширение доступности компьютерных наук и освещался в статьях в Chronicle of Higher Education, American Enterprise Institute и The Washington Post, а также опубликовал эссе в Wall Street Journal и Inside Higher Ed.

Награды

Премия Флажоле за лекции. AofA — Международная конференция по комбинаторным, вероятностным и асимптотическим методам в анализе алгоритмов, 2016 год. Премия Лероя П. Стила за популяризацию математики. Американское математическое общество, 2019 год. Премия Карла В. Карлстрома за выдающиеся достижения в области образования. Ассоциация вычислительной техники, 2019 год.

Последние книги и онлайн-контент

Информатика: междисциплинарный подход (с К. Уэйном). Эддисон Уэсли, Рединг, Массачусетс, 2016, 1131 с. Сопутствующий онлайн-контент: Booksite, подборка лекций, часть 1 и часть 2, и MOOC, часть 1 и часть 2. Алгоритмы, четвертое издание (с К. Уэйном). Эддисон Уэсли, Рединг, Массачусетс, 2011, 955 с. Более ранние издания: 11 книг, использующих 5 языков программирования, переведенных на множество иностранных языков, 1983–2003. Сопутствующий онлайн-контент: Booksite, подборка лекций и MOOC, часть 1 и часть 2. Введение в анализ алгоритмов, второе издание (с П. Флажоле). Эддисон Уэсли, Рединг, Массачусетс, 2013, 572 с. Первое издание, 1996. Сопутствующий онлайн-контент: Booksite, подборка лекций и MOOC. Аналитическая комбинаторика (с П. Флажоле). Кембриджский университетский пресс, 2009, 824 с. Сопутствующий онлайн-контент: Booksite, подборка лекций и MOOC.

Личная жизнь

Седжвик живет в Принстоне, штат Нью-Джерси, и проводит лето в Джеймстауне, штат Род-Айленд, с женой Линдой (в девичестве Миньо), с которой он заключил брак в 1971 году. У них четверо детей.