The object of research, development or design (in Russian) : Математическая постановка и методы разрешимости NP-полной задачи Subset Sum в классической, параметризованной и индексной формах.

The object of research, development or design (in Kazakh) : «Subset Sum» NP-толық есебінің классикалық, параметрленген және индекстелген түрлеріндегі математикалық қойылымы мен оны шешу әдістері.

Aim of work (in Russian) : Выполнение этапа НИР за 2025 год согласно календарному плану: формализация задачи Subset Sum в трёх формах, разработка принципов и методик решения, модификация методов разрешимости и формирование банка алгоритмов с оценкой их временной и пространственной сложности.

Aim of work (in Kazakh) : 2025 жылға арналған күнтізбелік жоспарға сәйкес ҒЗЖ кезеңін орындау: Subset Sum есебін үш формада формализациялау, оны шешу қағидаттары мен әдістемелерін әзірлеу, шешімділік әдістерін жетілдіру және олардың уақыттық пен кеңістіктік күрделілігін бағалай отырып алгоритмдер банкін қалыптастыру.

Методы исследования (на русском) : Теоретико-множественный анализ, параметризация подмножеств фиксированной мощности, индексное представление, применение свойств функции сочетаний, свёртки Вандермонда и ограничений Диофантовых уравнений; вычислительные эксперименты с многократными прогонами для оценки времени и памяти алгоритмов.

Методы исследования (на казахском) : Теоретикалық-көптік талдау, бекітілген қуат ішкі жиындарын параметрлеу, индексті ұсыну, комбинация функциясының қасиеттерін қолдану, Вандермонд конволюциясы және Диофант теңдеулерінің шектеулері; алгоритмдердің уақыты мен жадын бағалау үшін бірнеше жүгірістермен есептеу эксперименттері.

Obtained results and novelty (in Russian) : Научная новизна проекта заключается в разработке единой методологии описания задачи Subset Sum, объединяющей классическую, параметризованную и индексную формы. Это позволяет единообразно описывать параметры подмножеств и их индексные представления, что создаёт структурную основу для дальнейшего анализа и построения методов разрешимости. Новизна также выражается в том, что в проекте: 1. формулируются и доказываются теоремы и леммы; 2. вводится индексно-сертификатный метод, позволяющий выделять допустимые структуры без перебора всего пространства; 3. проводится сравнительный алгоритмический анализ, показывающий отличия в масштабируемости с действующими подходами; 4. формируются модули-прототипы, ориентированные на дальнейшее использование в прикладных задачах оптимизации и цифровых вычислительных платформах. Таким образом, проект обладает фундаментальной научной значимостью (развитие структурных методов анализа NP-полных задач) и прикладной актуальностью, поскольку формирует базу для создания точных и воспроизводимых алгоритмов, применимых в современных цифровых системах обработки данных.

Obtained results and novelty (in Kazakh) : Жобаның ғылыми жаңалығы Subset Sum есептің классикалық, параметрленген және индекстелген түрлерін біріктіретін біртұтас сипаттау әдістемесін әзірлеуде. Бұл қосалқы жиындардың параметрлерін және олардың индекстік ұсынылымдарын біркелкі сипаттауға мүмкіндік береді, осылайша одан әрі талдау жүргізу және шешімділік әдістерін құру үшін құрылымдық негіз жасалады. Жаңалық сондай-ақ мынада көрінеді: 1. Теоремалар мен леммаларды тұжырымдап, дәлелдеу жүргізіледі; 2. Барлық кеңістікті қарамай-ақ рұқсат етілген құрылымдарды бөліп көрсетуге мүмкіндік беретін индекстік-сертификаттық әдіс енгізіледі; 3. Іске асырылатын тәсілдермен салыстырмалы алгоритмдік талдау жүргізіледі, масштабталу айырмашылықтары көрсетіледі; 4. Қолданбалы оңтайландыру есептері мен цифрлық есептеу платформаларында әрі қарай пайдалану үшін модуль-прототиптер қалыптастырылады. Осылайша, жоба фундаментальді ғылыми маңыздылыққа ие (NP-толық есептерді талдаудың құрылымдық әдістерін дамыту) және қолданбалы өзектілігі бар, себебі ол қазіргі заманғы цифрлық деректерді өңдеу жүйелерінде қолдануға болатын дәл және қайталанатын алгоритмдерді жасауға негіз қалыптастырады.

The main constructive and technical economic indicators (in Russian) : Создана формальная математическая база, определены методы разрешимости и сформирован банк алгоритмов, включающий полный перебор (Brute Force) как базовый метод для оценки полноты; динамическое программирование в варианте Bellman–Held–Karp с оптимизацией по памяти для сравнения временной и пространственной сложности; индексно-сертификатный метод (Certificates), реализованный в виде первой экспериментальной итерации и опирающийся на разработанные модули, правила индексного перехода и определённые диапазоны k_min – k_max. Выполнены вычислительные эксперименты, включающие замеры времени выполнения, пикового потребления памяти, вариации параметров n, S, kи анализ критериев остановки. Полученные результаты подтверждают корректность алгоритмов и обеспечивают основу для дальнейшего построения вычислительных прототипов.

