Рассказываем о направлениях исследований, которые ведутся аспирантами на кафедре МО ЭВМ

Недавно прошел итоговый аттестационный семинар, на котором аспирант направления 2.3.5 «Математическое и программное обеспечение вычислительных систем, комплексов и компьютерных сетей» Шевелева Анна Михайловна представила результаты своей диссертационной работы «Полное сведение одной NP-трудной задачи к другой на примере задачи

коммивояжера, задачи о рюкзаке и родственных им задачах».

Работа посвящена исследованию сведения NP-трудных задач друг к другу с сохранением точного результата одной задачи через другую. Известно, что NP-трудные задачи на данный момент не имеют полиномиального решения. Одной из проблем того, что такое решение не найдено, является наличие фазовых переходов в задачах – увеличение сложности вычисления на порядки при небольшом колебании данных. В работе делается предположение того, что если сведение одной задачи к другой точное, то фазовые переходы также будут переноситься с одной задачи в другую. Такой подход к выявлению фазовых переходов в NP-трудных задачах может помочь в определении фазовых переходов в других задачах и дальнейшем улучшении эвристических алгоритмов решения NP-трудных задач.

? На семинаре выполнен разбор статьи Sharma P. C., Chaudhari N. S. Investigation of satisfiability based solution approach for graph coloring problem (Исследование подхода к решению задачи раскраски графа, основанного на задачи выполнимости), журнал - Int J Eng Adv Technol (IJEAT).

Рассмотрены задачи, результаты и применимость в диссертации.

Источник: vk.com

Комментарии: