Лесли Габриэль Валиант 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 году он определил понятие «точной P» (#P)-полноты и установил ее полезность при классификации задач подсчета или перебора в соответствии с вычислительной сложностью. Первым применением был подсчет совпадений (постоянная функция матрицы). В 1984 году Лесли представил определение индуктивного обучения, которое впервые сочетает вычислительную осуществимость с применимостью к нетривиальным классам логических правил, которые необходимо изучить. Это понятие, позже получившее название «вероятно приблизительно правильное обучение», стало теоретической основой для развития машинного обучения. В 1989 году он сформулировал концепцию объемных синхронных вычислений как объединяющий принцип параллельных вычислений. Лесли получила премию Неванлинны в 1986 году и премию Тьюринга в 2010 году .
Цитата на его премию А. М. Тьюринга гласит:
За революционный вклад в теорию вычислений, включая теорию вероятно приблизительно правильного обучения (PAC), сложность перечисления и алгебраических вычислений, а также теорию параллельных и распределенных вычислений. [6]
Два его сына Грегори Валиант [27] и Пол Валиант [28] также являются учеными-теоретиками в области информатики. [8]
В эту статью включен текст, доступный по лицензии CC BY 4.0.