Математические методы анализа решений в экономике, бизнесе и политике

20 октября (среда), 16:30, ауд. 227 в Государственном университете - Высшей школе экономики (www.hse.ru) состоится заседание общемосковского научного семинара "МАТЕМАТИЧЕСКИЕ МЕТОДЫ АНАЛИЗА РЕШЕНИЙ В ЭКОНОМИКЕ, БИЗНЕСЕ И ПОЛИТИКЕ".

Руководители семинара:

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

Доклад:

ДЕТЕРМИНИРОВАННЫЕ   И   РАНДОМИЗИРОВАННЫЕ АЛГОРИТМЫ   НА   ПРИМЕРЕ   ПОЛИНОМИАЛЬНОЙ АППРОКСИМАЦИИ   БУЛЕВЫХ  ФУНКЦИЙ

Докладчик:

Кабатянский Григорий Анатольевич (ИППИ РАН и кафедра анализа данных и искусственного интеллекта ВШЭ)

Краткая аннотация:

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

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

Заседание состоится в 16:30 по адресу: 101990, Москва, Покровский бульвар, 11, Высшая школа экономики, корпус Д, аудитория Д-316.

Трансляция семинара организована группой анализа и выбора решений Лаборатории ТАПРАДЕСС (руководитель группы Калягин В.А.) "