Browsing by Author "Макаров, Олексій Вікторович"

Now showing 1 - 6 of 6

Генетичний алгоритм для структурної адаптації алгоритмів сортування
(Інститут програмних систем НАН України, Київ, 2024) Шинкаренко, Віктор Іванович; Макаров, Олексій Вікторович
UKR: Застосовано конструктивізм для формування коду алгоритму сортування. Представлено метаалгоритм генерації програмного коду. Для генерації використовуються частини існуючих алгоритмів сортування і допоміжні утиліти. Використано генетичний алгоритм для вибору алгоритму з максимальною часовою ефективністю у заданих умовах використання. Використання стандартного генетичного алгоритму стикається з проблемою, пов’язаною з різною кількістю елементарних дій по сортуванню, що призводить до використання хромосом різної довжини. Для рішення проблеми запропоновано представлення хромосоми у формі бінарного дерева. Кожен вузол має гени початку, кінця і двох вузлів-нащадків. Для формування алгоритму, який гарантовано буде сортувати масив, усі кінцеві вузли (листя) включають ген фінального сортування у кінець початкової послідовності генів. Даний ген декодується викликом існуючого алгоритму сортування, який гарантовано виконає сортування. Операції кросоверу та мутацій виконуються на хромосомах у формі бінарного дерева. Схрещення виконується за допомогою обміну вузлами дерева. Реалізовані механізми кодування і декодування алгоритму сортування із хромосоми. Для декодування і формування відповідного алгоритму сортування виконується лінеріалізація: формування текстового представлення за алгоритмом обходу дерева у глибину. Фітнес функція визначається як середній час сортування випадково сформованих масивів для сортування (для всіх хромосом однакові масиви) у деякому стабільному середовищі з урахуванням певних особливостей цих масивів. Передбачено застосування інших фітнес функцій пов’язаних з кількістю обчислень, порівнянь або перестановок. Розроблене програмне забезпечення має застосовуватись у процесі адаптації алгоритмів сортування до стабільних потоків вхідних даних та середовищ використання.
Дослідження ефективності деяких детермінованих методів передобробки сортування даних
(Інститут програмних систем НАН України, Київ, 2023) Шинкаренко, Віктор Іванович; Макаров, Олексій Вікторович
UKR: Для виконання перевірки гіпотези щодо зменшення часу сортування алгоритмами різної обчислювальної складності проведені експерименти. Опрацьовано декілька ідей з детермінованої передобробки масивів даних для алгоритмів сортування. Запропоновані відповідні алгоритми: швидка передобробка – передбачення індексу елемента у відсортованому масиві і перестановка, передобробка з пам’яттю – передбачення і перестановка із запам’ятовуванням раніше встановлених елементів, передобробка із розворотом – розвертання послідовностей елементів відсортованих у зворотному порядку. Також запропоновані блочні варіації швидкої та передобробки з пам’яттю, які виконуються для частин масиву заданої довжини. Встановлено що більшу ефективність передобробки показують разом із алгоритмами сортування які значно прискорюються на відсортованих (або майже відсортованих) масивах даних. Блочні передобробки можуть виконуватись швидше через можливість уникнути промахів кешу (cache miss), однак показують нижчий відсоток впорядкованості масиву. Проведені експерименти з оцінки ефективності різних алгоритмів сортування після і разом з запропонованими передобробками.
Комбіновані алгоритми сортування
(Український державний університет науки і технологій, ІВК «Системні технології», Дніпро, 2023) Шинкаренко, Віктор Іванович; Макаров, Олексій Вікторович
UKR: Це дослідження представляє використання попередньої обробки даних для підвищення продуктивності алгоритмів сортування. Поєднання різних базових алгоритмів сортування вже успішно використовувалося, щоб перевершити будь-який окремий алгоритм. Метою цього дослідження є виявлення та оцінка різних способів реорганізації несортованих даних безпосередньо перед виконанням основного алгоритму сортування. Було розроблено та випробувано п’ять технологій попередньої обробки в поєднанні з коктейльним сортуванням, сортуванням із вставкою та швидким сортуванням. Часову ефективність оцінювали шляхом порівняння часу окремого алгоритму сортування та комбінованого алгоритму, який включає попередню обробку. Потрібне подальше вивчення методів попередньої обробки та їх впливу на різні алгоритми сортування.
Конструктивно-продукційне формування програм сортування, адаптованих генетичним алгоритмом
(Національна академія наук України, Інститут програмних систем НАН України, 2026) Шинкаренко, Віктор Іванович; Макаров, Олексій Вікторович
UKR: У попередніх роботах представлені механізми конструктивно-продукційного моделювання для адаптації алгоритмів сортування. У зв’язку з цим виникли задачі перетворення хромосом генетичного алгоритму на текст програм сортування для подальшого застосування, оцінки можливостей еволюційного розвитку. Розглядається підхід до перетворення хромосом, що кодують алгоритми сортування на тексти програм готових до застосування у реальних умовах. Розроблено конструктор-трансформер, який реалізує пере творення хромосоми-дерева на лінійну послідовність генів. Інший конструктор-трансформер призначений для перетворення послідовності генів на код програми сортування. Наведено приклади послідовності обходу дерева-хромосоми, додавання генів до лінійної послідовності і формування тексту програми. Проведено експерименти із вхідними даними різної структури і обсягів. Результати експериментів підтвердили, що запропонована методика може бути використана для автоматичної генерації ефективних алгоритмів сортування. А застосування конструктивно-продукційного моделювання у сукупності із генетичним алгоритмом дозволяє ефективно виконувати структурну адаптацію алгоритмів.
Конструювання алгоритмів сортування
(Український державний університет науки і технологій, ІВК «Системні технології», Дніпро, 2025) Макаров, Олексій Вікторович; Шинкаренко, Віктор Іванович
UKR: З розвитком цифрових технологій та збільшенням обсягів оброблюваних даних ефективність алгоритмів сортування набуває критичного значення. У роботі розглянуто еволюцію сортувальних алгоритмів від класичних до гібридних методів, зокрема Timsort та Introsort, які демонструють покращені часові характеристики та стабільність у порівнянні з традиційними підходами. Окрема увага приділена методам передобробки даних та їх впливу на продуктивність. Запропоновано підхід конструктивно-продукційного моделювання для створення адаптивних алгоритмів сортування, що дозволяє комбінувати існуючі методи та формувати нові ефективні алгоритми. Використання генетичного алгоритму у процесі конструювання дозволяє автоматизувати вибір оптимальних стратегій сортування відповідно до характеристик вхідних даних. Отримані результати підтверджують перспективність застосування конструктивно-продукційного підходу для побудови адаптивних алгоритмів сортування, що забезпечують високу продуктивність у різних умовах.
Формування алгоритмів сортування засобами конструктивно-продукційного моделювання та генетичного алгоритму
(Український державний університет науки і технологій, ІВК «Системні технології», Дніпро, 2026) Макаров, Олексій Вікторович; Шинкаренко, Віктор Іванович
UKR: Розглянуто підхід до автоматизованого синтезу алгоритмів сортування на основі конструктивно‑продукційного моделювання. Описано конструктивну модель хромосоми деревовидної структури, яка кодує алгоритм сортування у вигляді ієрархічної композиції алгоритмічних фрагментів і допоміжних операцій. Представлено систему з трьох взаємопов’язаних конструкторів: конструктора формування хромосоми‑дерева, конструктора‑трансформера для перетворення деревоподібної хромосоми у лінійну послідовність генів та конструктора‑ трансформера, що забезпечує генерацію програмного коду алгоритму сортування мовою програмування. Показано, що використання чотирьох етапів конструктивно‑продукційного моделювання – спеціалізації, інтерпретації, конкретизації та реалізації – дозволяє формалізувати процес переходу від абстрактного опису алгоритму до його виконуваної програмної реалізації. Застосування генетичного алгоритму забезпечує еволюційний відбір та оптимізацію алгоритмів сортування за заданими критеріями якості з урахуванням властивостей вхідних даних і обмежень обчислювального середовища. Запропонований підхід створює умови для структурної адаптації алгоритмів, поєднання базових алгоритмічних примітивів у нові коректні композиції та розширення простору пошуку ефективних алгоритмічних рішень. Отримані результати підтверджують доцільність використання конструктивно‑продукційного моделювання як основи для автоматизованого синтезу та оптимізації алгоритмів сортування.