Пример готовой дипломной работы по предмету: Высшая математика
Содержание
ВВЕДЕНИЕ 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
Выдержка из текста
Традиционно понятие сложности алгоритма связано с использованием временных ресурсов и ресурсов памяти, т.е. насколько много необходимо времени для реализации алгоритма, насколько много при этом расходуется память? Учет памяти при этом ведется по объему данных и не принимается во внимание память, расходуемая для записи и выбора команд. Необходимо отметить, что время рассчитывается в относительных единицах так, чтобы эта оценка, по возможности, была одинаковой при различных незначительнымх вариациях.
Такой подход сложился исторически и ориентируется, прежде всего, на инженерные и научные теории алгоритмов, где объемы данных в несколько раз превышают размеры самого алгоритма, а алгоритм, в свою очередь, может выполняться несколько часов. В этом случае следует учесть вид и назначение приложения, для которого применяется алгоритм. Например, в научных и инженерных приложениях большое время вычислений может доставить неудобство только пользователям, а в то в ряде других областей ресурсы настолько принципиальны, что может возникнуть вопрос о целесообразности всего проекта из-за неэффективной работы алгоритма. В частности, к таким областям можно отнести системы реального времени (real-time systems).
Это, основанные на компьютерах, системы, которые управляют процессами в реальном мире или обрабатывают информацию, которая служит для принятия оперативных решений.
Объект исследования: алгоритмы на графах.
Предмет исследования: оценка сложности алгоритмов на графах.
Цель исследования: на основе теоретического анализа временной и емкостной сложности алгоритмов на графах математически обосновать применение формул оценки сложности для алгоритма построения минимального остовного дерева.
Для достижения поставленной цели были сформулированы следующие задачи:
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 с.,
26. ил.
9. Макконнел Дж. Анализ алгоритмов. Вводный курс. – М.: Техносфера, 2002 г. – 304 с.
10. Новиков Ф. А. Дискретная математика для программистов. – СПб.: Питер, 2001 г. – 304 с., ил.
11. Романовский И.В. Дискретный анализ. Учебное пособие для студентов, специализирующихся по прикладной математике. – Издание 2-ое, исправленное. – СПб.; Невский диалект, 2000 г. – 240 с., ил.
12. Успенский В.А. Машина Поста. – М.: Наука, 1999 г. – 96 с.
