Цель проекта

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

Актуальность

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

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

Значимость проекта

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

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

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

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

Достигнутые результаты

Проект основан на ранее полученных результатах, опубликованных в статьях и патентах США, которые касаются проблемы о сумме подмножеств с малой мощностью выходного множества. Результаты были доложены на Ninth International Congress on Information and Communication Technology в Лондоне с публикацией в серии Springer Link.

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

Публикации (2022–2024)

1. Sinchev B., Sinchev A.B., Mukhanova A.M. Algorithm Based on the Subset Sum Problem for High Performance Computing // Lecture Notes in Networks and Systems. 2024. Vol. 1002. P. 627–637. DOI: 10.1007/978-981-97-3299-9_51
2. Sinchev B., Mukhanova A., Auezova A., Sadykova T. Polynomial Solvability of the Subset Sum Problem // SIST 2022 — International Conference on Smart Information Systems and Technologies, Proceedings. 2022. DOI: 10.1109/SIST54437.2022.9945761

Патенты

1. Sinchev B., Sinchev A.B., Akzhanova Z.A., Issekeshev Y. Computing network architecture for reducing a computing operation time and memory usage associated with determining, from a set of data elements, a subset of at least two data elements, associated with a target computing operation result. US Patent 10,860,317 B2, 2020.
2. Sinchev B., Sinchev A., Akzhanova Z. Computing Network Architecture for Reducing a Computing Operation Time and Memory Usage Associated with Determining, from a Set of Data Elements, a Subset of at Least Two Data Elements, Associated with a Target Computing Operation Result. US Patent 10,394,555 B1, 2019.

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