Лесли Габриэль Валиант FRS [4] [5] (родился 28 марта 1949 года) — британо-американский [6] учёный-компьютерщик и теоретик вычислений . [7] [8] Он родился в семье инженера-химика и переводчицы. [9] В настоящее время он является профессором компьютерных наук и прикладной математики имени Т. Джефферсона Кулиджа в Гарвардском университете . [10] [11] [12] [13] Валиант был удостоен премии Тьюринга в 2010 году, будучи описанным ACM как героическая фигура в теоретической информатике и образец для подражания за его мужество и креативность в решении некоторых из самых глубоких нерешённых проблем в науке; в частности, за его «поразительное сочетание глубины и широты». [6]
Валиант получил образование в Королевском колледже Кембриджа , [14] [6], Имперском колледже Лондона , [14] [6] и в Университете Уорика , где он получил докторскую степень в области компьютерных наук в 1974 году. [15] [1]
Валиант всемирно известен своей работой в области теоретической информатики . Среди его многочисленных вкладов в теорию сложности он ввел понятие #P-полноты («полнота Sharp-P»), чтобы объяснить, почему проблемы перечисления и надежности являются неразрешимыми. Он создал модель обучения «Вероятно, приблизительно правильно » или PAC, которая ввела область теории вычислительного обучения и стала теоретической основой для развития машинного обучения . Он также ввел концепцию голографических алгоритмов, вдохновленную моделью квантовых вычислений . В компьютерных системах он наиболее известен введением модели массовой синхронной параллельной обработки. Аналогично модели фон Неймана для архитектуры одного компьютера, BSP стала влиятельной моделью для параллельных и распределенных вычислительных архитектур. Недавние примеры — Google , принявший его для вычислений в больших масштабах с помощью MapReduce , MillWheel, [16] Pregel [17] и Dataflow , а также Facebook , создавший систему анализа графов, способную обрабатывать более 1 триллиона ребер. [18] [19] Также были активные проекты с открытым исходным кодом для добавления явного программирования BSP, а также других высокопроизводительных моделей параллельного программирования, полученных из BSP. Популярные примеры — Hadoop , Spark , Giraph , Hama , Beam и Dask . Его ранняя работа в теории автоматов включает алгоритм для контекстно-свободного синтаксического анализа , который до сих пор является самым быстрым из известных. Он также работает в области вычислительной нейронауки, сосредоточившись на понимании памяти и обучения.
Книга Валианта 2013 года называется « Вероятно, приблизительно правильно: алгоритмы природы для обучения и процветания в сложном мире» . [20] В ней он, среди прочего, утверждает, что эволюционная биология не объясняет скорость, с которой происходит эволюция, написав, например, следующее: «Доказательства того, что общая схема эволюции Дарвина по сути верна, убедительны для подавляющего большинства биологов. Автор этой книги посетил достаточно музеев естественной истории, чтобы убедиться в этом сам. Однако все это не означает, что современная теория эволюции является адекватно объяснительной. В настоящее время теория эволюции не может дать никакого объяснения скорости, с которой эволюция прогрессирует, развивая сложные механизмы или поддерживая их в изменяющихся условиях».
Валиант начал преподавать в Гарвардском университете в 1982 году и в настоящее время является профессором компьютерных наук и прикладной математики имени Т. Джефферсона Кулиджа в Гарвардской школе инженерии и прикладных наук . До 1982 года он преподавал в Университете Карнеги-Меллона , Университете Лидса и Эдинбургском университете .
Валиант получил премию Неванлинны в 1986 году, премию Кнута в 1997 году, премию EATCS в 2008 году [21] и премию Тьюринга в 2010 году. [22] [23] Он был избран членом Королевского общества (FRS) в 1991 году [4], членом Ассоциации по развитию искусственного интеллекта (AAAI) в 1992 году [24] и членом Национальной академии наук США в 2001 году [25] В номинации Валианта на премию Королевского общества говорится следующее:
Лесли Валиант внес решающий вклад в развитие теоретической информатики. Его работа в основном связана с математической количественной оценкой затрат ресурсов на решение задач на компьютере. В ранней работе (1975) он нашел асимптотически самый быстрый алгоритм, известный для распознавания контекстно-свободных языков. В то же время он был пионером в использовании коммуникационных свойств графов для анализа вычислений. В 1977 году он определил понятие «sharp-P» (#P)-полноты и установил его полезность в классификации задач подсчета или перечисления в соответствии с вычислительной разрешимостью. Первое применение было к подсчету соответствий (матрица постоянной функции). В 1984 году Лесли ввел определение индуктивного обучения, которое впервые примиряет вычислительную осуществимость с применимостью к нетривиальным классам логических правил, которые должны быть изучены. Это понятие, позже названное «вероятно приблизительно правильным обучением», стало теоретической основой для развития машинного обучения. В 1989 году он сформулировал концепцию объемных синхронных вычислений как объединяющий принцип для параллельных вычислений. Лесли получил премию Неванлинны в 1986 году и премию Тьюринга в 2010 году. [26]
В постановлении о присуждении ему премии имени А.М. Тьюринга говорится:
За преобразующий вклад в теорию вычислений, включая теорию вероятно приблизительно правильного (PAC) обучения, сложность перечисления и алгебраических вычислений, а также теорию параллельных и распределенных вычислений. [6]
Его два сына Грегори Валиант [27] и Пол Валиант [28] также являются специалистами по теоретической информатике. [8]
В данной статье используется текст, доступный по лицензии CC BY 4.0.