Премию Тьюринга присудили за случайность в алгоритмах

Премия Алана Тьюринга, которой сопутствует денежный приз в размере $1 млн, была присуждена Ави Видгерзону, профессору математики в Институте передовых исследований Принстона (США), спустя три года после присуждения Абелевской премии за вклад в информатику, https://www.livescience.com/physics-mathematics/mathematics/... Life Science. Теоретические труды Видгерзона стали ключевыми для появления различных инноваций в области вычислительной техники, от облачных сетей до методов криптографии, которые предшествовали появлению криптовалют.

«Видгерзон возвышается интеллектуальной громадой в теории информатики, интересной дисциплине, которая привлекает самых талантливых молодых исследователей к работе над самыми сложными проблемами, - сказал Яннис Иоаннидис, президент ACM. – В этом году премия Тьюринга чествует работу Видгерзона над случайностью, а также косвенный, но существенный вклад, который он внес в целое поле теоретической информатики».

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

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

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

«С самых ранних дней информатики исследователи понимали, что включение случайности позволит создавать более быстрые алгоритмы для широкого спектра приложений, - произнес во время выступления Джефф Дин, ведущий научный сотрудник Google Research и Google DeepMind. – Попытки лучшего понимания случайности продолжают приносить значимые преимущества нашей области, и Видгерзон открыл для нас новые горизонты».

Попытки приручить случайность https://hightech.plus/2024/03/21/abelevskuyu-premiyu-po-mate... Абелевскую премию 2023 года и Майклу Талагранду. Ученый вывел формулы, делающие случайные процессы более предсказуемыми, и внес важный вклад в различные области знаний, от предсказания погоды до больших языковых моделей.