Система визначення часової складності програмних алгоритмів

Скорочена інформація про документ
dc.contributor.advisorКоляда, Костянтин В'ячеславович
dc.contributor.authorЧорний, Єгор Геннадійович
dc.date.accessioned2020-07-12T15:35:20Z
dc.date.available2020-07-12T15:35:20Z
dc.date.issued2020-06
dc.description.abstractПояснювальна записка містить 50 сторінки, 2 таблиці, 6 рисунків, 20 джерел. Об’єкт дослідження – система визначення часової складності програмних алгоритмів. Предмет дослідження – типи часової складності алгоритмів, методи її визначення та призначення. Мета роботи – аналіз відомих типів часової складності та методів її визначення, дослідження призначення і можливості використання отриманих даних часової складності алгоритмів, розробка програмного забезпечення для статистичного аналізу алгоритмів і визначення часової складності їх структурних одиниць. Метод дослідження – вивчення літератури, аналіз відомих типів часової складності та способів її визначення, дослідження статистичного аналізу алгоритмів, середовища створення програмного забезпечення та його розробка, аналіз отриманих результатів і написання висновків. В процесі розробки були проаналізовані існуючі інструменти для парсинга коду заданої граматики (ANTLR4), використання мови програмування Common Lisp для розробки серверної частини програми, а також використання мови Java для розробки користувацького інтерфейсу. Технічне завдання було розділене на структурні частини для розподілення роботи на етапи. Схема взаємодії програмних модулів була сформована на основі принципів архітектури MVC (Module View Control), що дозволило підвищити ефективність розробки. Дана реалізація програмного комплексу дозволяє досить легко додавати нові модулі, що реалізують підтримку нових можливостей програми. Розроблена програма приймає на вхід файли з граматикою та кодом, що підлягає аналізу. Для тестування була розроблена тестова граматика. Процес роботи програми розроблений таким чином, що за допомогою вхідної граматики з вхідного коду створюється дерево розбору на якому проводиться аналіз часової складності після приведення структури дерева розбору до графа потоку керування програми. Було проведено ряд тестів, практичний результат яких співпав з теоретичними розрахунками.uk
dc.description.abstractenThe explanatory note contains 50 pages, 2 tables, 6 figures, 20 sources. The object of research is a system for determining the temporal complexity of software algorithms. The subject of research - types of time complexity of algorithms, methods of its definition and purpose. The purpose of the work - analysis of known types of temporal complexity and methods of its determination, study of the purpose and possibility of using the obtained data of temporal complexity of algorithms, development of software for statistical analysis of algorithms and determination of temporal complexity of their structural units. Research method - studying the literature, analysis of known types of time complexity and methods of its determination, research of statistical analysis of algorithms, software creation environment and its development, analysis of the obtained results and writing conclusions. During the development process, the existing tools for parsing the code of a given grammar (ANTLR4), the use of the programming language Common Lisp to develop the server part of the program, as well as the use of Java language to develop the user interface were analyzed. The terms of reference were divided into structural parts to divide the work into stages. The scheme of interaction of software modules was formed on the basis of the principles of MVC architecture (Module View Control), which allowed to increase the efficiency of development. This implementation of the software package allows you to easily add new modules that implement support for new features of the program. The developed program accepts files with grammar and code to be analyzed. A test grammar was developed for testing. The operation of the program is designed in such a way that with the help of input grammar from the input code creates a parsing tree, which analyzes the time complexity after bringing the structure of the parsing tree to the graph of the control flow of the program. A number of tests were conducted, the practical result of which coincided with the theoretical calculations.uk
dc.format.page66 с.uk
dc.identifier.citationЧорний, Є. Г. Система визначення часової складності програмних алгоритмів : дипломний проєкт ... бакалавра : 123 Комп'ютерна інженерія / Чорний Єгор Геннадійович. – Київ, 2020. – 66 с.uk
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/34971
dc.language.isoukuk
dc.publisherКПІ ім. Ігоря Сікорськогоuk
dc.publisher.placeКиївuk
dc.subjectалгоритмuk
dc.subjectобчислювальна складністьuk
dc.subjectчасова складність алгоритмуuk
dc.subjectтип складностіuk
dc.subjectграф потоку керування програмиuk
dc.subjectформальна граматикаuk
dc.subjectANTLRuk
dc.subjectalgorithmuk
dc.subjectcomputational complexityuk
dc.subjecttime complexity of the algorithmuk
dc.subjecttype of complexityuk
dc.subjectprogram control flow graphuk
dc.subjectformal grammaruk
dc.titleСистема визначення часової складності програмних алгоритмівuk
dc.typeBachelor Thesisuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
Chornyi-Ye-H_bakalavr.pdf
Розмір:
1.28 MB
Формат:
Adobe Portable Document Format
Опис:
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
9.06 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Бакалаврські роботи (СПСКС)
Бакалаврські роботи