ЗАСТОСУВАННЯ ДИНАМІЧНОГО ПРОГРАМУВАННЯ ДЛЯ ОПТИМАЛЬНОГО ГРУПУВАННЯ ДИЗ’ЮНКТНИХ БІНАРНИХ ВЕКТОРІВ

ЗАСТОСУВАННЯ ДИНАМІЧНОГО ПРОГРАМУВАННЯ ДЛЯ ОПТИМАЛЬНОГО ГРУПУВАННЯ ДИЗ'ЮНКТНИХ БІНАРНИХ ВЕКТОРІВАнотація.У роботі розглядається задача розбиття множини рядків бінарної матриці на мінімальну кількість груп за критерієм їх попарної диз'юнктності, тобто відсутності спільних одиничних компонент у будь-яких двох векторів однієї групи.Дослідження зосереджене на розробці, аналізі та верифікації точного алгоритму, побудованого на основі методу динамічного програмування з використанням бітових масок.Вивчаються математичні властивості відношення незалежності векторів, структура простору станів задачі та рекурентні співвідношення, що визначають її оптимальну підструктуру.Особливу увагу приділено зменшенню експоненційної надлишковості, характерної для наївних рекурсивних методів.У роботі детально обґрунтовується оптимізація на основі фіксації опорного елемента: вибір наймолодшого встановленого біта в поточній масці як обов'язкового елемента першої групи забезпечує канонічну декомпозицію, уникає повторних конфігурацій та суттєво скорочує простір перебору.Розглянуто також інші оптимізації, зокрема ефективне генерування підмасок, кешування проміжних результатів та застосування низькорівневих бітових операцій для прискорення реалізації алгоритму.Подано докладні оцінки часової та просторової складності, а також окреслено межі практичної застосовності методу для задач розмірності до 25 векторів.Запропонований підхід показує високу ефективність для широкого класу комбінаторних задач, у яких вирішальне значення має незалежність векторів.Отримані результати можуть бути безпосередньо використані у плануванні паралельних обчислень, розподілі ресурсів за умов конфліктів, оптимізації логічних та структурних систем, а також в інших сферах, де