The main constructive and technical economic indicators (in Kazakh) : Ресми математикалық база құрылған, шешімділік әдістері анықталған және алгоритмдер банкі қалыптастырылған, оған мыналар кіреді: толық перебор (Brute Force) — толықтықты бағалау үшін базалық әдіс ретінде; Bellman–Held–Karp нұсқасындағы динамикалық бағдарламалау, уақыттық және кеңістіктік күрделілікті салыстыру үшін жадыны оңтайландырумен; индекстік-сертификаттық әдіс (Certificates), алғашқы эксперименттік итерация ретінде жүзеге асырылған, әзірленген модульдерге, индекстік өту ережелеріне және k_min – k_max диапазондарына негізделген. Уақытты орындау, жадтың шыңдық тұтынуы, n, S, k параметрлерінің вариациялары мен тоқтату критерийлерін талдауды қамтитын есептеу эксперименттері жүргізілді. Алынған нәтижелер алгоритмдердің дұрыстығын растайды және одан әрі есептеу прототиптерін құруға негіз береді.

Level of implementation (in Russian) : На данном этапе внедрение не выполнялось; результаты являются теоретической и алгоритмической основой для последующих этапов проекта

Level of implementation (in Kazakh) : Осы кезеңде енгізу жүзеге асырылмады; нәтижелер жобаның келесі кезеңдері үшін теориялық және алгоритмдік негіз болып табылады.

Efficiency (in Russian) : Эффективность этапа состоит в создании базовой математической и алгоритмической платформы, необходимой для оптимизации вычислений при анализе подмножеств фиксированной мощности и подготовки прикладных прототипов. Результаты вычислительных экспериментов: • Brute Force. Начиная с k ≈ 7 наблюдается характерный экспоненциальный рост времени выполнения; максимальное зафиксированное значение соответствует k = 13 и составляет около 4.2 секунд. • Dynamic Programming (DP). Для k = 4 время составляет приблизительно 0.07 с; при k = 8 — около 0.7 с; при k = 12 — порядка 1.7 с; при k = 14 — около 2.25 с. Полученные значения демонстрируют квазиполиномиальный характер роста и подтверждают более устойчивое масштабирование DP по сравнению с методом полного перебора, при том, что DP восстанавливает лишь часть допустимых решений. • Certificates. Время работы первой итерации индексно-сертификатного алгоритма составляет около 0.03–0.05 с. по всему диапазону k и практически не увеличивается с ростом параметров. Алгоритм формирует полное множество решений, совпадающее с результатами полного перебора, что подтверждает корректность базовой конструкции и обосновывает необходимость дальнейшего исследования и развития индексно-сертификатного подхода.

Efficiency (in Kazakh) : **Кезеңнің тиімділігі берілген қуаттылықтағы қосалқы жиындарды талдау кезінде есептеулерді оңтайландыру және қолданбалы прототиптерді әзірлеу үшін қажетті базалық математикалық және алгоритмдік платформаны құруда жатыр. Есептеу эксперименттерінің нәтижелері: Brute Force. k ≈ 7 бастап орындалу уақыты экспоненциалды түрде өсетін сипатты көрсетеді; максималды тіркелген мән k = 13 кезінде шамамен 4,2 секундқа тең. Динамикалық бағдарламалау (DP). k = 4 үшін уақыт шамамен 0,07 с; k = 8 — 0,7 с; k = 12 — 1,7 с; k = 14 — 2,25 с. Алынған мәндер өсудің квази-полиномиалды сипатын көрсетеді және DP әдісінің толық переборға қарағанда тұрақты масштабталуын растайды, алайда DP тек рұқсат етілген шешімдердің бір бөлігін қалпына келтіреді. Certificates. Индекстік-сертификаттық алгоритмнің алғашқы итерациясы бойынша жұмыс уақыты k параметрлерінің барлық диапазонында шамамен 0,03–0,05 с болып, параметрлердің өсуімен дерлік өзгермейді. Алгоритм толық шешім жиынтығын қалыптастырады, ол толық перебор нәтижелерімен сәйкес келеді, бұл базалық конструкцияның дұрыстығын растайды және индекстік-сертификаттық тәсілді одан әрі зерттеу мен дамыту қажеттілігін негіздейді.

Field of application (in Russian) : Комбинаторные и оптимизационные задачи, вычислительные методы и алгоритмы, цифровые платформы анализа данных, задачи типа «ранца», «расписания» и распределения ресурсов.

Field of application (in Kazakh) : Комбинаторлық және оңтайландыру есептері, есептеу әдістері мен алгоритмдер, деректерді талдау цифрлық платформалары, «рюкзак», «кестелеу» және ресурстарды бөлу типтес есептер.