Семинар «Информатика, управление и системный анализ»

ОБЩЕРОССИЙСКИЙ СЕМИНАР «ИНФОРМАТИКА, УПРАВЛЕНИЕ И СИСТЕМНЫЙ АНАЛИЗ»
под общим руководством
Академика РАН Юрия Ивановича Журавлева
Академика РАН Евгения Ивановича Моисеева
Академика РАН Станислава Николаевича Васильева
Академика РАН Юрия Соломоновича Попкова
организатор и ученый секретарь семинара
профессор Михаил Васильевич Ульянов

Общероссийский семинар поддерживает связь с УМО «Математические и компьютерные науки» и УМС по фундаментальной информатике и прикладной математике в интересах российских университетов

Сайт семинара: www.commonmind.ru

ЗАСЕДАНИЕ № 32

Вторник 19 сентября 2017 г., 17-30, ауд. 685 ВМК МГУ

ПОВЕСТКА ДНЯ
1. Научный доклад:
«ВЕРОЯТНОСТНЫЙ ПРОГНОЗ СЛОЖНОСТИ ИНДИВИДУАЛЬНЫХ ЗАДАЧ КОММИВОЯЖЕРА»
Докладчики: д.т.н, проф., в.н.с., Институт проблем управления РАН им. В. А. Трапезникова (ИПУ РАН),
профессор ВМК МГУ имени М.В. Ломоносова Михаил Васильевич Ульянов,
к.ф.-м.н., доцент ФКН НИУ ВШЭ Галина Николаевна Жукова
Аннотация
В докладе приводятся результаты статистического исследования сложности несимметричной задачи коммивояжера (ATSP), полученные в результате обработки пула, состоящего из 15 миллионов несимметричных матриц (экспериментальные результаты получены магистрантом ФКН НИУ ВШЭ М.И. Фомичевым). Показано, что нормальное распределение удовлетворительно приближает распределение логарифма сложности при фиксированной размерности задачи. На этой основе построено семейство распределений сложности, позволяющее удовлетворительно решить задачу вероятностного прогнозирования. Вводится понятие TSP-сложности матрицы, на основе которого формулируются два направления развития исследований.