Аннотация:
В данной статье предложен систематический подход к разработке алгоритмов комбинаторной генерации для множеств дискретных структур, мощность которых задается коэффициентами алгебраических производящих функций и их степеней. Исследование базируется на наличии связи между операциями над производящими функциями и комбинаторными множествами. В качестве основы использован математический аппарат деревьев И/ИЛИ, который позволяет комбинировать алгоритмы комбинаторной генерации для простых подструктур в сложные комбинаторные объекты. При этом основным теоретическим результатом работы является вывод новых эффективных рекуррентных формул для вычисления значений коэффициентов алгебраических производящих функций и их степеней с полиномиальной вычислительной сложностью $O((n_1 + \ldots + n_m + m) \cdot n^2)$ по времени и $O(n^2)$ по памяти. На основе доказанных теорем о рекуррентных формулах, предложенный подход позволяет строить алгоритмы с полиномиальной оценкой вычислительной сложности, что делает их применимыми для решения практических задач в области прикладной дискретной математики и теоретической информатики. Кроме того, использование коэффициентов степеней производящих функций расширяет возможности генерации, так как это позволяет строить не только объекты исходного комбинаторного множества, связанного с производящей функцией, но и кортежи таких объектов. Апробация предложенного подхода показана на примерах получения рекуррентных формул и алгоритмов генерации на их основе для классических числовых последовательностей, таких как числа Фибоначчи, Пелля, Каталана, Моцкина и Шредера. Предложенный подход открывает новые возможности для решения задач оптимизации, моделирования и кодирования сложных дискретных структур, например, в таких областях как биоинформатика и криптография.
Полный текст:
PDF файл (1666 kB)