Пошук академічних текстів

Інформація × Реєстраційний номер 2122U007058, Матеріали видань та локальних репозитаріїв Категорія Опубліковано, Стаття Назва роботи АЛГОРИТМ ДЕКОМПОЗИЦІЇ ПЕРМАНЕНТУ ДЛЯ ГЕНЕРАЦІЇ КОМБІНАТОРНИХ ОБ’ЄКТІВ Автор Турбал Ю. В.Бабич С. В.Кунанець Н. Е.Turbal Y. V.Babych S. V.Kunanets N. E. Дата публікації 11-12-2022 Постачальник інформації Журнал "Радіоелектроніка, інформатика, управління" (Національний університет "Запорізька політехніка") Першоджерело https://ric.zp.edu.ua/article/view/268849 Видання National University "Zaporizhzhia Polytechnic" Опис Актуальність. Розглядається задача генерування векторів, що складаються з різних представників заданої множини. Такі проблеми виникають, зокрема, в теорії складання розкладів, при плануванні зустрічей. Окремим випадком цієї задачі є задача генерування перестановок. Мета роботи – розглянути проблему з точки зору постійного та загальновідомого підходу, виходячи з концепції лексикографічного порядку. Метод. У багатьох завданнях виникає необхідність генерувати різноманітні комбінаторні об’єкти: перестановки, комбінації з повтореннями і без них, різноманітні підмножини. У цій роботі розглядається новий підхід до генерації комбінаторних об’єктів, який базується на процедурі постійної декомпозиції. Перманент будується для спеціальної матриці інцидентності. Основна ідея цього підходу полягає в включенні до процесу алгебраїчної перманентної декомпозиції за допомогою додаткової функції рядка для запису ідентифікаторів стовпців у відповідні структури даних. У цьому випадку алгебраїчний перманент не обчислюється, а отримуємо конкретний рекурсивний алгоритм генерації комбінаторного об’єкта. Проаналізовано обчислювальну складність цього алгоритму. Результати. В межах PD-підходу розглянуто задачі генерації комбінаторних об’єктів, зокрема, перестановок. Досліджено обчислювальну складність запропонованих алгоритмів у порівнянні з відомими підгодами. Розглянуто варіант програмної реалізації розроблених алгоритмів. Висновки. У роботі розглянуто новий підхід до генерації складних комбінаторних об’єктів, що грунтується на процедурі декомпозиції модифікованого перманенту матриці інцидентності за рядком із запам’ятовуванням елементів індексу. Специфіка цього підходу полягає в тому, що певні додаткові умови, що накладаються на відповідні системи різних представників, враховуються на етапі процедур декомпозиції. Досліджено складність розглянутих алгоритмів. У разі більш складних варіантів матриці інцидентності пропонується відповідна модифікація поняття перманенту і, відповідно, процедура його декомпозиції . Додано в НРАТ 2026-02-26 Закрити