Математические методы анализа решений в экономике, бизнесе и политике
Внимание! Прямая трансляция в НФ ГУ-ВШЭ состоится 20 октября (среда), 16:30, ауд. 227
20 октября (среда), 16:30, ауд. 227 в Государственном университете - Высшей школе экономики (www.hse.ru) состоится заседание общемосковского научного семинара "МАТЕМАТИЧЕСКИЕ МЕТОДЫ АНАЛИЗА РЕШЕНИЙ В ЭКОНОМИКЕ, БИЗНЕСЕ И ПОЛИТИКЕ".
Руководители семинара:
- д.т.н., проф. Алескеров Фуад Тагиевич,
- д.т.н., проф. Подиновский Владислав Владимирович,
- д.т.н., проф. Миркин Борис Григорьевич.
Доклад:
ДЕТЕРМИНИРОВАННЫЕ И РАНДОМИЗИРОВАННЫЕ АЛГОРИТМЫ НА ПРИМЕРЕ ПОЛИНОМИАЛЬНОЙ АППРОКСИМАЦИИ БУЛЕВЫХ ФУНКЦИЙ
Докладчик:
Кабатянский Григорий Анатольевич (ИППИ РАН и кафедра анализа данных и искусственного интеллекта ВШЭ)
Краткая аннотация:
"Если понятие алгоритма большинству людей, использующих современную математику, знакомо (на том или ином уровне строгости), то рандомизированные (вероятностные) алгоритмы чаще всего ассоциируются лишь с методом Монте-Карло.
Я начну с иллюстративного примера алгоритма оценки числа позиций, в которых различаются два слова из конечного алфавита (например, двоичного). Затем будет рассмотрена задача о нахождении линейных приближений для произвольной булевой функции от m переменных. Лучший известный детерминированный алгоритм - это алгоритм быстрого преобразования Фурье-Адамара и он имеет сложность порядка m log m. А вот рандомизированный алгоритм (Левина-Голдрайха) решает эту задачу со сложностью порядка многочлен(log m). Но, конечно, «бесплатного сыра» здесь тоже нет, и за такую малую сложность приходится платить появлением вероятности ошибки алгоритма и зависимостью сложности алгоритма от «радиуса» приближения. Будет также обсуждена задача о поиске приближений произвольной булевой функции многочленами степени не выше заданной."
Заседание состоится в 16:30 по адресу: 101990, Москва, Покровский бульвар, 11, Высшая школа экономики, корпус Д, аудитория Д-316.
Трансляция семинара организована группой анализа и выбора решений Лаборатории ТАПРАДЕСС (руководитель группы Калягин В.А.) "