Пример готовой дипломной работы по предмету: Высшая математика
ВВЕДЕНИЕ 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
Содержание
Выдержка из текста
Цель исследования: на основе теоретического анализа временной и емкостной сложности алгоритмов на графах математически обосновать применение формул оценки сложности для алгоритма построения минимального остовного дерева.
Рассматриваемый в настоящей работе мобильный робот представляет собой колёсную платформу, снабжённую лазерным сканирующим дальномером – прибором, измеряющим расстояния до непрозрачных препятствий в некотором известном сегменте с определённой дискретностью – и камерой.
В современной жизни общества все большую роль играет транспорт. Одним и з наиболее распространенных в настоящее время для городских пассажироперевозок является автомобильный транспорт (автобусы; троллейбусы; маршрутное такси).
Но эксплуатация автомобильного транспорта связана с большими трудовыми затратами и проблемами его экс плуатации в городе (высокая урбанизация, плохие автодороги и др.).
Несомненно, труд водителей, также как и любая другая профессия требует эмоциональных ресурсов и физических затрат. Оценка трудоемкости работы, выполняемой водителями, является актуальной и очень важной задачей для определения наиболее рациональной оплаты их труда, режима отдыха, питания, создание возможно более комфортных условий работы водителей, повышение престижности профессии, факторов, стимулирующей их к более качественной работе.
Оценка сложности работы — это процесс выстраивания в порядке сложности выполняемых видов работ с целью установления справедливого вознаграждения работникам за их выполнение. Вследствие значительного разнообразия работ и их различий по множеству аспектов проблема оценки относительной важности каждого вида работы представляет существенные трудности.
Оценка сложности алгоритмов Построение управляющего графа программы Оценка сложности по управляющему графу
Проведение анализа литературных источников из основных понятий теории графов и использования графов моделей в различных областях знаний. Разработка алгоритма работы программного модуля Разработка графов моделей и выполнения примеров из их исследования.
Например, в виде графа отображают последовательность выполняемых работ при строительстве объектов, начиная от изыскательских работ и заканчивая обустройством прилегающих территорий, маршруты транспортировок материалов, взаимосвязи этапов работ, потоки ресурсов различного рода (материальных, финансовых, трудовых, энергетических), системы учета и управления проектами в соответствии с каждым из этапов и т.д.
Таким образом, граф полностью задаётся (и обозначается) упорядоченной парой . Графически граф обычно изображают в виде кругов (вершин) и соединяющих их линий (рёбер):Используя описанный выше алгоритм, создадим программу на языке C++, которая будет получать орграф в виде списка смежности с дополнительным параметром (весом) для каждого ребра из текстового файла следующего формата: первая строка ‒ количество вершин графа, вторая ‒ количество рёбер графа, далее следуют строки с описанием каждого ребра
Содержание: данный проект содержит в себе файлы, реализующие работу алгоритма нахождения длин кратчайших путей от вершины до всех остальных вершин. На экране выводится пошаговая работа алгоритма и графическое представление графа.
При наступлении этого события компонент ListBox 1 очищается, затем вызывается основная подпрограмма FloydWarshall, выполняющая нахождение кратчайших путей между вершинами графа.
Теоретические сведения об алгоритмах поиска подстроки в строке. Понятие о сложности алгоритма. Пример построения конечного автомата 19
Список источников информации
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 с.
список литературы
