Статья: Алгоритмы комбинаторной генерации на основе структур деревьев И/ИЛИ для класса алгебраических производящих функций (2025)

Читать онлайн

В данной статье предложен систематический подход к разработке алгоритмов комбинаторной генерации для множеств дискретных структур, мощность которых задается коэффициентами алгебраических производящих функций и их степеней. Исследование базируется на наличии связи между операциями над производящими функциями и комбинаторными множествами. В качестве основы использован математический аппарат деревьев И/ИЛИ, который позволяет комбинировать алгоритмы комбинаторной генерации для простых подструктур в сложные комбинаторные объекты. При этом основным теоретическим результатом работы является вывод новых эффективных рекуррентных формул для вычисления значений коэффициентов алгебраических производящих функций и их степеней с полиномиальной вычислительной сложностью O ((n1 + … + nm + m) n2)по времени и O( n2) по памяти. На основе доказанных теорем о рекуррентных формулах, предложенный подход позволяет строить алгоритмы с полиномиальной оценкой вычислительной сложности, что делает их применимыми для решения практических задач в области прикладной дискретной математики и теоретической информатики. Кроме того, использование коэффициентов степеней производящих функций расширяет возможности генерации, так как это позволяет строить не только объекты исходного комбинаторного множества, связанного с производящей функцией, но и кортежи таких объектов. Апробация предложенного подхода показана на примерах получения рекуррентных формул и алгоритмов генерации на их основе для классических числовых последовательностей, таких как числа Фибоначчи, Пелля, Каталана, Моцкина и Шредера. Предложенный подход открывает новые возможности для решения задач оптимизации, моделирования и кодирования сложных дискретных структур, например, в таких областях как биоинформатика и криптография.

Ключевые фразы: дискретная структура, комбинаторная генерация, алгебраическая производящая функция, функциональное уравнение, РЕКУРРЕНТНАЯ ФОРМУЛА, дерево иили
Автор (ы): Шабля Юрий Васильевич
Журнал: МОДЕЛИРОВАНИЕ И АНАЛИЗ ИНФОРМАЦИОННЫХ СИСТЕМ

Предпросмотр статьи

Идентификаторы и классификаторы

SCI
Математика
УДК
519.111.3. Комбинаторика формальных степенных рядов. Производящие функции
Для цитирования:
ШАБЛЯ Ю. В. АЛГОРИТМЫ КОМБИНАТОРНОЙ ГЕНЕРАЦИИ НА ОСНОВЕ СТРУКТУР ДЕРЕВЬЕВ И/ИЛИ ДЛЯ КЛАССА АЛГЕБРАИЧЕСКИХ ПРОИЗВОДЯЩИХ ФУНКЦИЙ // МОДЕЛИРОВАНИЕ И АНАЛИЗ ИНФОРМАЦИОННЫХ СИСТЕМ. 2025. Т. 32, № 4
Текстовый фрагмент статьи