📄Работа №125595
Тема: Оценка трудоемкости алгоритма на основе эмпирического анализа
Тип работы
Бакалаврская работа
Предмет
программирование
Объем:
45 листов
Год:
2020
Просмотров:
53
4600
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 4
Постановка задачи 5
Обзор литературы 6
Глава 1. Обзор существующих решений 9
Глава 2. Исследование трудоемкости 10
2.1. Общие положения исследования 10
2.2. Построение гистограммы частот 11
2.2.1 Формула Стерджесса 12
2.2.2 Эмпирический метод 13
2.2.3 Принцип наихудших измерений 13
2.3. Определение объема выборки 13
2.3.1 Метод с использованием схемы Бернулли 14
2.3.2 Метод на основе закона распределения 14
2.4. Используемые законы распределения 15
2.4.1 Равномерное распределение 16
2.4.2 Треугольное распределение (распределение Симпсона) 17
2.4.3 Бета-распределение 17
2.5. Восстановление параметров функции плотности 18
2.6. Рассмотрение гипотезы о законе распределения 19
2.6.1 Критерий согласия Пирсона (у2) 19
2.6.2 Критерий согласия Колмогорова 20
2.7. Прогнозирование функции трудоемкости 21
2.7.1 Коэффициент детерминации (Я2) 22
Глава 3. Проведение экспериментального исследования трудоемкости 23
3.1. Описание выбранного алгоритма 23
3.2. Этап предварительного исследования 24
3.2.1 Основные шаги 24
3.2.2 Результаты предварительного исследования 27
3.3. Этап основного исследования 30
3.3.1 Основные шаги 30
3.3.2 Результаты основного исследования 32
Глава 4. Создание инструментария 36
4.1. Постановка задачи 36
4.2. Архитектура системы 36
4.3. Описание реализации 37
Выводы 40
Заключение 41
Список литературы 42
Постановка задачи 5
Обзор литературы 6
Глава 1. Обзор существующих решений 9
Глава 2. Исследование трудоемкости 10
2.1. Общие положения исследования 10
2.2. Построение гистограммы частот 11
2.2.1 Формула Стерджесса 12
2.2.2 Эмпирический метод 13
2.2.3 Принцип наихудших измерений 13
2.3. Определение объема выборки 13
2.3.1 Метод с использованием схемы Бернулли 14
2.3.2 Метод на основе закона распределения 14
2.4. Используемые законы распределения 15
2.4.1 Равномерное распределение 16
2.4.2 Треугольное распределение (распределение Симпсона) 17
2.4.3 Бета-распределение 17
2.5. Восстановление параметров функции плотности 18
2.6. Рассмотрение гипотезы о законе распределения 19
2.6.1 Критерий согласия Пирсона (у2) 19
2.6.2 Критерий согласия Колмогорова 20
2.7. Прогнозирование функции трудоемкости 21
2.7.1 Коэффициент детерминации (Я2) 22
Глава 3. Проведение экспериментального исследования трудоемкости 23
3.1. Описание выбранного алгоритма 23
3.2. Этап предварительного исследования 24
3.2.1 Основные шаги 24
3.2.2 Результаты предварительного исследования 27
3.3. Этап основного исследования 30
3.3.1 Основные шаги 30
3.3.2 Результаты основного исследования 32
Глава 4. Создание инструментария 36
4.1. Постановка задачи 36
4.2. Архитектура системы 36
4.3. Описание реализации 37
Выводы 40
Заключение 41
Список литературы 42
📖 Введение
Оценка эффективности алгоритмов является важным этапом в создании качественных программных средств, причем один из критериев качества — временная эффективность, особенно актуальная для систем, работающих в режиме реального времени. Очевидно, что временная эффективность компьютерной программы связана с функцией трудоемкости алгоритма, т. е. с точным количеством операций, задаваемых алгоритмом в основе программной реализации. Однако, асимптотические оценки вычислительной сложности, получаемые в теоретическом исследовании алгоритмов, не всегда справедливы для конечного диапазона длин входов, что объясняется большими значениями коэффициентов у компонентов функции трудоемкости. В работе предлагается практический подход на основе эмпирического анализа времени выполнения программной реализации, для чего создана автоматизированная система с критерием оценки по величине доверительной трудоемкости в выбранном диапазоне входных данных.
Вычисление доверительной трудоемкости основано на построении доверительных интервалов оцениваемой величины трудоемкости с заданной доверительной вероятностью в классическом подходе математической статистики [1]. Данный метод требует использования репрезентативных выборок достаточно большого объема и многократного запуска программных реализаций исследуемых алгоритмов в соответствующем многоэтапном процессе; поэтому, несомненно, актуальной является разработка системы для автоматизированного проведения анализа, значительно сокращающего время оценки качества алгоритмов.
В данной работе рассматривается построение такой системы и исследование применимости предложенного подхода на основе доверительной трудоемкости для большего количества алгоритмов.
Вычисление доверительной трудоемкости основано на построении доверительных интервалов оцениваемой величины трудоемкости с заданной доверительной вероятностью в классическом подходе математической статистики [1]. Данный метод требует использования репрезентативных выборок достаточно большого объема и многократного запуска программных реализаций исследуемых алгоритмов в соответствующем многоэтапном процессе; поэтому, несомненно, актуальной является разработка системы для автоматизированного проведения анализа, значительно сокращающего время оценки качества алгоритмов.
В данной работе рассматривается построение такой системы и исследование применимости предложенного подхода на основе доверительной трудоемкости для большего количества алгоритмов.
✅ Заключение
Исследованы различные дополнительные методы для применения методологии [1] на более широкий класс алгоритмов.
Разработана автоматизированная система для оценки качества алгоритмов по доверительной трудоемкости, вычисленной в процессе эмпирического анализа программной реализации. Преимущество системы состоит в получении гарантирующей оценки на основе статистических заключений с заданным уровнем значимости. Исходный код и документация системы находятся в публичном репозитории в GitHub [39].
Разработана автоматизированная система для оценки качества алгоритмов по доверительной трудоемкости, вычисленной в процессе эмпирического анализа программной реализации. Преимущество системы состоит в получении гарантирующей оценки на основе статистических заключений с заданным уровнем значимости. Исходный код и документация системы находятся в публичном репозитории в GitHub [39].
ИЛИ
Поиск аналога
📕 Список литературы
🖼 Скриншоты
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.