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

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

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

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

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

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