Система визначення часової складності програмних алгоритмів
Вантажиться...
Дата
2020-06
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Пояснювальна записка містить 50 сторінки, 2 таблиці, 6 рисунків, 20 джерел.
Об’єкт дослідження – система визначення часової складності програмних алгоритмів.
Предмет дослідження – типи часової складності алгоритмів, методи її визначення та призначення.
Мета роботи – аналіз відомих типів часової складності та методів її визначення, дослідження призначення і можливості використання отриманих даних часової складності алгоритмів, розробка програмного забезпечення для статистичного аналізу алгоритмів і визначення часової складності їх структурних одиниць.
Метод дослідження – вивчення літератури, аналіз відомих типів часової складності та способів її визначення, дослідження статистичного аналізу алгоритмів, середовища створення програмного забезпечення та його розробка, аналіз отриманих результатів і написання висновків.
В процесі розробки були проаналізовані існуючі інструменти для парсинга коду заданої граматики (ANTLR4), використання мови програмування Common Lisp для розробки серверної частини програми, а також використання мови Java для розробки користувацького інтерфейсу. Технічне завдання було розділене на структурні частини для розподілення роботи на етапи. Схема взаємодії програмних модулів була сформована на основі принципів архітектури MVC (Module View Control), що дозволило підвищити ефективність розробки. Дана реалізація програмного комплексу дозволяє досить легко додавати нові модулі, що реалізують підтримку нових можливостей програми.
Розроблена програма приймає на вхід файли з граматикою та кодом, що підлягає аналізу. Для тестування була розроблена тестова граматика. Процес роботи програми розроблений таким чином, що за допомогою вхідної граматики з вхідного коду створюється дерево розбору на якому проводиться аналіз часової складності після приведення структури дерева розбору до графа потоку керування програми.
Було проведено ряд тестів, практичний результат яких співпав з теоретичними розрахунками.
Опис
Ключові слова
алгоритм, обчислювальна складність, часова складність алгоритму, тип складності, граф потоку керування програми, формальна граматика, ANTLR, algorithm, computational complexity, time complexity of the algorithm, type of complexity, program control flow graph, formal grammar
Бібліографічний опис
Чорний, Є. Г. Система визначення часової складності програмних алгоритмів : дипломний проєкт ... бакалавра : 123 Комп'ютерна інженерія / Чорний Єгор Геннадійович. – Київ, 2020. – 66 с.