Премия Кнута 2011 достается исследователю Microsoft


Рави Каннан был назван лауреатом Премии Кнута 2011 года, ежегодно присуждаемой Специальной группой по алгоритмам и теории вычислений ACM (Ассоциация вычислительной техники).

Группа алгоритмов и теории вычислений ACM вручила в этом году премию Кнута Рави Каннану из Microsoft Research Labs India за

«разработка влиятельных алгоритмических методов, направленных на решение давних вычислительных проблем».

Большая часть работ, которые упоминаются в качестве причины присуждения премии, могут показаться очень абстрактными, но есть также некоторые очень практические области исследований.

В цитируемой основной статье представлен алгоритм, который работает за полиномиальное время для оценки объема выпуклого тела в n-мерном пространстве. Он использует случайное блуждание по выпуклому телу, порожденному цепью Маркова. Большая часть работы Каннана посвящена случайным алгоритмам с использованием цепей Маркова.

Еще одна более практическая область исследований – это применение преимущественно случайных алгоритмов к большим данным и выборке. Например, быстрый алгоритм Монте-Карло, который производит приближенное умножение матриц, имеет всевозможные практические применения. Алгоритмы кластеризации также фигурируют в исследованиях, как и алгоритмы на решетке.

В целом исследование сосредоточено на алгоритмах, и поэтому Каннан – хороший выбор для этого приза, который связан с отцом анализа алгоритмов, Дональдом Кнутом.


Добавить комментарий