Коляда, Костянтин В'ячеславовичЧорний, Єгор Геннадійович2020-07-122020-07-122020-06Чорний, Є. Г. Система визначення часової складності програмних алгоритмів : дипломний проєкт ... бакалавра : 123 Комп'ютерна інженерія / Чорний Єгор Геннадійович. – Київ, 2020. – 66 с.https://ela.kpi.ua/handle/123456789/34971Пояснювальна записка містить 50 сторінки, 2 таблиці, 6 рисунків, 20 джерел. Об’єкт дослідження – система визначення часової складності програмних алгоритмів. Предмет дослідження – типи часової складності алгоритмів, методи її визначення та призначення. Мета роботи – аналіз відомих типів часової складності та методів її визначення, дослідження призначення і можливості використання отриманих даних часової складності алгоритмів, розробка програмного забезпечення для статистичного аналізу алгоритмів і визначення часової складності їх структурних одиниць. Метод дослідження – вивчення літератури, аналіз відомих типів часової складності та способів її визначення, дослідження статистичного аналізу алгоритмів, середовища створення програмного забезпечення та його розробка, аналіз отриманих результатів і написання висновків. В процесі розробки були проаналізовані існуючі інструменти для парсинга коду заданої граматики (ANTLR4), використання мови програмування Common Lisp для розробки серверної частини програми, а також використання мови Java для розробки користувацького інтерфейсу. Технічне завдання було розділене на структурні частини для розподілення роботи на етапи. Схема взаємодії програмних модулів була сформована на основі принципів архітектури MVC (Module View Control), що дозволило підвищити ефективність розробки. Дана реалізація програмного комплексу дозволяє досить легко додавати нові модулі, що реалізують підтримку нових можливостей програми. Розроблена програма приймає на вхід файли з граматикою та кодом, що підлягає аналізу. Для тестування була розроблена тестова граматика. Процес роботи програми розроблений таким чином, що за допомогою вхідної граматики з вхідного коду створюється дерево розбору на якому проводиться аналіз часової складності після приведення структури дерева розбору до графа потоку керування програми. Було проведено ряд тестів, практичний результат яких співпав з теоретичними розрахунками.ukалгоритмобчислювальна складністьчасова складність алгоритмутип складностіграф потоку керування програмиформальна граматикаANTLRalgorithmcomputational complexitytime complexity of the algorithmtype of complexityprogram control flow graphformal grammarBachelor Thesis66 с.