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

Вища нагорода в галузі інформатики за 2023 рік дісталася ізраїльському математику Аві Відгерзону за «основний внесок у теорію обчислень, у тому числі за зміну нашого розуміння ролі випадковості в обчисленнях, і за десятки років передової інтелектуальної праці в галузі теоретичної інформатики» Асоціація обчислювальної техніки, яка започаткувала цю премію.

Премію Алана Тьюринга, якій супроводжує грошовий приз у розмірі $1 млн, було присуджено Аві Відгерзону, професору математики в Інституті передових досліджень Принстона (США), через три роки після присудження Абелівської премії за внесок в інформатику, повідомляє Life Science. Теоретичні праці Відгерзона стали ключовими для появи різних інновацій у галузі обчислювальної техніки, від хмарних мереж до методів криптографії, що передували появі криптовалют.

Комп’ютерні алгоритми детерміновані за своєю природою, що дає можливість робити прогнози, але й обмежує в здатності працювати із заплутаною випадковістю реального світу. Багато проблем, які вважаються складними з обчислювальної точки зору, є такими саме тому, що детерміновані алгоритми з ними не справляються.

Однак Відгерзон та його колега Річард Карп знайшли спосіб, як спростити ці проблеми — додаванням до алгоритмів випадковості.

Відгерзон зробив важливе спостереження, яке пізніше підтвердив: імовірнісні алгоритми завжди можна позбавити випадковості, щоб перетворити їх на детерміновані. Це відкриття підкреслює зв’язок між обчислювальною складністю та випадковістю, що призвела до переосмислення теорії інформатики.