Пошук академічних текстів

Інформація × Реєстраційний номер 2120U008149, Матеріали видань та локальних репозитаріїв Категорія Бакалаврська робота Назва роботи Система визначення часової складності програмних алгоритмів Автор Чорний Єгор ГеннадійовичChornyi Yehor Hennadiiovych Дата публікації 01-06-2020 Постачальник інформації Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського» Першоджерело https://ela.kpi.ua/handle/123456789/34971 Видання Київ Опис Пояснювальна записка містить 50 сторінки, 2 таблиці, 6 рисунків, 20 джерел. Об’єкт дослідження – система визначення часової складності програмних алгоритмів. Предмет дослідження – типи часової складності алгоритмів, методи її визначення та призначення. Мета роботи – аналіз відомих типів часової складності та методів її визначення, дослідження призначення і можливості використання отриманих даних часової складності алгоритмів, розробка програмного забезпечення для статистичного аналізу алгоритмів і визначення часової складності їх структурних одиниць. Метод дослідження – вивчення літератури, аналіз відомих типів часової складності та способів її визначення, дослідження статистичного аналізу алгоритмів, середовища створення програмного забезпечення та його розробка, аналіз отриманих результатів і написання висновків. В процесі розробки були проаналізовані існуючі інструменти для парсинга коду заданої граматики (ANTLR4), використання мови програмування Common Lisp для розробки серверної частини програми, а також використання мови Java для розробки користувацького інтерфейсу. Технічне завдання було розділене на структурні частини для розподілення роботи на етапи. Схема взаємодії програмних модулів була сформована на основі принципів архітектури MVC (Module View Control), що дозволило підвищити ефективність розробки. Дана реалізація програмного комплексу дозволяє досить легко додавати нові модулі, що реалізують підтримку нових можливостей програми. Розроблена програма приймає на вхід файли з граматикою та кодом, що підлягає аналізу. Для тестування була розроблена тестова граматика. Процес роботи програми розроблений таким чином, що за допомогою вхідної граматики з вхідного коду створюється дерево розбору на якому проводиться аналіз часової складності після приведення структури дерева розбору до графа потоку керування програми. Було проведено ряд тестів, практичний результат яких співпав з теоретичними розрахунками. The 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. Додано в НРАТ 2025-11-05 Закрити