
Тип работы:	Предмет:	Язык работы:

Апостериорный анализ и оценка эффективности алгоритмов

Работа №	128308
Тип работы	Бакалаврская работа
Предмет	информатика
Объем работы	23
Год сдачи	2021
Стоимость	4310 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено	23

Не подходит работа?

Узнай цену на написание

Содержание

Введение 3
Постановка задачи 4
Обзор литературы 5
Глава 1. Исследование ресурсоемкости 7
1.1. Общие положения исследования 7
1.2. Построение гистограммы частот 8
1.3. Определение объема выборки 8
1.3.1 Метод с использованием схемы Бернулли 9
1.3.2 Метод на основе закона распределения 9
Глава 2. Проведение экспериментального исследования функции объема памяти 11
2.1. Описание выбранного алгоритма 11
2.2. Генерация данных 11
2.3. Этап предварительного исследования 12
2.4. Этап основного исследования 14
Глава 3. Создание автоматизированной системы 18
Выводы 20
Заключение 21
Список литературы

Введение

Алгоритмы являются одной из важнейших составляющих эффективной программной системы. В больших проектах правильно написанный алгоритм может сэкономить компании миллионы долларов. Например, в 2016 году социальная сеть “ВКонтакте”, оптимизировав работу с личными сообщениями, сэкономила минимум 5 млн. долларов [1].
В разработке таких алгоритмов не обойтись без предварительного анализа: нужно уметь оценивать те или иные ресурсы, которые алгоритм потребляет во время работы. Самый распространенный ресурс — это время выполнения алгоритма. Он является важнейшим, так как пользователи не любят ждать. Второй по значимости ресурс — это память. Причем, если время выполнения алгоритма вычисляется как количество базовых операций и связано с функцией трудоемкости алгоритма, то память обычно берется не как суммарное количество памяти, которое потребляет алгоритм, а как количество дополнительной памяти, при этом память связана с функцией объема памяти алгоритма.
Обычный асимптотический анализ не всегда точен для конечного диапазона длин входов из-за часто больших коэффициентов у компонентов функций ресурсной эффективности:
*A(D)= CV- VA(D)+ Cf- /A(D),
где V — объем потребляемой алгоритмом Aпамяти, f— трудоемкость.
В данной работе будет рассмотрен новый подход на основе эмпирического анализа: по данным, полученным экспериментальным путем, будет построена функция доверительной ресурсоемкости (доверительной памяти) с выбранным коэффициентом доверия, а также для упрощения процесса разработана автоматизированная система в виде сайта.

Возникли сложности?

Нужна помощь преподавателя?

Помощь студентам в написании работ!

ДИПЛОМНЫЕ МАГИСТЕРСКИЕ ДИССЕРТАЦИИ

Курсовые Статьи Диплом Рязань

Заключение

В данной работе построена функция доверительной ресурсоемкости для алгоритма Левита. Также реализована автоматизированная система в виде сайта, через которую можно проводить анализ, загружая данные работы алгоритма.
Исходный код всех программ находится в публичном репозитории в GitHub [16].

Литература

[1] Переписать базу сообщений с нуля и выжить [Электронный ресурс] // URL: url: https://vk.com/blog/messages-database(дата обращения: 20.01.2021)
[2] Трахтенброт Б. А. Сложность алгоритмов и вычислений. Новосибирск: Изд-во Новосибирского ун-та, 1967.
[3] Офман Ю. П. Об алгоритмической сложности дискретных функций // ДАН СССР. 1962. Т. 45, вып. 1. С. 48-51.
[4] Маркова Н. А. Качество программы и его измерения // Системы и средства информатики. Вып. 12. — М.: Наука, 2002. С. 170-188.
[5] Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms. Chapter 1: Foundations (Second ed.) // Cambridge, MA: MIT Press and McGraw-Hill. 2001. P. 3-122.
[6] Кнут Д. Э. Искусство программирования, том 1. Основные алгоритмы, 3-е изд.: Пер. с англ. — М.: Издательский дом «Вильямс», 2002. — 720 с.
[7] Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов: Пер. с англ.: — М.: Мир, 1979. — 546 с.
[8] Петрушин В. Н., Ульянов М. В., Кривенцов А. С. Доверительная трудоемкость — новая оценка качества алгоритмов // Информационные технологии и вычислительные системы. 2009. № 2. С. 23-37.
[9] Петрушин В. Н., Ульянов М. В. Планирование экспериментального исследования трудоемкости алгоритмов на основе бета-распределения // Информационные технологии и вычислительные системы. 2008. № 2. С. 81-91.
[10] Hutter F., Xu L. Hoos H., Leyton - Brown K. Algorithm runtime prediction: Methods evaluation // Artificial Intelligence. 2014. Vol. 206. No 1. P. 79-111.
[11] Erik D. Demaine, Jayson Lynch, Geronimo J. Mirano, Nirvan Tyagi. Energy-Efficient Algorithms. May 30, 2016
[12] Петрушин В. Н., Ульянов М. В. Информационная чувствительность компьютерных алгоритмов. М.: Физматлит, 2010.
[13] Ульянов М. В. Система обозначений в анализе ресурсной эффективности вычислительных алгоритмов // Вестн. МГАПИ. Сер. Естеств. и инж. науки. 2004. No1 (1). С. 42-49.
[14] Pallottino S. Shortest-path methods: Complexity, interrelations and new propositions // Networks. 1984. Vol. 14. P. 257-267.
[15] Королюк В. С., Портенко Н. И., Скороход А. В., Турбин А. Ф. Справочник по теории вероятностей и математической статистике. М.: Наука, 1985.
[16] Репозиторий проекта в системе контроля версий GitHub [Электронный ресурс]: URL: https://github.com/romanychev-l/apostorial_analysis(дата обращения: 31.05.2021)