Дисертації (ІПІ)
Постійне посилання зібрання
У зібранні розміщено дисертації, які захищені працівниками кафедри.
Переглянути
Нові надходження
Документ Відкритий доступ Мова програмування та програмні засоби опису агентних моделей розповсюдження інфекційних захворювань(КПІ ім. Ігоря Сікорського, 2023) Сарнацький, Владислав Віталійович; Баклан, Ігор ВсеволодовичСарнацький В.В. Мова програмування та програмні засоби опису агентних моделей розповсюдження інфекційних захворювань. – Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 121 – Інженерія програмного забезпечення та 12 – Інформаційні технології. – Національний Технічний Університет України «Київський Політехнічний Інститут імені Ігоря Сікорського», Київ, 2023. Дисертаційна робота присвячена розробці інструментального забезпечення для ефективного моделювання процесів розповсюдження інфекційних захворювань. Висвітлено основні напрями та тенденції розвитку сфери епідеміологічного моделювання у цілому та зокрема процесу розробки агентних епідеміологічних моделей. Були виявлені переваги та недоліки запропонованих дослідницькою спільнотою рішень та, зокрема, обсяг, гнучкість та швидкодія програмних засобів моделювання. Серед програмних засобів моделювання не було помічено представників, що поєднують у собі доступний інтерфейс з високою швидкодією та гнучкістю опису моделей. Був зроблений висновок, що розробка предметно-орієнтованої мови програмування для опису агентних моделей та графічного середовища розробки та аналізу нададуть доступний інтерфейс опису моделі у поєднанні зі значною гнучкістю та швидкодією. Виконана побудова загального математичного апарату епідеміологічної моделі агентного типу. У рамках математичної моделі була сформульована основна складність агентного епідеміологічного моделювання, а саме урахування контактів під час обчислення розподілу майбутнього стану захворювання. Запропоновано три алгоритми обчислення цього розподілу, проаналізована їх алгоритмічна складність. Також, для одного з них – алгоритму з групуванням було виконане дослідження оптимальної його імплементації. З огляду на розроблену математичну модель було дано визначення формальної граматики предметно-орієнтованої мови опису агентної епідеміологічної моделі CTrace. Мова надає вбудований високорівневий інтерфейс для задання основних сутностей заданої загальної епідеміологічної моделі, а також відношень між ними. Мова підтримує задання ймовірнісних розподілів різного типу та основні операції між ними що значно спрощує задання соціодемографічної параметризації моделей. Виконана побудова транслятора розробленої формальної мови опису агентної епідеміологічної моделі. Розроблений транслятор є компілятором із конфігурованою проміжною мовою. Такою мовою може бути Python, який своєю чергою транслюється у мову машинних інструкцій під час процесу JIT-компіляції, або будь-яка мова загального призначення, що має інтерфейс до побудови Pythonмодулів. Такою мовою була обрана мова Rust. Основним аспектом алгоритму трансляції є мінімізація кількості виділень пам’яті у процесі виконання результівної програми. Для цього, компілятор обраховує загальний обсяг пам’яті, необхідний для роботи моделі, і використовує буфер відповідного розміру для організації усіх обчислень. Розроблене середовище розробки та аналізу агентних епідеміологічних моделей з використанням мови CTrace – CTraceEnv. Розроблене середовище надає базовий функціонал необхідний для підтримки процесу опису моделей мовою CTrace, що включає підсвітку синтаксису вихідного коду, вбудований транслятор тощо. Серед функціоналу аналізу представлені елементи керування роботою моделі, значень її глобальних параметрів, інтерфейс перегляду динаміки розповсюдження досліджуваного інфекційного захворювання, а також функціонал експорту результатів для подальшого аналізу сторонніми спеціалізованими інструментами. Проведений аналіз розробленої мови опису агентних епідеміологічних моделей з боку доцільності її використання, обсягу сценаріїв, що можуть бути змодельовані, ефективності розробки та використання Виконана практична апробація розробленого інструментарію для ефективного моделювання розповсюдження інфекційних захворювань. У її рамках, було дано визначення агентної епідеміологічної моделі розповсюдження коронавірусу SARS-CoV-2 серед населення Польщі у період з початку вересня 2020 року до кінця листопада 2020 року, що була відкалібрована з використанням публічно доступних епідеміологічних даних. Результівна модель описує динаміку зміни кількості інфікованих людей з коефіцієнтом детермінації рівним 0.9319, що свідчить про здатність розробленого підходу описувати процеси розповсюдження інфекційних захворювань. Проведений аналіз впливу соціодемографічної гетерогенності середовища моделювання на якість карантинних стратегій побудованих на його основі. Відповідний експеримент полягав у реалізації алгоритму пошуку карантинних стратегій для заданої агентної епідеміологічної моделі країни Європейського Союзу. Соціодемографічна параметризація моделі побудована з використанням статистичного моделювання на основі відкритих історичних даних, з відкритої бази статистичних даних Eurostat. Знайдені алгоритмом стратегії були порівняні із тривіальними, що показало більшу їх ефективність та використані у процесі перехресного порівняння. Для цього, стратегія, отримана з моделі країни тестування була порівняна з іншими. В обох випадках критерієм порівняння виступала сумарна винагорода за дії агента, що використовує відповідну стратегію у середовищі моделювання, сформульованим як Марківський процес вирішення. Аналіз показав, що для покращення їх якості соціодемографічні показники мають бути ураховані, що, своєю чергою, показує необхідність наявності їх задання у будь-якому інструменті епідеміологічного моделювання. Це свідчить про доцільність тої уваги, що була приділена процесу їх задання при розробці мови CTrace. Окремо був проведений якісний аналіз спектра сценаріїв, що можуть бути змодельовані з використанням мови CTrace. Показано моделювання таких аспектів агентного епідеміологічного моделювання як: динамічні параметри моделі та її сутностей, географія середовища, погодні умови, векторні захворювання. Аналіз ефективності розробки епідеміологічних моделей мовою CTrace показав значне скорочення обсягу вихідного коду програми у порівнянні з моделями імплементованими мовами програмування загального призначення. В якості цих моделей, був використаний лістинг програмного коду проміжною мовою, що генерується транслятором. Скорочення обсягу програмного коду становило від 14 до 34 разів для мови Python та від 16 до 45 разів для мови Rust. Це скорочення може свідчити про зменшення кількості людино-годин необхідних для їх розробки, а також збільшену швидкість ітерування. Окрім цього, зменшення обсягу вихідного коду призводить до зменшення кількості помилок, що, своєю чергою, зменшує час опису моделей. Дано визначення метрики функціональності інструменту епідеміологічного моделювання, що дозволяє оцінити обсяг сценаріїв та функцій доступних користувачу. Дано визначення метрики ефективності моделі, що дозволяє виконувати порівняння різних моделей та інструментів моделювання з точки зору їх обчислювальної ефективності. Ця метрика є інваріантною до кількості агентів, тривалості симуляції, її гранульованості та кількості одночасно залучених до обчислення моделі ядер центрального процесору. Аналіз швидкодії результівних моделей, заданих мовою CTrace, ставив дві мети: обґрунтувати доцільність використання мови Python як проміжної мови трансляції, а також порівняти їх швидкодію з наявними моделями. Показано, що використання мови Python з бібліотекою для JIT-компіляції Numba дозволяє отримати швидкодію моделей, порівняну з отриманою у разі використання мови Rust, ефективність якої порівняна з C/C++. При цьому, гнучкість мови Python дозволяє відносно просто вносити корективи у процес трансляції. Експерименти з використанням різних тестових середовищ показали, що існуючі епідеміологічні моделі не виграють у швидкодії у розроблених мовою CTrace еквівалентів. З результатів порівняння розробленого середовища CTraceEnv з аналогами за визначеними метриками ефективності та функціональності можна зробити висновок що обсяг функцій агентного епідеміологічного моделювання наданий CTraceEnv є значно більшим за аналоги й приблизно відповідає середовищу NetLogo, надаючи при цьому ефективність результівних моделей, що не програє аналогам.Документ Відкритий доступ Методи та програмні засоби багатовимірної поліноміальної регресії за надлишковим описом на основі побудови одновимірної регресії з використанням ортогональних поліномів Форсайта(КПІ ім. Ігоря Сікорського, 2023) Головченко, Максим Миколайович; Павлов, Олександр АнатолійовичГоловченко М.М. Методи та програмні засоби багатовимірної поліноміальної регресії за надлишковим описом на основі побудови одновимірної регресії з використанням ортогональних поліномів Форсайта. – Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 121 – Інженерія програмного забезпечення з галузі знань 12 – Інформаційні технології. – Національний Технічний Університет України «Київський Політехнічний Інститут імені Ігоря Сікорського», Київ, 2023. Дисертаційна робота присвячена розробці універсального синтетичного методу оцінок коефіцієнтів багатовимірної поліноміальної регресії, заданої надлишковим описом та створенням оригінальних програмних засобів, що ефективно реалізують цей метод. У процесі розробки та дослідження ефективності синтетичного методу були отримані такі результати. Вперше розроблено синтетичний метод побудови багатовимірної поліноміальної регресії, заданої надлишковим описом, що відрізняється від існуючих тим, що органічно поєднує риси класичного методу (теоретично обґрунтовані випадки, в яких оцінка коефіцієнтів при нелінійних членах знаходиться з заданою точністю) з ефективністю евристичних методів (знаходження структури регресії з використанням перевірочної послідовності в модифікованому методі групового урахування аргументів, що входить в склад синтетичного методу), а також включає в себе метод побудови одновимірної поліноміальної регресії на основі довільного повторного активного експерименту з використанням лише одного набору нормованих ортогональних поліномів Форсайта, декомпозиційний метод оцінки коефіцієнтів при нелінійних членах багатовимірної поліноміальної регресії з наперед заданою точністю, що багатовимірну задачу зводить до послідовної побудови відповідних одновимірних поліноміальних регресій. Вперше обґрунтовано можливість знаходження нормованих ортогональних поліномів Форсайта з наперед заданою точністю, яка досягається за рахунок представлення даних у вигляді раціональних дробів та застосування до них символьних обчислень, що дозволяє отримати оцінки коефіцієнтів при нелінійних членах багатовимірної поліноміальної регресії, значення яких відповідають теоретично виведеним умовам. Вперше приведено теоретичне обґрунтування зменшення обчислювальної складності програмного забезпечення реалізації методу найменших квадратів на основі повторних експериментів, що полягає в заміні операцій з матрицями повного активного експерименту операціями з матрицями основного експерименту суттєво меншої розмірності. Вперше запропоновано архітектуру кросплатформної бібліотеки для реалізації синтетичного методу та його складових, яка дозволяє використовувати її компоненти, як окремо, так і в цілому для розв'язання прикладних задач побудови регресійних моделей. Проведено дослідження ефективності алгоритмів, що реалізують операції з матрицями в методі найменших квадратів, зокрема обґрунтовано можливість використання паралельних обчислень. Розглядаються матричні операції, які входять у формулу для знаходження оцінок коефіцієнтів багатовимірної поліноміальної регресії методом найменших квадратів як складової модифікованого методу групового урахування аргументів та можуть виконуватись ефективніше при застосуванні паралельних обчислень. Було виконано дослідження ефективності алгоритмів множення матриць та обернення матриць, як складових задачі знаходження оцінок коефіцієнтів багатовимірної поліноміальної регресії модифікованим методом групового урахування аргументів. Це дослідження ефективності алгоритмів виконувалось шляхом реалізації алгоритмів на базі 8-ми ядерного мікропроцесора Apple M1 та фіксації часу роботи різних алгоритмів для фіксованої кількості потоків та квадратних матриць заданої розмірності. Приведено обґрунтування можливості розпаралелювання обчислень в модифікованому методі групового урахування аргументів для знаходження оцінок коефіцієнтів часткових описів та залишкових сум квадратів. Реалізовано кросплатформну бібліотеку та її програмний інтерфейс для побудови регресійних моделей. Так, для користувачів, які володіють базовими навичками у області програмування і статистичного аналізу та бажають отримати розв’язок задачі побудови багатовимірної поліноміальної регресії достатньо у автоматизованому режимі підключити кросплатформну бібліотеку у власний застосунок та передати у її функції бібліотеки вхідні дані. В цьому випадку функції кросплатформної бібліотеки аналізують надлишковий опис і визначають, що він відноситься до класу, у якому всі лінійні системи мають лише одну змінну, якщо це не так, то задача розв’язується повністю модифікованим методом групового урахування аргументів. У протилежному випадку, програма аналізує можливості декомпозиційного методу та видає вимоги для проведення відповідної кількості повторних активних експериментів для побудови одновимірних поліноміальних регресій та множину коефіцієнтів, які будуть оцінені. Далі формується багатовимірна поліноміальна регресія задана надлишковим описом, яка буде розв’язана модифікованим методом групового урахування аргументів. Для користувачів, які володіють розширеними навичками у області програмування і статистичного аналізу та бажають отримати розв’язок задачі побудови багатовимірної поліноміальної регресії, повинні ознайомитись з детальною інструкцією по роботі з кросплатформною бібліотекою, у якій описані теоретичні положення та практичні рекомендації з використання синтетичного методу. Далі користувачі за допомогою функцій кросплатформної бібліотеки у частині декомпозиційного методу можуть запрограмувати індивідуальний алгоритм розв’язку задачі на основі теоретичних положень синтетичного методу. У частині модифікованого методу групового урахування аргументів все залишається без змін. За результатами виконання синтетичного методу користувачу буде виданий кінцевий результат, який містить структуру багатовимірної поліноміальної регресії, знайдені декомпозиційним методом оцінки коефіцієнтів багатовимірної поліноміальної регресії та їх дисперсії та оцінки коефіцієнтів багатовимірної поліноміальної регресії з оцінками їх дисперсій, знайдені за допомогою модифікованого методу групового урахування аргументів, з оцінкою результатів – має високу ступінь достовірності; задовільну ступінь достовірності; результат недостовірний. При розробці кросплатформної бібліотеки, що реалізує синтетичний метод, використовувались такі допоміжні засоби. В якості мови реалізації кросплатформної бібліотеки була обрана Python, оскільки дана мова програмування краще за інші підходить для реалізації data science та статистичних методів обробки даних. Крім того для мови Python існує великий набір високорівневих фреймворків різного призначення та програмних бібліотек, які можна використовувати у якості допоміжних засобів при розробці. Середовищем розробки кросплатформної бібліотеки було обрано IntelliJ IDEA через наявність безкоштовної експрес-версії та зручність встановлення допоміжних програмних пакетів та бібліотек. У якості архітектури кросплатформної бібліотеки було використано монолітну архітектуру, оскільки решта архітектур програмного забезпечення – багаторівнева, клієнт-серверна, мікросервісна, сервісно-орієнтована – не рекомендується для використання при розробці такого роду програмного забезпечення. Внутрішня логіка бібліотеки побудована з використанням компонентно-орієнтованого підходу, так як даний підхід добре себе зарекомендував при розробці програмного забезпечення цільового призначення, що використовується при розробці цільового прикладного програмного забезпечення. В якості пакету для паралельної реалізації деяких підалгоритмів було використано multiprocessing, а для реалізації символьних обчислень було використано бібліотеку SymPy. Для розгортання кросплатформної бібліотеки було використано систему управління пакетами pip. Це універсальна, зручна і найбільш популярна система управління пакетами, написаними для мови програмування Python. В результаті розгортання користувачі зможуть завантажувати і встановлювати бібліотеку для своїх потреб командою pip install regression_lib_mpr у своєму середовищі розробки. Дисертаційна робота складається зі вступу, чотирьох розділів, загальних висновків, списку використаних джерел із 84 найменувань на дев’яти сторінках та чотирьох додатків. Загальний обсяг дисертації становить 185 сторінок, з яких 128 сторінок основного тексту, містить 23 рисунки та 24 таблиці.Документ Відкритий доступ Методи візуального програмування Петрі-об'єктних моделей(КПІ ім. Ігоря Сікорського, 2022) Дифучин, Антон Юрійович; Жаріков, Едуард В‘ячеславовичДисертаційна робота присвячена розробці методів та засобів візуального програмування моделей дискретно-подійних систем, формалізованих у вигляді Петрі-об‘єктної моделі. Візуальне програмування є способом розробки програм, що використовує візуальні об‘єкти для опису завдання на виконання обчислень. Для того, щоб візуальне представлення стало візуальним програмуванням необхідно гарантувати однозначне перетворення візуального представлення у обчислення. Таку однозначність перетворення гарантує розробка формальної мови програмування. На сьогоднішній день положення теорії формальних мов сформульовані в припущенні, що мова є текстовою, і адаптації цих положень до мови програмування, в якій символами є елементи візуального представлення, є невирішеним завданням. Особливе місце візуальні засоби представлення займають у програмних засобах з імітаційного моделювання, оскільки слугують не тільки для конструювання моделі, але й для її відлагодження та представлення кінцевого результату імітації. Існуючі програмні засоби з імітаційного моделювання широко застосовують графічні редактори для конструювання моделі з блоків або з більш низькорівневих елементів, наприклад, елементів мережі Петрі. Процес розробки моделі у графічному редакторі є трудомістким і довготривалим, а у випадку великої кількості елементів часто є неможливим, оскільки потребує великого обсягу рутинної роботи з елементами та налаштуванням їх параметрів. Імітаційні моделі є одним з потужних інструментів обробки даних з метою пошуку оптимальних умов або короткострокового прогнозування. У поєднанні з даними, що постачаються у реальному часі, вони можуть стати потужним компонентом сучасних систем прийняття рішень та управління. Тому розробка нових методів та програмних засобів, що спрямовані на підвищення ефективності процесу програмної реалізації моделі за рахунок автоматизації кодування, є актуальним науковим завданням. Метою наукового дослідження є підвищення ефективності програмних засобів представлення складних моделей систем для цілей імітаційного моделювання за рахунок зменшення складності конструювання моделі та збільшення швидкодії алгоритмів імітації, зручності сприйняття моделі, зменшення кількості помилок при створенні зв‘язків між елементами моделі та зменшення часу на модифікацію моделі. У першому розділі наведено огляд існуючих програмних засобів моделювання систем стохастичними мережа Петрі та обґрунтовано розробку мови візуального програмування. Виявлено, що графічні редактори не вирішують низку проблем: неможливість коригування параметрів моделі без коригування її візуального представлення, неможливість тиражування однотипних елементів у великій кількості (оскільки усі вони будуть займати візуальний простір), неможливість тиражування зв‘яків при повторному використанні фрагментів мережі Петрі, неможливість налаштування параметрів елементів без коригування кожного окремого параметра у спеціально відведеному для цього вікні. У другому розділі наведені відомості з теорії стохастичних мереж Петрі та основні теоретичні положення Петрі-об‘єктного моделювання. Формальний опис Петрі-об‘єктної моделі розвинутий за рахунок введення понять конектора Петрі-об‘єктів, групи Петрі-об‘єктів, колекції Петрі-об‘єктів. Введені поняття відкривають можливість тиражування зв‘язків при конструюванні Петріоб‘єктної моделі. Проте відсутність візуального представлення моделі робить процес розробки моделі складним через рутинні та схильні до помилок операції кодування зв‘язків між елементами. У третьому розділі представлена формальна граматика мови Петріоб‘єктного моделювання, яка розроблена. Алфавіт мови складається з графічних елементів візуального представлення, а дозволені мовою набори графічних елементів утворюють лексеми мови. Синтаксис мови визначений правилами виведення граматики, в основі яких правила утворення триплетів елементів. Для розробленої контекстно-вільної граматики встановлено, що вона є однозначною і приведеною. Наведений приклад розробки моделі інформаційної системи розробленою мовою. У четвертому розділі представлена розробка транслятора мови візуального програмування Петрі-об‘єктних моделей. На клієнтській частині веб застосування реалізована частина транслятора, що відповідає за лексичний та синтаксичний аналіз мовного виразу. На серверній частині веб застосування реалізована частина транслятора, що виконує семантичний аналіз мовного виразу. Для передачі даних між клієнтом та сервером використовується JSON формат. У розділі представлена інтерпретація символів алфавіту мови візуального програмування Петрі-об‘єктних моделей мовою TypeScript. Запуск на обчислення відбувається після перетворення отриманих у форматі JSON даних в об‘єкт PetriObjModel бібліотеки Петрі-об‘єктного моделювання PetriObjLIb. Обчислення Петрі-об‘єктної моделі – це відтворення подій в часі алгоритмом імітації. П’ятий розділ містить результати експериментального дослідження процесу розробки моделей, точності моделювання та швидкодії обчислення моделі. Результати, отримані у дисертаційному дослідженні, містять наукову новизну. Вперше розроблено візуальну мову програмування Петрі-об‘єктних моделей, яка дозволяє спростити процес побудови моделей, підвищити наочність сприйняття моделей та час виконання імітаційного моделювання шляхом організації дворівневого способу побудови моделей. На відміну від існуючих рішень в області імітаційного моделювання, візуальна мова програмування Петрі-об‘єктних моделей надає універсальний та гнучкий інструмент для побудови моделей дискретно-подійних систем, а процес виконання імітаційного моделювання не залежить від обчислювальних ресурсів користувача. Удосконалено Петрі-об‘єктну модель за рахунок введення поняття групи Петрі-об‘єктів, колекції Петрі-об‘єктів та групи колекцій Петрі-об‘єктів, що, на відміну від існуючих засобів представлення імітаційної моделі, надають можливість тиражувати Петрі-об‘єкти з заданими наборами параметрів, тиражувати колекції взаємопов‘язаних Петрі-об‘єктів та тиражувати зв‘язки між Петрі-об‘єктом та групою Петрі-об‘єктів, між Петрі-об‘єктом та групою колекцій Петрі-об‘єктів. За рахунок тиражування однотипних фрагментів моделі та тиражування зв‘язків створюються умови для швидкого конструювання моделей з великою кількістю елементів та значно скорочується обсяг їх візуального представлення. Вперше запропоновано клієнт-серверну архітектуру серед програмного забезпечення з імітаційного моделювання на основі Петрі-об‘єктного підходу, використання якої дозволяє задіяти ресурси віддаленого серверу для проведення імітаційного моделювання для забезпечення стабільного часу виконання, зменшення витрат на інфраструктуру обчислювальних ресурсів серед користувачів та організації спільного доступу до розробки моделей. Результати дисертаційної роботи опубліковано у 7 наукових публікаціях, серед яких 1 стаття у періодичному науковому виданні, проіндексованому у Web of Science Core Collection та Scopus базах даних, 2 статті у фаховому науковому журналі категорії «Б», 1 стаття у фаховому науковому журналі категорії «В», 1 стаття у науковому журналі, проіндексованому GoogleScholar, 2 публікації у матеріалах міжнародних наукових конференцій, проіндексованих у Scopus.