Чарльз Лейзерсон¶

Чарльз Лейзерсон (англ. Charles Leiserson; род. 10 ноября 1953, Норфолк, Виргиния, США) — американский учёный в области информатики, специалист по параллельным вычислениям, алгоритмам и проектированию вычислительных систем. Наиболее известен как соавтор фундаментального учебника «Введение в алгоритмы» (Introduction to Algorithms), а также как разработчик языка Cilk для параллельного программирования.

¶Биография

Чарльз Энтони Лейзерсон родился в семье военного лётчика. В 1975 году получил степень бакалавра наук по информатике в Йельском университете. В 1977 году — степень магистра по информатике в Университете Карнеги — Меллон, а в 1981 году — докторскую степень (Ph.D.) по информатике там же под руководством Джона Бентли и Х. Т. Куна. Диссертация была посвящена проблемам проектирования эффективных алгоритмов на основе теории площадей и времени.

С 1981 года работает в Массачусетском технологическом институте (MIT). В 1985 году стал профессором кафедры электротехники и информатики. В 1996 году основал лабораторию Supercomputing Technologies Group, которую возглавлял до 2015 года. В 2017 году перешёл на позицию профессора-исследователя в MIT Computer Science and Artificial Intelligence Laboratory (CSAIL).

Лейзерсон является членом Ассоциации вычислительной техники (ACM) с 2001 года и Института инженеров электротехники и электроники (IEEE) с 2004 года. За вклад в развитие параллельных вычислений и алгоритмов удостоен ряда наград, включая премию ACM Paris Kanellakis Theory and Practice Award (2013) и премию IEEE Computer Society Charles Babbage Award (2014).

¶Основные научные достижения

¶Учебник «Введение в алгоритмы»

В 1990 году совместно с Томасом Корменом, Рональдом Ривестом и Клиффордом Штайном выпустил первое издание книги «Введение в алгоритмы» (Introduction to Algorithms). Книга стала одним из самых цитируемых учебников по информатике в мире, выдержала четыре издания (1990, 2001, 2009, 2022) и переведена на десятки языков, включая русский. Учебник охватывает широкий спектр алгоритмов — от сортировки и поиска до графовых алгоритмов и криптографии, и используется в ведущих университетах мира как базовый курс по алгоритмам.

¶Язык Cilk и параллельные вычисления

В 1994 году Лейзерсон разработал язык параллельного программирования Cilk (позднее Cilk++ и Cilk Plus). Cilk основан на языке Си и предоставляет программисту простые аннотации (ключевые слова cilk_spawn, cilk_sync, cilk_for) для автоматического распараллеливания рекурсивных алгоритмов. Язык использует лёгкие потоки (fibers) и планировщик с алгоритмом «воровство работы» (work-stealing), который обеспечивает эффективное распределение задач между процессорами. Cilk стал основой для коммерческих продуктов Intel Cilk Plus (2010–2017) и повлиял на развитие параллельных расширений в языках C++ (OpenMP, TBB) и Java.

¶Теория алгоритмов и вычислительных систем

Лейзерсон внёс вклад в теорию сложности вычислений, в частности в анализ алгоритмов на многопроцессорных системах. Совместно с Томасом Корменом разработал модель «потоковых графов» (stream graphs) для анализа параллельных вычислений. Также известен работами по проектированию VLSI-схем (сверхбольших интегральных схем) — его диссертация и последующие исследования заложили основы теории площади и времени для интегральных схем.

¶Алгоритмы для графов и комбинаторики

Совместно с другими учёными Лейзерсон разработал алгоритмы для поиска максимального потока в сетях (алгоритм Эдмондса — Карпа с улучшениями), а также алгоритмы для задачи о кратчайших путях и задачи о рюкзаке. Его работы по комбинаторной оптимизации используются в логистике, телекоммуникациях и проектировании сетей.

¶Критика и влияние

Работы Лейзерсона получили широкое признание в научном сообществе. Учебник «Введение в алгоритмы» критикуется некоторыми специалистами за излишнюю формальность и объём (более 1300 страниц в четвёртом издании), однако остаётся стандартом для обучения алгоритмам. Язык Cilk, несмотря на свою эффективность, не получил массового распространения из-за конкуренции с OpenMP и другими технологиями, но его идеи (воровство работы, лёгкие потоки) стали основой для современных библиотек параллельного программирования.

Лейзерсон является активным популяризатором параллельных вычислений. Он регулярно выступает на конференциях (включая SIGCOMM, SC, PPoPP) и ведёт блог о высокопроизводительных вычислениях. В 2010-х годах участвовал в разработке стандарта C++11 для параллельного программирования.

¶Награды и звания

• 2001 — член ACM (Association for Computing Machinery)
• 2004 — член IEEE (Institute of Electrical and Electronics Engineers)
• 2013 — премия ACM Paris Kanellakis Theory and Practice Award (совместно с Томасом Корменом, Рональдом Ривестом и Клиффордом Штайном) за вклад в теорию алгоритмов и их практическое применение
• 2014 — премия IEEE Computer Society Charles Babbage Award за выдающиеся достижения в области параллельных вычислений
• 2019 — почётный доктор (Doctor Honoris Causa) Университета Лозанны (Швейцария)

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

• Лейзерсон является автором более 100 научных статей и нескольких патентов в области параллельных вычислений и алгоритмов.
• В 1990-х годах он совместно с MIT разработал систему MapReduce для распределённых вычислений, которая позже стала основой для одноимённой технологии Google (опубликована в 2004 году).
• Лейзерсон — один из немногих учёных, чьи работы цитируются более 100 000 раз (по данным Google Scholar).
• В 2015 году он основал стартап Cilk Arts, занимавшийся коммерциализацией параллельного программирования (позднее поглощён Intel).

¶Источники

• Charles Leiserson. MIT CSAIL. — Официальный профиль на сайте MIT.
• Introduction to Algorithms, 4th Edition. — T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. — MIT Press, 2022.
• Cilk: An Efficient Multithreaded Runtime System. — R. D. Blumofe, C. E. Leiserson. — Journal of Parallel and Distributed Computing, 1995.
• ACM Paris Kanellakis Theory and Practice Award — 2013. — ACM Press.
• IEEE Computer Society Charles Babbage Award — 2014. — IEEE Computer Society.