Спосіб оцінювання обчислювальної складності алгоритмів за критерієм часу виконання асемблерних інструкцій

Скорочена інформація про документ
dc.contributor.advisorМарченко, Олександр Іванович
dc.contributor.authorЧорний, Єгор Геннадійович
dc.date.accessioned2022-01-19T10:14:21Z
dc.date.available2022-01-19T10:14:21Z
dc.date.issued2021
dc.description.abstractenRelevance of the topic. Understanding the complexity of the algorithm is an important aspect in the process of developing any software, because it allows you to talk about the effectiveness of the software system and look for ways to improve it. By determining the complexity of the algorithms used, it becomes possible to identify performance issues throughout the software system before they actually affect the system after it is deployed. There are many ways to estimate the computational complexity of algorithms: LOC-metric, Halsted's metric, cyclomatic complexity metric, Chepin's metric and others. Their combination allows you to thoroughly and comprehensively assess the complexity of the algorithm. However, all of the above evaluation methods do not take into account the properties of the processor on which the algorithm will run. Each program algorithm to be executed by its processor will be converted into a set of assembler instructions. This set of commands can be obtained quite easily, using the capabilities of modern integrated development environments or third-party translators, which are freely available for the vast majority of modern high-level programming languages. This paper proposes another method of estimating computational complexity, which takes into account the characteristics of the processor, namely the execution time of the assembly instructions. The purpose of the study: to develop a method for estimating the computational complexity of the algorithm by the criterion of the execution time of assembly instructions. The object of research is the computational complexity of algorithms. The subject of research is ways to assess the computational complexity of algorithms. Research methods: study of existing methods of estimating the computational complexity of algorithms, study of the characteristics of the algorithm on which the estimation data are based. The scientific novelty is to create a method for estimating the computational complexity of the algorithm, which takes into account the characteristics of the processors on which the algorithm will run. The practical value lies in the ability to take into account the characteristics of the processor when estimating the computational complexity of the algorithm. Approbation of dissertation results. The main provisions and results of the work were presented at the scientific conference "XIV scientific-practical conference of undergraduates and graduate students of PMK-2021 of the Faculty of Applied Mathematics". Publications. The results of the dissertation are presented in scientific works, including: - XIV scientific-practical conference of undergraduates and graduate students of PMK-2021 of the Faculty of Applied Mathematics; - XV International Scientific and Practical Conference "Modern Information and Communication Technologies in Transport, Industry and Education". Structure and scope of work. The master's dissertation is executed on 80 sheets, it contains the list of references to the used sources from X names. The paper presents X figures, X tables. The work consists of an introduction, four chapters and conclusions. The introduction presents the general characteristics of the work, the prerequisites for its implementation, its relevance and objectives. The first section provides basic definitions for estimating the complexity of algorithms. The second section compares the methods of estimating the computational complexity of algorithms and justifies the choice of research topics. The third section describes the proposed method of calculating the computational complexity of the algorithm by the criterion of the execution time of assembly instructions. In the fourth section of the explanatory note the testing of the developed estimation method is carried out, the comparative analysis of the offered method with already existing and the comparative analysis of various algorithms on the basis of the offered estimation is carried out.uk
dc.description.abstractukАктуальність теми. Розуміння складності алгоритму є важливим аспектом у процесі розробки будь-якого програмного забезпечення, адже завдяки цьому можна говорити про ефективність програмної системи та шукати шляхи її покращення. За допомогою визначення складності використаних алгоритмів, стає можливим виявлення проблем, пов’язаних з продуктивністю усієї програмної системи, ще до того, як вони фактично вплинуть на цю систему після її розгортання. Існує значна кількість способів оцінки обчислювальної складності алгоритмів: LOC-метрика, метрики Холстеда, метрика цикломатичної складності, метрика Чепіна та інші. Їх комбінація дають змогу досить ґрунтовно та багатогранно оцінювати складність алгоритму. Але всі вище вказані способи оцінки не враховують властивості процесора, на якому буде виконуватись алгоритм. Кожен програмний алгоритм для виконання його процесором буде перетворений в набір інструкцій асемблера. Цей набір команд можна отримати досить легко, використовуючи можливості сучасних інтегрованих середовищ розробки або сторонніх трансляторів, що є у вільному доступі для переважної більшості сучасних мов програмування високого рівня. В даній роботі запропоновано інший спосіб оцінки обчислювальної складності, який врахує особливості процесора, а саме час виконання інструкції асемблера. Мета дослідження: розробка способу оцінки обчислювальної складності алгоритму за критерієм часу виконання асемблерних інструкцій. Об’єктом дослідження є обчислювальна складність алгоритмів. Предметом дослідження є способи оцінки обчислювальної складності алгоритмів. Методи дослідження: дослідження існуючих способів оцінки обчислювальної складності алгоритмів, дослідження характеристик алгоритму, на яких базуються дані оцінки. Наукова новизна полягає у створенні способу оцінки обчислювальної складності алгоритму, який врахує характеристики процесорів, на яких буде виконуватись алгоритм. Практична цінність полягає в можливості врахувати характеристики процесора при оцінці обчислювальної складності алгоритму. Апробація результатів дисертації. Основні положення й результати роботи представлено на науковій конференції «XIV науково-практична конференція магістрантів та аспірантів ПМК-2021 факультету прикладної математики». Публікації. Результати дисертації викладено в наукових працях, у тому числі: - XIV науково-практична конференція магістрантів та аспірантів ПМК-2021 факультету прикладної математики; - XV міжнародна науково-практична конференція «Сучасні інформаційні та комунікаційні технології в транспорті, промисловості та освіті». Структура та обсяг роботи. Магістерська дисертація виконана на 80 аркушах, вона містить перелік посилань на використані джерела з Х найменувань. У роботі наведено Х рисунків, Х таблиць. Робота складається з вступу, чотирьох розділів та висновків. У вступі представлена загальна характеристика роботи, передумови до її виконання, її актуальність та завдання. У першому розділі даються основні визначення оцінки складності алгоритмів. У другому розділі проведено порівняльний аналіз способів оцінки обчислювальної складності алгоритмів та обґрунтовано вибір тематики дослідження. В третьому розділі описано запропонований спосіб підрахунку обчислювальної складності алгоритму за критерієм часу виконання асемблерних інструкцій. В четвертому розділі пояснювальної записки проведено тестування розробленого способу оцінки, проведено порівняльний аналіз запропонованого способу з вже існуючими та порівняльний аналіз різних алгоритмів на основі запропонованої оцінки.uk
dc.format.page94 с.uk
dc.identifier.citationЧорний, Є. Г. Спосіб оцінювання обчислювальної складності алгоритмів за критерієм часу виконання асемблерних інструкцій : магістерська дис. : 123 Комп’ютерна інженерія / Чорний Єгор Геннадійович. – Київ, 2021. – 94 с.uk
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/45949
dc.language.isoukuk
dc.publisherКПІ ім. Ігоря Сікорськогоuk
dc.publisher.placeКиївuk
dc.subjectскладність алгоритмівuk
dc.subjectобчислювальна складністьuk
dc.subjectalgorithm complexityuk
dc.subjectcomputational complexityuk
dc.subject.udc004.4uk
dc.titleСпосіб оцінювання обчислювальної складності алгоритмів за критерієм часу виконання асемблерних інструкційuk
dc.typeMaster Thesisuk

Файли

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

Зібрання

Магістерські роботи (СПСКС)
Магістерські роботи