Ukrainian Journal of Information Systems and Data Science

Різноманіття псевдовипадкових блукань шахового коня для скремблювання багатовимірних даних

Вадим Романюк — Mon, 09 Dec 2024 00:00:00 +0200

Задача відкритого циклу шахового коня полягає у побудові послідовності ходів шахового коня, яка повністю покриває шахову дошку без повторів, де початкове та кінцеве положення є завжди різними. Розв’язок задачі відкритого циклу шахового коня подібний до послідовності псевдовипадкових чисел, за якими можна відобразити дані у корисну інформацію без можливості її читання. Задача відкритого циклу шахового коня для певного стартового положення має різноманіття розв’язків, кількість яких залежить від розміру шахової дошки. Розв’язки задачі відкритого циклу шахового коня виглядають як його псевдовипадкове блукання або як випадкова послідовність його положень. Ці розв’язки використовуються для подальшого покращення балансу простоти скремблювання та продуктивності, де головними показниками є ймовірність зламу та індекс подібності. Ймовірність зламу суттєво зменшується завдяки різноманіттю псевдовипадкових блукань шахового коня для певного стартового положення на даній шаховій дошці. Песимістична оцінка ймовірності зламу для шахової дошки розміром 8×8 є меншою за 10^-16. Аналогічна оцінка для шахової дошки розміром 8×8×8 є меншою за 10^-26. Конкретна реалізація псевдовипадкового блукання шахового коня будується в режимі онлайн за заданого початкового цілого для генератора псевдовипадкових чисел. Вектор даних після скремблювання також будується в режимі онлайн за лінійної часової складності. Індекс подібності є прийнятним. Він стрімко падає зі зростанням розміру шахової дошки (для більших масивів багатовимірних даних). Конкретне псевдовипадкове блукання шахового коня визначається розміром шахової дошки, початковим положенням, методом векторизації псевдовипадкового блукання шахового коня, а також початковим цілим для генератора псевдовипадкових чисел. Ці параметри визначають специфічний рух коня у ситуаціях, коли постають множинні варіанти подальшого руху. Скремблер на основі відкритого циклу шахового коня має від 10¹⁶до 10²¹разів меншу ймовірність зламу, порівняно зі звичайним псевдовипадковим генератором, залежно від розміру шахової дошки та початкового положення шахового коня.

Дослідження ефективності розпаралелювання процесорозалежних задач мовою Python на основі механізму потоків

Бабаков Роман, Баркалов Олександр — Mon, 09 Dec 2024 00:00:00 +0200

Метою роботи є дослідження ефективності застосування паралельної обробки даних на основі потоків у мові Python для розв’язання задач, які потребують значних ресурсів центрального процесора. В якості такої задачі розглядалась задача обробки двовимірного масиву великих розмірів стандартними засобами Python без використання спеціалізованих бібліотек на кшталт Numpy. Виявлено непрогнозоване зменшення часу виконання багатопотокової програми на 30% у порівнянні з послідовною (непаралельною) реалізацією розв’язуваної задачі. Це дає змогу поставити під сумнів загальновідоме твердження про те, що багатопотокове розв’язання процесорозалежних задач саме в мові Python не є ефективним, оскільки не приводить до зменшення часу роботи програм. Раніше вважалося, що завдяки використанню так званого глобального замка (GIL) інтерпретатор мови Python у разі виконання багатопотокових програм із застосуванням модуля Threading спрямовує усі потоки програми на одне процесорне ядро, що виключає фізичне паралельне виконання потоків і за жодних умов не дає змоги зменшити час роботи програми. Відомою рекомендацією для отримання реального виграшу в часі є використання розпаралелювання на основі механізму процесів і модуля «multiprocessing», який допомагає задіяти кілька фізичних ядер процесора. Однак такий підхід потребує додаткових ресурсів процесора (ядер) та додаткових витрат часу на обмін даними між процесами, що може звести нанівець ефект від багатоядерної обробки. Проведені авторами експерименти довели, що застосування багатопотокового підходу також може бути доцільним у випадку процесорозалежних задач, оскільки виграш у часі, що досягається, не потребує додаткових ресурсів з боку центрального процесора комп’ютера та зайвих витрат часу на обмін даними між потоками.

Залежність швидкодії програм від інструментальних засобів розробки та синтаксичних конструкцій

Юрій Антонов — Mon, 09 Dec 2024 00:00:00 +0200

Запропоновано реалізацію автоматизованої інформаційної системи, що дає змогу досліджувати та аналізувати вплив інструментальних засобів розробки та синтаксичних конструкцій на швидкодію роботи програм. У системі застосовано архітектуру трирівневих баз даних. Спеціалізований додаток LST Client використано як клієнт, LST Web Service як сервер додатків, а MySQL як реляційна СУБД. Взаємодія додатка LST Client з LST Web Service відбувається за допомогою Web API з використанням Application Key. Application Key являє собою унікальний ключ, який створюється для кожного пристрою, що бере участь у дослідженні. Для тих випадків, коли у досліджені має взяти участь пристрій, розташований поза межами intranet-мережі, підключення здійснюється аналогічним способом, але через спеціально налаштований SSH-тунель. Для кожного пристрою створюється відповідний користувач з авторизацією за особистим RSA-ключем максимальної довжини. Дослідження проведено для мов програмування C, C++, Fortran, Java, C#, JavaScript, PHP, Python з використанням компіляторів та інтерпретаторів, що належать до x64 архітектури під керуванням Windows 10 для освітніх установ. Результати експериментів засвідчили, що на швидкодію програми впливає версія компілятора чи інтерпретатора, та набір синтаксичних конструкцій, що використовується, наприклад, ++i та i++. Лише компілятори мов програмування C, C++ та Fortran змогли оптимізувати код та не виконувати зайві цикли. Розроблена система дає змогу максимально автоматизувати процес тестування швидкодії програмного коду. Запропонована система може бути використана для оцінювання нових версій мов програмування та програмного забезпечення. Вона також може бути задіяна під час викладання дисциплін, пов’язаних із програмуванням, для звернення уваги студентів на слабкі та сильні місця мов програмування та інструментальних засобів розробки.

