Спосіб оцінювання обчислювальної складності алгоритмів за критерієм часу виконання асемблерних інструкцій
Дата
2021
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Актуальність теми. Розуміння складності алгоритму є важливим аспектом у процесі розробки будь-якого програмного забезпечення, адже завдяки цьому можна говорити про ефективність програмної системи та шукати шляхи її покращення. За допомогою визначення складності використаних алгоритмів, стає можливим виявлення проблем, пов’язаних з продуктивністю усієї програмної системи, ще до того, як вони фактично вплинуть на цю систему після її розгортання.
Існує значна кількість способів оцінки обчислювальної складності алгоритмів: LOC-метрика, метрики Холстеда, метрика цикломатичної складності, метрика Чепіна та інші. Їх комбінація дають змогу досить ґрунтовно та багатогранно оцінювати складність алгоритму. Але всі вище вказані способи оцінки не враховують властивості процесора, на якому буде виконуватись алгоритм.
Кожен програмний алгоритм для виконання його процесором буде перетворений в набір інструкцій асемблера. Цей набір команд можна отримати досить легко, використовуючи можливості сучасних інтегрованих середовищ розробки або сторонніх трансляторів, що є у вільному доступі для переважної більшості сучасних мов програмування високого рівня.
В даній роботі запропоновано інший спосіб оцінки обчислювальної складності, який врахує особливості процесора, а саме час виконання інструкції асемблера.
Мета дослідження: розробка способу оцінки обчислювальної складності алгоритму за критерієм часу виконання асемблерних інструкцій.
Об’єктом дослідження є обчислювальна складність алгоритмів.
Предметом дослідження є способи оцінки обчислювальної складності алгоритмів.
Методи дослідження: дослідження існуючих способів оцінки обчислювальної складності алгоритмів, дослідження характеристик алгоритму, на яких базуються дані оцінки.
Наукова новизна полягає у створенні способу оцінки обчислювальної складності алгоритму, який врахує характеристики процесорів, на яких буде виконуватись алгоритм.
Практична цінність полягає в можливості врахувати характеристики процесора при оцінці обчислювальної складності алгоритму.
Апробація результатів дисертації. Основні положення й результати роботи представлено на науковій конференції «XIV науково-практична конференція магістрантів та аспірантів ПМК-2021 факультету прикладної математики».
Публікації. Результати дисертації викладено в наукових працях, у тому числі:
- XIV науково-практична конференція магістрантів та аспірантів ПМК-2021 факультету прикладної математики;
- XV міжнародна науково-практична конференція «Сучасні інформаційні та комунікаційні технології в транспорті, промисловості та освіті».
Структура та обсяг роботи. Магістерська дисертація виконана на 80 аркушах, вона містить перелік посилань на використані джерела з Х найменувань. У роботі наведено Х рисунків, Х таблиць. Робота складається з вступу, чотирьох розділів та висновків.
У вступі представлена загальна характеристика роботи, передумови до її виконання, її актуальність та завдання.
У першому розділі даються основні визначення оцінки складності алгоритмів.
У другому розділі проведено порівняльний аналіз способів оцінки обчислювальної складності алгоритмів та обґрунтовано вибір тематики дослідження.
В третьому розділі описано запропонований спосіб підрахунку обчислювальної складності алгоритму за критерієм часу виконання асемблерних інструкцій.
В четвертому розділі пояснювальної записки проведено тестування розробленого способу оцінки, проведено порівняльний аналіз запропонованого способу з вже існуючими та порівняльний аналіз різних алгоритмів на основі запропонованої оцінки.
Опис
Ключові слова
складність алгоритмів, обчислювальна складність, algorithm complexity, computational complexity
Бібліографічний опис
Чорний, Є. Г. Спосіб оцінювання обчислювальної складності алгоритмів за критерієм часу виконання асемблерних інструкцій : магістерська дис. : 123 Комп’ютерна інженерія / Чорний Єгор Геннадійович. – Київ, 2021. – 94 с.