№АР26101119

Руководитель проекта Синчев Бахтгерей Куспанович, доктор технических наук, профессор (sinchev@mail.ru)

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

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

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

Ожидаемые результаты:

В 2025-2027 годах будут подготовлены аналитический, промежуточный и заключительный (итоговый) отчеты по НИР. Результатами проекта станут быстрые по времени и пространству алгоритмы и программное обеспечение, пропорциональные квадрату длины входных данных и не зависящих от их бинарного представления. Распространение информации о разработанном проекте планируется через участие в выставках, семинарах, интернет-конференциях, рекламу в профильных печатных изданиях, встречи с ведущими производителями. Научно-исследовательская работа будет являться конкурентоспособной на мировом рынке, так как ориентирована на возможность применения методов машинного обучения и искусственного интеллекта и сможет быть ориентирована на коммерческое применение при решении комбинаторных задач, таких как загрузка воздушных и морских судов, составление расписания аэропортов, учебных занятий и других. Полученные результаты исследования будут способствовать возрастанию уровня цифровой компетенции Казахстана.

Состав исследовательской группы: