Введение

Британский американский учёный в области компьютерных наук

Лесли Габриэль Валиант (родился 28 марта 1949 года) — британец и американец по происхождению. Его отец был инженером-химиком, а мать — переводчиком. В настоящее время он является профессором компьютерных наук и прикладной математики в Гарвардском университете. Валиант был удостоен премии Тьюринга в 2010 году, и А.С.М. назвала его выдающейся фигурой в теоретической информатике и образцом для подражания благодаря его смелости и креативности в решении глубочайших нерешённых проблем науки, особенно отметив его «поразительное сочетание глубины и широты». Он участвовал в разработке систем графической аналитики для Imperial College London, Pregel и Dataflow, а также для Facebook, способных обрабатывать более триллиона рёбер. Существуют также активные проекты с открытым исходным кодом, направленные на добавление явного BSP-программирования, а также других высокопроизводительных моделей параллельного программирования, основанных на BSP. Популярные примеры включают Hadoop, Spark, Giraph, Hama, Beam и Dask. Его ранние работы в теории автоматов включают алгоритм контекстно-свободного разбора, который до сих пор остаётся самым быстрым из известных. Он также работает в области вычислительной нейробиологии, уделяя особое внимание пониманию механизмов памяти и обучения. Книга Валианта 2013 года называется «Вероятно, приблизительно верно: алгоритмы природы для обучения и процветания в сложном мире». В ней он, среди прочего, утверждает, что эволюционная биология не объясняет скорость эволюции, приводя пример: «Доказательства того, что общая схема эволюции Дарвина в целом верна, убедительны для подавляющего большинства биологов. Сам автор посетил достаточно музеев естественной истории, чтобы убедиться в этом. Однако это не означает, что современная теория эволюции является адекватным объяснением. В настоящее время теория эволюции не может объяснить темпы, с которыми эволюция развивает сложные механизмы или поддерживает их в меняющихся условиях». Валиант начал преподавать в Гарвардском университете в 1982 году и в настоящее время является профессором компьютерных наук и прикладной математики в Гарвардской школе инженерии и прикладных наук. До 1982 года он преподавал в Университете Карнеги — Меллона, Университете Лидса и Университете Эдинбурга.

Награды и почести

Валиант получил премию Неванлинны в 1986 году, премию Кнута в 1997 году, премию EATCS в 2008 году и премию Тьюринга в 2010 году. В 1991 году он был избран членом Королевского общества (FRS), а в 2001 году – членом Национальной академии наук США. В представлении к избранию Валианта в Королевское общество говорится:

Лесли Валиант внес решающий вклад в развитие теоретической информатики. Его работа посвящена главным образом математическому определению количественных затрат ресурсов, необходимых для решения задач на компьютере. В ранних работах (1975) он обнаружил асимптотически самый быстрый известный алгоритм для распознавания контекстно-свободных языков. Одновременно он стал пионером в использовании коммуникационных свойств графов для анализа вычислений. В 1977 году он определил понятие #P-полноты и установил ее полезность в классификации задач подсчета и перечисления с точки зрения вычислительной реализуемости. Первым применением стало подсчет паросочетаний (постоянная матрицы). В 1984 году Лесли представил определение индуктивного обучения, которое впервые согласовало вычислительную осуществимость с применимостью к нетривиальным классам логических правил, подлежащих изучению. Это понятие, впоследствии названное «вероятно, приблизительно правильным обучением» (PAC-обучением), стало теоретической основой для развития машинного обучения. В 1989 году он сформулировал концепцию массово-синхронных вычислений как объединяющий принцип для параллельных вычислений. Лесли получил премию Неванлинны в 1986 году и премию Тьюринга в 2010 году. В обосновании присуждения ему премии А.М. Тьюринга говорится:

За преобразующий вклад в теорию вычислений, включая теорию вероятно, приблизительно правильного (PAC) обучения, сложность перечисления и алгебраических вычислений, а также теорию параллельных и распределенных вычислений. Пол Валиант также является теоретиком-информатиком.