Control Systems and Computers, N1, 2021, Стаття 2
https://doi.org/10.15407/csc.2021.01.015
Тимофеева Н.К. Використання властивості періодичності для генерування комбінаторних конфігурацій. Control Systems and Computers. 2021. № 1. С. 15-28.
УДК 519.816
Тимофієва Н.К., д.т.н., пров. наук. співроб., Міжнародний науково-навчальний центр інформаційних технологій та систем НАН та МОН України, tymnad@gmail.com
Використання властивості періодичності для генерування комбінаторних конфігурацій
Вступ. Уводяться правила генерування комбінаторних конфігурацій. Показано, що впорядкуванню комбінаторних множин властиві закономірності, завдяки яким вони генеруються одними і тими ж самими процедурами. Це – властивість періодичності, яка випливає з рекурентного способу утворення та впорядкування комбінаторних конфігурацій. На її основі розроблено рекурентно-періодичний метод, орієнтований для генерування комбінаторних конфігурацій різних типів. За його допомогою упорядкування комбінаторних конфігурацій проводиться за одними і тими самими правилами, а деякі з них генеруються різними модифікаціями одного і того самого алгоритму.
Постановка задачі. Комбінаторні множини можуть бути впорядковані як хаотично, так і за строгими правилами. Аналіз цих множин показує, що вони упорядковуються одними і тими самими процедурами, тобто існують закономірності їхнього генерування. Одна з таких закономірностей, що характерна для багатьох типів комбінаторних конфігурацій, є властивість періодичності, яка випливає з рекурентного способу їхнього утворення. Задача полягає у виявленні та формулюванні загальних правил, за якими утворюються та впорядковуються комбінаторні множини різних типів та різних впорядкувань.
Підхід, що пропонується. Для розв’язання поставленої задачі проводиться аналіз структури комбінаторних множин. Цей аналіз показує, що утворення комбінаторних конфігурацій проводиться за допомогою трьох рекурентних комбінаторних операторів, а їхнє строге впорядкування виконується також за трьома правилами. Тобто, для генерування комбінаторних множин достатньо задати тип комбінаторної конфігурації, базову множину та правила їхнього утворення та впорядкування.
Висновок. Виявлення закономірностей упорядкування певної комбінаторної множини дозволяє розробляти нескладні процедури її генерування для довільного значення і строго доводити, що ця множина містить усі нетотожні комбінаторні конфігурації. Характерною особливістю комбінаторних множин є утворення їх із базової множини за заданими правилами. Для цього досить увести базову множину , з елементів якої проводиться їхнє формування, тип цих об’єктів і систему правил їхнього генерування.
Завантажити повний текст! (українською)
Ключові слова: комбінаторна конфігурація, генерування комбінаторних множин, властивість періодичності, сполучення без повторень, перестановки, розбиття натурального числа.
Надійшла 04.12.2020
