Работа выполнена качественно, с учетом всех пожеланий
Информация о работе
Подробнее о работе
оценка сложности алгоритма построения графа
- 37 страниц
- 2015 год
- 308 просмотров
- 0 покупок
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
Традиционно понятие сложности алгоритма связано с использованием временных ресурсов и ресурсов памяти, т.е. насколько много необходимо времени для реализации алгоритма, насколько много при этом расходуется память? Учет памяти при этом ведется по объему данных и не принимается во внимание память, расходуемая для записи и выбора команд. Необходимо отметить, что время рассчитывается в относительных единицах так, чтобы эта оценка, по возможности, была одинаковой при различных незначительнымх вариациях.
Такой подход сложился исторически и ориентируется, прежде всего, на инженерные и научные теории алгоритмов, где объемы данных в несколько раз превышают размеры самого алгоритма, а алгоритм, в свою очередь, может выполняться несколько часов. В этом случае следует учесть вид и назначение приложения, для которого применяется алгоритм. Например, в научных и инженерных приложениях большое время вычислений может доставить неудобство только пользователям, а в то в ряде других областей ресурсы настолько принципиальны, что может возникнуть вопрос о целесообразности всего проекта из-за неэффективной работы алгоритма. В частности, к таким областям можно отнести системы реального времени (real-time systems). Это, основанные на компьютерах, системы, которые управляют процессами в реальном мире или обрабатывают информацию, которая служит для принятия оперативных решений.
Объект исследования: алгоритмы на графах.
Предмет исследования: оценка сложности алгоритмов на графах.
Цель исследования: на основе теоретического анализа временной и емкостной сложности алгоритмов на графах математически обосновать применение формул оценки сложности для алгоритма построения минимального остовного дерева.
Для достижения поставленной цели были сформулированы следующие задачи:
1. На основе теоретического анализа литературы сформулировать основные понятия теории графов, рассмотреть способы их задания.
2. Изучить сложностные классы задач, а также особенности оценки временной и емкостной сложности алгоритмов на графах.
3. Математически обосновать оценку сложности алгоритма минимального остовного дерева и алгоритма Дейкстры.
ВВЕДЕНИЕ 2
Глава 1. Графы и способы их задания 4
1.1. Основные понятия теории графов 4
1.2. Область применения графов 9
1.3. Теоретические основы теории сложности вычислений 12
1.3.1. Основные понятия и принципы теории сложности вычислений 12
1.3.2. Сложностные классы задач 15
3. Проблема P NP 16
4. Класс NPC (NP – полные задачи) 17
1.3.3. Временная и емкостная сложности 18
1.4. Алгоритмы на графах и порядок оценки их сложности 19
1.4.1. Алгоритм построения минимального остова 19
1.4.2. Корректность теоремы Дейкстры 26
Глава 2. Оценка сложности алгоритма на графах 30
2.1. Оценка сложности алгоритма построения минимального остова 30
2.2. Оценка сложности алгоритма Дейкстры 32
Заключение 34
Список литературы 35
Теория алгоритмов - это наука, которая изучает общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. На основе формализации понятия алгоритма существует возможность их сравнения по эффективности, проверка их эквивалентности, определение областей применимости.
В 1930-х годах были разработаны разнообразные формальные модели алгоритмов (Пост, Тьюринг, Черч). Данные модели, также как и предложенные в 1950-х годах Колмогоровым и Марковым, оказались эквивалентными. Их эквивалентность определяется тем, что любой класс проблем, разрешимых в одной модели, разрешимы и в другой.
В настоящее время всё большее распространение в области проектирования и разработки программных систем получают практические рекомендации, полученные на основе теории алгоритмов.
Одной из основных задач, которая обычно ставится при разработке алгоритмов – это оптимизация их выполнения (по времени и по памяти). Теория сложности алгоритмов предлагает достаточные эффективные методы решения поставленной проблемы. Точное решение возможно в подавляющем большинстве практически важных ситуаций.
Однако по-прежнему остаются открытыми вопросы, связанные со сводимостью алгоритмов друг к другу и нерешенной остается известная проблема PNP.
В нашем исследовании:
1. Были сформулированы основные понятия теории графов, изучены способы их задания.
2. Изучены сложностные классы задач, а также особенности оценки временной и емкостной сложности алгоритмов на графах.
3. Математически обоснована оценка сложности алгоритма минимального остовного дерева и алгоритма Дейкстры.
1. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы: Пер. с англ.: – М.: Издательский дом «Вильямс», 2001 г. –384 с., ил.
2. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. – 2-ое изд., испр. – СПб.: Невский диалект, 2001 г. – 352 с., ил.
3. Иванова Г.С. Математические модели структур данных. Информационные технологии, 2008б №9б с. 44-52.
4. Иванова Г.С. Автоматизация анализа вычислительной и емкостной сложности алгоритмов на множествах и графах. Инженерный журнал: наука и инновации, 2013, вып. № 11.
5. Карпов Ю.Г. Теория автоматов – СПб.: Питер, 2002 г. – 224с., ил.
6. Кормен Т., Лейзерсон Ч., Риверст Р., Штайн К. Алгоритмы: построение и анализ. Москва, Вильямс, 2011, 1296 с.
7. Кнут Д. Искусство программирования. Тома 1, 2, 3. 3-е изд. Пер. с англ. : Уч. пос. – М.: Изд. дом "Вильямс", 2001 г.
8. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 2001 г. – 960 с., 263 ил.
9. Макконнел Дж. Анализ алгоритмов. Вводный курс. – М.: Техносфера, 2002 г. –304 с.
10. Новиков Ф. А. Дискретная математика для программистов. – СПб.: Питер, 2001 г. – 304 с., ил.
11. Романовский И.В. Дискретный анализ. Учебное пособие для студентов, специализирующихся по прикладной математике. – Издание 2-ое, исправленное. – СПб.; Невский диалект, 2000 г. – 240 с., ил.
12. Успенский В.А. Машина Поста. – М.: Наука, 1999 г. – 96 с.
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
