Марк Ричард Джеррам (род. 1955) - британский ученый-компьютерщик и теоретик вычислений .
Джеррам получил докторскую степень. в области информатики «О сложности вычисления многомерных многочленов» [1] в 1981 году из Эдинбургского университета под руководством Лесли Валианта . [2] Он является профессором чистой математики в Queen Mary Лондонского университета . [3]
Вместе со своим учеником Алистером Синклером Джеррам исследовал перемешивающее поведение цепей Маркова, чтобы построить алгоритмы аппроксимации для подсчета таких задач, как вычисление перманента , с приложениями в различных областях, таких как алгоритмы сопоставления, геометрические алгоритмы, математическое программирование, статистика, приложения на основе физики , и динамические системы. Эта работа оказала большое влияние на теоретическую информатику и была отмечена премией Гёделя в 1996 году. [4] Уточнение этих методов привело к полностью полиномиальному рандомизированному алгоритму аппроксимации для вычисления перманента, для которого Джеррам и его коллеги. авторы получилиПремия Фулкерсона в 2006 году. [5]
Ссылки [ править ]
- ^ Марк, Джеррам (1981). «О сложности вычисления многомерных многочленов». hdl : 1842/12296 . Цитировать журнал требует
|journal=
( помощь ) - ^ Марк Джеррум на Математическая генеалогия
- ↑ Персональная страница , Королева Мэри, Лондонский университет .
- ^ Гедель премии цитата архивации 12 февраля 2017 в Wayback Machine , 1996.
- ^ Цитирование Премии Фулкерсона 2006 г. , Уведомления AMS , декабрь 2006 г., том 53, номер 11.
Выберите публикации [ править ]
- Frieze, A., Jerrum, M., Molloy M., Robinson, R., & Wormald, N. (1996). Генерация и подсчет циклов Гамильтона в случайных регулярных графах . Журнал алгоритмов , 21, 176–198.