Премію Тьюринга присудили за випадковість у алгоритмах
Вища нагорода в галузі інформатики за 2023 рік дісталася ізраїльському математику Аві Відгерзону за «основний внесок у теорію обчислень, у тому числі за зміну нашого розуміння ролі випадковості в обчисленнях, і за десятки років передової інтелектуальної праці в галузі теоретичної інформатики» Асоціація обчислювальної техніки, яка започаткувала цю премію.
Премію Алана Тьюринга, якій супроводжує грошовий приз у розмірі $1 млн, було присуджено Аві Відгерзону, професору математики в Інституті передових досліджень Принстона (США), через три роки після присудження Абелівської премії за внесок в інформатику, повідомляє Life Science. Теоретичні праці Відгерзона стали ключовими для появи різних інновацій у галузі обчислювальної техніки, від хмарних мереж до методів криптографії, що передували появі криптовалют.
Комп’ютерні алгоритми детерміновані за своєю природою, що дає можливість робити прогнози, але й обмежує в здатності працювати із заплутаною випадковістю реального світу. Багато проблем, які вважаються складними з обчислювальної точки зору, є такими саме тому, що детерміновані алгоритми з ними не справляються.
Однак Відгерзон та його колега Річард Карп знайшли спосіб, як спростити ці проблеми — додаванням до алгоритмів випадковості.
Відгерзон зробив важливе спостереження, яке пізніше підтвердив: імовірнісні алгоритми завжди можна позбавити випадковості, щоб перетворити їх на детерміновані. Це відкриття підкреслює зв’язок між обчислювальною складністю та випадковістю, що призвела до переосмислення теорії інформатики.
![У Миколаєві любителі дрифтингу влаштували показові виступи (відео)](https://img.youtube.com/vi/OlqnvoZGlWo/mqdefault.jpg?t=88d3fe6)
![У Миколаївській області провели перші у 2024 році змагання з кінного спорту (фото, відео)](https://img.youtube.com/vi/ZjMYFWqGyk0/mqdefault.jpg?t=88d3fe6)
![Мешканці будинку у центрі Миколаєва стали заручниками байдужості мерії](https://img.youtube.com/vi/AjorqUBs4V8/mqdefault.jpg?t=88d3fe6)
![Масштабна пожежа на Намиві: вогонь впритул підступив до гаражів (відео)](https://img.youtube.com/vi/GQdR85n0VUY/mqdefault.jpg?t=88d3fe6)
![У Миколаєві зіткнулися Opel і Toyota: під час погрузки працівник евакуатору «упустив» одну з машин (фото, відео)](https://img.youtube.com/vi/fnDmJm64-0g/mqdefault.jpg?t=88d3fe6)
![ДТП з перевернутим MAN у Миколаєві: із фури розсипалося зерно, його збирають технікою](https://img.youtube.com/vi/oDa70YRTp9g/mqdefault.jpg?t=88d3fe6)
![На Прикарпатті жителі перекрили дорогу та заблокували роботу ТЦК: дійшло до бійки](https://img.youtube.com/vi/2g2QmmrG6OQ/mqdefault.jpg?t=88d3fe6)
![Миколаївський театр закрив 101-й сезон: директор розповів про подробиці (фото, відео)](https://img.youtube.com/vi/7s11aD8578Y/mqdefault.jpg?t=88d3fe6)
![У центрі Миколаєва зіткнулися три автомобілі, один із них перекинувся: четверо постраждалих (фото, відео)](https://img.youtube.com/vi/vyqXGHSfWfo/mqdefault.jpg?t=88d3fe6)