Дайер, Мартин
Мартин Дайер
- Место рождения
- Райд
- Род деятельности
- математик, специалист в области теоретической информатики
- Место работы
- Университет Лидса
- Учёная степень
- доктор философии
Награды и премии
Премия Фалкерсона (1991), Премия EATCS (2013), Премия Гёделя (2021)
- Сайт
-
{{#property:p856}}
Мартин Эдвард Дайер (англ. Martin Edward Dyer; [Нет даты!]) — британский математик и специалист в области теоретической информатики. Известен работами по сложности задач оптимизации. Лауреат премии Фалкерсона (1991), премии EATCS (2013) и премии Гёделя (2021).
Биография[править]
В 1967 году получил степень бакалавра в Университете Лидса, в 1968 году — степень магистра в Имперском колледже Лондона. В 1979 году защитил диссертацию на соискание степени доктора философии в Университете Лидса (тема: «Перечисление вершин в математическом программировании — методы и приложения») под руководством Леса Г. Пролла[1]. Является профессором Школы вычислительной техники Университета Лидса.
Научная деятельность[править]
Области исследований Дайера включают теоретическую информатику, дискретную оптимизацию и комбинаторику. Он работает над сложностью перечисления и эффективностью алгоритмов приближённого перечисления с использованием цепей Маркова. Основные достижения[2]:
- Дайер и независимо от него Нимрод Мегиддо разработали алгоритмы линейного времени для линейных программ в малых размерностях. Эти алгоритмы были улучшены Дайером, Мегиддо и другими исследователями, что привело к созданию высокоэффективных алгоритмов линейного времени, имеющих важные приложения в вычислительной геометрии.
- В области вероятностного анализа алгоритмов результаты Дайера и Фриза показывают, что многие NP-трудные задачи комбинаторной оптимизации могут быть решены за полиномиальное время в среднем, если экземпляры выбираются из естественных распределений.
- В статье, написанной совместно с Аланом Фризом и Равиндраном Каннаном[3], описан рандомизированный алгоритм полиномиального времени для аппроксимации объёма выпуклого тела в многомерном пространстве. Эта работа является наиболее известной. Традиционные подходы имеют время выполнения, которое экспоненциально возрастает с увеличением числа измерений. Алгоритм, предложенный тремя авторами, стал первым полиномиальным алгоритмом в зависимости от размерности.
- Применение метода связывания путей для доказательства быстрого перемешивания цепей Маркова (совместно с Рассом Бабли).
- Исследование сложности перечисления задач удовлетворения ограничений.
Награды и премии[править]
В 1991 году Мартин Дайер совместно с Аланом Фризом и Рави Каннаном получил премию Фалкерсона[4] по дискретной математике за статью в журнале ACM[3]. В 2013 году EATCS присудила ему премию EATCS. В 2021 году он был удостоен премии Гёделя.
Примечания[править]
- ↑ Дайер, Мартинангл. в проекте «Математическая генеалогия»
- ↑ Laudatio pour le prix de l'EATCS.
- ↑ 3,0 3,1 A random polynomial-time algorithm for approximating the volume of convex bodies // Journal of the ACM. — 1991. — том 38. — № 1. — С. 1–17. — DOI:10.1145/102782.102783
- ↑ Prix Fulkerson 1991
 | Одним из источников, использованных при создании данной статьи, является статья из википроекта «Рувики» («ruwiki.ru») под названием «Дайер, Мартин», расположенная по адресу:
Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC-BY-SA 4.0 и более поздних версий. Всем участникам Рувики предлагается прочитать материал «Почему Циклопедия?». |
|---|