ФОРМУВАННЯ АЛГОРИТМІВ СОРТУВАННЯ ЗАСОБАМИ КОНСТРУКТИВНО-ПРОДУКЦІЙНОГО МОДЕЛЮВАННЯ ТА ГЕНЕТИЧНОГО АЛГОРИТМУ
DOI:
https://doi.org/10.34185/1991-7848.itmm.2026.01.045Ключові слова:
конструктивно-продукційне моделювання, програмне забезпечення, інформаційні технології, алгоритм, генетичний алгоритмАнотація
Розглянуто підхід до автоматизованого синтезу алгоритмів сортування на основі конструктивно‑продукційного моделювання. Описано конструктивну модель хромосоми деревовидної структури, яка кодує алгоритм сортування у вигляді ієрархічної композиції алгоритмічних фрагментів і допоміжних операцій. Представлено систему з трьох взаємопов’язаних конструкторів: конструктора формування хромосоми‑дерева, конструктора‑трансформера для перетворення деревоподібної хромосоми у лінійну послідовність генів та конструктора‑ трансформера, що забезпечує генерацію програмного коду алгоритму сортування мовою програмування.
Показано, що використання чотирьох етапів конструктивно‑продукційного моделювання – спеціалізації, інтерпретації, конкретизації та реалізації – дозволяє формалізувати процес переходу від абстрактного опису алгоритму до його виконуваної програмної реалізації. Застосування генетичного алгоритму забезпечує еволюційний відбір та оптимізацію алгоритмів сортування за заданими критеріями якості з урахуванням властивостей вхідних даних і обмежень обчислювального середовища.
Запропонований підхід створює умови для структурної адаптації алгоритмів, поєднання базових алгоритмічних примітивів у нові коректні композиції та розширення простору пошуку ефективних алгоритмічних рішень. Отримані результати підтверджують доцільність використання конструктивно‑продукційного моделювання як основи для автоматизованого синтезу та оптимізації алгоритмів сортування.
Посилання
J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. – MIT Press, 1992. https://mitpress.mit.edu/9780262111706/genetic-programming/
R. Sedgewick, K. Wayne. Algorithms. – Addison‑Wesley, 2011. https://algs4.cs.princeton.edu/home/
V.I. Shynkarenko, V.M. Ilman. Constructive-Synthesizing Structures and Their Grammatical Interpretations. I. Generalized Formal Constructive-Synthesizing Structure / Cybernetics and Systems Analysis, Volume 50, Issue 5, pp 655-662. https://doi.org/10.1007/s10559-014-9655-z
M. Mitchell. An Introduction to Genetic Algorithms. – MIT Press, 1998. https://mitpress.mit.edu/9780262631853/an-introduction-to-genetic-algorithms/
V. Shynkarenko, O. Makarov. Structural Adaptation of Sorting Algorithms Based on Constructive Fragments / 14th International Scientific and Practical Programming Conference, UkrPROG 2024, CEUR Workshop Proceedings. Vol. 3806, pp. 16–29. https://ceur-ws.org/Vol-3806/
