Лесли Валиант
Лесли Валиант | |
|---|---|
 Валиант в 2012 году | |
| Рожденный | Лесли Габриэль Валиант 28 марта 1949 г. |
| Национальность | Британский |
| Альма-матер |
|
| Известный | |
| Награды |
|
| Научная карьера | |
| Поля | Математика Теоретическая информатика Теория вычислительного обучения Теоретическая нейронаука |
| Учреждения | |
| Диссертация | Процедуры принятия решений для семейств детерминированных автоматов с выталкиванием (1974) |
| Докторантура | Майк Патерсон [1] |
| Докторанты | |
| Веб-сайт | люди |
Лесли Габриэль Валиант, ФРС [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] Прегель [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 году. [26]
Цитата на его премию А. М. Тьюринга гласит:
За революционный вклад в теорию вычислений, включая теорию вероятно приблизительно правильного обучения (PAC), сложность перечисления и алгебраических вычислений, а также теорию параллельных и распределенных вычислений. [6]
Личная жизнь
[ редактировать ]Два его сына Григорий Валиант [27] и Пол Валиант [28] оба также учёные-теоретики в области информатики. [8]
Ссылки
[ редактировать ]- ^ Jump up to: а б с Лесли Валиант в проекте «Математическая генеалогия»
- ^ Валиант, Л.; Вазирани, В. (1986). «NP — это так же просто, как найти уникальные решения» (PDF) . Теоретическая информатика . 47 : 85–93. дои : 10.1016/0304-3975(86)90135-0 .
- ^ Валиант, Л.Г. (1979). «Сложность перечисления и проблемы надежности». SIAM Journal по вычислительной технике . 8 (3): 410–421. дои : 10.1137/0208032 .
- ^ Jump up to: а б «Лесли Валиант ФРС» . Лондон: Королевское общество . 1991.
- ^ Выставка каталога архива DServe
- ^ Jump up to: а б с д и «Лесли Дж. Валиант — лауреат премии А.М. Тьюринга» . Премия А. М. Тьюринга . Проверено 9 января 2019 г.
- ^ Хоффманн, Л. (2011). «Вопросы и ответы: Лесли Валиант обсуждает машинное обучение, параллельные вычисления и вычислительную нейробиологию» . Коммуникации АКМ . 54 (6): 128. дои : 10.1145/1953122.1953152 .
- ^ Jump up to: а б Анон (2017). «Доблестный профессор Лесли Габриэль» . Кто есть кто (онлайн- изд. Oxford University Press ). Оксфорд: A&C Black. дои : 10.1093/ww/9780199540884.013.U40928 . (Требуется подписка или членство в публичной библиотеке Великобритании .)
- ^ «Интервью по устной истории на премию AM Тьюринга с Лесли Габриэль Валиант» (PDF) .
- ^ Лесли Валиант Страница профиля автора ACM. в цифровой библиотеке
- ^ Вигдерсон, А. (2009). «Работа Лесли Валиант». Материалы 41-го ежегодного симпозиума ACM по теории вычислений - STOC '09 . стр. 1–2. дои : 10.1145/1536414.1536415 . ISBN 9781605585062 . S2CID 15370663 .
- ^ Лесли Г. Валиант на DBLP библиографическом сервере
- ^ Валиант, Лесли (1984). «Теория обучаемого» (PDF) . Коммуникации АКМ . 27 (11): 1134–1142. дои : 10.1145/1968.1972 . S2CID 12837541 .
- ^ Jump up to: а б «Резюме Лесли Дж. Валиант» (PDF) . Гарвардский университет . Проверено 9 января 2019 г.
- ^ Валиант, Лесли (1973). Процедуры принятия решений для семейств детерминированных автоматов с выталкиванием . warwick.ac.uk (докторская диссертация). Университет Уорика. OCLC 726087468 . EThOS uk.bl.ethos.475930 .
- ^ MillWheel: отказоустойчивая потоковая обработка в масштабе Интернета
- ^ Pregel: система для крупномасштабной обработки графов.
- ^ Сравнение современных систем обработки графов .
- ^ Один триллион ребер: обработка графов в масштабе Facebook
- ^ https://www.hachettebookgroup.com/titles/leslie-valiant/probally-approximately-correct/9780465037902/?lens=basic-books , ISBN 9780465032716
- ^ Дэвид Пелег Премия EATCS 2008 - Laudatio профессору Лесли Валиант Европейская ассоциация теоретической информатики.
- ↑ Джош Фишман «Вероятно, приблизительно правильный» изобретатель из Гарвардского университета, получает премию Тьюринга» Хроника высшего образования, 9 марта 2011 г.
- ^ Премия ACM Тьюринга достается новатору в области машинного обучения Новости ACM Computing
- ^ Избрана Ассоциация стипендиатов AAAI по развитию искусственного интеллекта.
- ^ Справочник участников: Национальная академия наук Лесли Г. Вэлиант.
- ^ https://royalsociety.org/people/leslie-valiant-12451/ Биография Королевского общества
- ^ Домашняя страница Грегори Валианта
- ^ Домашняя страница Пола Валианта
Внешние ссылки
[ редактировать ]
В эту статью включен текст , доступный по лицензии CC BY 4.0 .
- 1949 рождений
- Живые люди
- Члены Национальной академии наук США
- Лауреаты премии Тьюринга
- Лауреаты премии Неванлинны
- Лауреаты премии Кнута
- Британские ученые-компьютерщики
- Теоретики-компьютерщики
- Выпускники факультета вычислительной техники Имперского колледжа Лондона
- Выпускники Уорикского университета
- Академики Эдинбургского университета
- Факультет Гарвардской школы инженерии и прикладных наук имени Джона А. Полсона
- Члены Королевского общества
- Члены Ассоциации развития искусственного интеллекта
- Члены Американской ассоциации содействия развитию науки
- Люди из Белмонта, Массачусетс
- Люди из Будапешта