МИЭТ

Национальный
исследовательский
университет

Орден трудового красного знамени
Рейтинг QS

National Research University of
Electronic Technology

Версия для слабовидящих Версия для печати Поиск по сайту На гланую страницу сайта
Авторизация
Ученые МИЭТа отличились в сфере высшей математики 09.12.2016

Ученые МИЭТа отличились в сфере высшей математики

Доктор физико-математических наук, доцент кафедры вычислительной техники МИЭТ Михаил Анатольевич Посыпкин принял участие в работе по решению задачи о сумме подмножеств методом ветвей и границ. Вместе с аспирантом МИЭТа Си Ту Тант Сином и профессором кафедры дискретной математики механико-математического факультета МГУ имени М.В. Ломоносова Романом Максимовичем Колпаковым они получили точную верхнюю оценку сложности решения задачи о сумме подмножеств методом ветвей и границ.

Результаты работы были опубликованы в журнале The American Institute of Physics (AIP) Conference Proceedings.

Суть метода ветвей и границ состоит в последовательном переборе вариантов, рассмотрении лишь тех из них, которые по определенным признакам оказываются перспективными, и отбрасывании бесперспективных вариантов. Рассмотрена естественная модификация стандартного метода ветвей и границ, и найдено точное значение сложности решения задачи о сумме подмножеств с этой модификацией в наихудшем случае. Для решения поставленной задачи использовались комбинаторные результаты, касающиеся структуры единичного n-мерного куба.

Дополнительная информация:

Молодые ученые МИЭТа выиграли гранты Президента РФ