Експрес-підбір опонентів для разових рад із захисту PhD-дисертацій

Сергій Штовба, Микола Петричко — Mon, 09 Dec 2024 00:00:00 +0200

Сьогодні ради із захисту PhD-дисертацій формують у ручному режимі. Це обумовлює як корупційні ризики, так і значні витрати часу на пошук та аналіз кандидатів з великими шансами пропустити кваліфікованих опонентів. Тому виникає зацікавленість у автоматизації формування разових рад для усунення зазначених ризиків впливу людського фактора. Стаття фокусується на експрес-підборі рад, коли потрібно сильно звузити великий список кандидатів. Подальший короткий список можна аналізувати або вручну, або передавати на процедуру тонкого підбору, яка є ресурсно-витратною і вимагає значно більшого об’єму початкової інформації. Пропонується метод призначення команди рецензентів за їх відповідністю тематиці дисертації, який, на відміну від ізольованого підбору кандидатів, враховує здатність саме колективу рецензентів спільно оцінити роботу за всіма аспектами її тематики. Метод є збалансованим за критеріями якості підбору і витратами ресурсів на пошук членів ради. Метод включає три етапи. На першому етапі здійснюється категоризація дисертації та потенційних членів ради шляхом представлення їх тематик векторами у просторі наукових спеціальностей з ANZSRC-2020. На другому етапі розраховується рівень відповідності кандидатів тематиці дисертації з урахуванням спорідненості наукових спеціальностей ANZSRC-2020. На третьому етапі підбирається склад ради, яка відповідає тематиці дисертації з максимально можливим ступенем. Для реалізації третього етапу запропоновано кілька алгоритмів оптимізації. Тестування алгоритмів на сформованому датасеті із 67 PhD-дисертацій показало, що найкращий баланс за критеріями якості підбору й витрат ресурсів на пошук колективу забезпечують жадібний алгоритм без елітизму та повний перебір на прорідженій множині кандидатів. Внаслідок оптимізації вдалося покращити склад разових рад у середньому на 13–34% залежно від типу використаного алгоритму.

Методи розв’язання задачі управління запасами на основі нейро-асоціативного навчання і навчання з підкріпленням

Євген Федоров, Тетяна Уткіна, Ольга Нечипоренко — Mon, 09 Dec 2024 00:00:00 +0200

Сьогодні актуальним завданням є розробка інтелектуальних методів, спрямованих на розв’язання задач управління запасами. Багато сучасних компаній для вдосконалення та оптимізації своїх бізнес-процесів використовують технологію теорії обмежень, яка забезпечує динамічне управління буфером запасів і використовується для управління ланцюгами поставок. Метою роботи є підвищення ефективності управління запасами за допомогою нейро-асоціативного навчання на основі обмеженої машини Коші та навчання з підкріпленням на основі Q-навчання та SARSA. Для досягнення поставленої мети створено метод на основі обмеженої машини Коші для управління буфером запасів, метод на основі Q-навчання та метод на основі SARSA для загальних задач управління запасами. Запропонована нейромережева модель обмеженої машини Коші має гетероасоціативну пам’ять без обмежень на ємність і забезпечує високу точність управління буфером запасів. Модель використовує розподіл Коші, що покращує збіжність методу параметричної ідентифікації, порівняно з традиційною обмежено машиною Больцмана. На відміну від повної машини Коші, обмежена машина Коші дає змогу працювати з більшим обсягом пам'яті. Модифікація методів Q-навчання та SARSA за рахунок динамічних параметрів дає змогу підвищити швидкість навчання за заданого рівня середньоквадратичної помилки. Проведені обчислювальні експерименти показали, що керування важливістю нагороди, параметром швидкості навчання, параметром для e--жадібного підходу для методів Q-навчання та SARSA дає змогу на початкових стадіях зробити пошук рішення більш глобальним, а на заключних стадіях зробити пошук рішення більш локальним. Запропоновані методи дають змогу розширити сферу застосування нейро-асоціативного навчання та навчання з підкріпленням, що підтверджується їх адаптацією для задач управління запасами та сприяє підвищенню ефективності інтелектуальних комп’ютерних систем загального і спеціального призначення. Перспективами подальших досліджень є застосування запропонованих методів для інших задач прийняття рішень, зокрема й у області штучного інтелекту.

Титул і зміст

Tue, 10 Dec 2024 00:00:00 +0200

Журнал "Ukrainian Journal of Information Systems and Data Science", №1 за 2024 р. містить статті за напрямками: моделі прийняття рішень; інформаційні систем на основі інтренету речей; машинне навчання; інженерія знань.

Увесь випуск

Tue, 10 Dec 2024 00:00:00 +0200

Журнал "Ukrainian Journal of Information Systems and Data Science", №1 за 2024 р. містить статті за напрямками: алгоритми та структури даних; моделі прийняття рішень; машинне навчання.