Cостоялось очередное заседание общемосковского научного семинара "МАТЕМАТИЧЕСКИЕ МЕТОДЫ АНАЛИЗА РЕШЕНИЙ В ЭКОНОМИКЕ, БИЗНЕСЕ И ПОЛИТИКЕ"

Кабатянский Г.А. (ИППИ РАН, кафедра АДиИИ ГУ-ВШЭ) - "Детерминированные и рандомизированные алгоритмы на примере полиномиальной аппроксимации булевых функций"

  Аннотация доклада:

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

Я начну с иллюстративного  примера алгоритма оценки числа позиций, в которых различаются два слова из конечного алфавита (например, двоичного). Затем будет рассмотрена задача о нахождении линейных приближений для произвольной булевой функции от m переменных. Лучший известный детерминированный алгоритм - это алгоритм быстрого преобразования Фурье-Адамара и он имеет сложность порядка m log m. А вот рандомизированный алгоритм (Левина-Голдрайха) решает эту задачу со сложностью порядка многочлен(log m). Но, конечно, «бесплатного сыра» здесь тоже нет, и за такую малую сложность приходится платить появлением вероятности ошибки алгоритма и зависимостью  сложности алгоритма от «радиуса» приближения. Будет также обсуждена задача о поиске приближений произвольной булевой функции многочленами степени не выше заданной.

 

Рабочий язык: русский

------------------------------------------------------------------------------------------------------------------------- 

Руководители семинара: д.т.н., проф. Алескеров Фуад Тагиевич, д.т.н., проф. Подиновский Владислав Владимирович. 
Соруководитель семинара - д.т.н., проф. Миркин Борис Григорьевич,

-------------------------------------------------------------------------------------------------------------------------