Помощь в учёбе, очень быстро...
Работаем вместе до победы

Разработка алгоритмического и программного обеспечения для решенияграфовых задач

Курсовая: Разработка алгоритмического и программного обеспечения для решенияграфовых задач
КурсоваяПомощь в написанииУзнать стоимостьмоей работы

В данной работе представлены лишь некоторые вопросы из теории графов. В частности решается задачи нахождения кратчайшего пути между двумя заданными вершинами графа и нахождения минимального остовного дерева. Для решения этих задач на прктике существуют готовые алгоритмы. Рассмотрением этих алгоритмов и решением конкретно заданных практических задач получились следующие результаты: Теория графов… Читать ещё >

Содержание

  • Введение
  • 1. Описание алгоритмов
    • 1. 1. Алгоритмы нахождения кратчайшего пути между двумя заданными вершинами графа
    • 1. 2. Алгоритмы нахождения минимального остовного дерева графа
  • 2. Реализация алгоритмов
    • 2. 1. Реализация алгоритма Дейкстры определения кратчайшего пути между двумя заданными вершинами графа в языке программирования С++
    • 2. 2. Реализация алгоритма Прима определения минимального остовного дерева графа в языке программирования С++
  • 3. Тестирование алгоритмов
  • Заключение
  • Список использованной литературы

Разработка алгоритмического и программного обеспечения для решенияграфовых задач (реферат, курсовая, диплом, контрольная)

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он сформулировал и предложил решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

Теория графов — это раздел дискретной математики, изучающий свойства графов. В общем случае граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V, E), где V есть подмножество любого счётного множества, а E — подмножество VxV. На рисунке 1 представлен граф с шестью вершинами и семью ребрами.

Рисунок 1 — Граф с шестью вершинами и семью ребрами Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.

В данной работе представлены лишь некоторые вопросы из теории графов. В частности решается задачи нахождения кратчайшего пути между двумя заданными вершинами графа и нахождения минимального остовного дерева. Для решения этих задач на прктике существуют готовые алгоритмы. Рассмотрением этих алгоритмов и решением конкретно заданных практических задач получились следующие результаты:

Показать весь текст

Список литературы

  1. Андерсон Джеймс А. Дискретная математика и комбинаторика. — М.: Издатель- Издательский дом «Вильямс», 2004. — 960 с.
  2. Ю. А. Тюрин С.Ф. Дискретная математика и математическая логика. — М.: Финансы и статистика, 2006. — 368 с.
  3. М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. — 288 с.
  4. А.И., Ткачев С. Б. Дискретная математика. — М.: МГТУ им. Н. Э. Баумана, 2004. — 742 с.
  5. Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. — М., Мир, 1998. — 704 с.
  6. Я.М. Дискретная математика: теория, задачи, приложения. — М.: Вузовская книга, 2000. — 200с.
  7. . Н. Дискретная математика. Алгоритмы и программы. — М.: Лаборатория Базовых Знаний, 2003. — 288 с.
  8. Кук Д., Бейз Г. Компьютерная математика. — М.: Наука, 1990. — 384 с.
  9. Кузнецов О П. Адельсон-Вельский Г. М. Дискретная математика дли инженера. — М.: Энергия, 1980. — 344 с.
  10. Г. И. Дискретная математика. Математика для менеджера в примерах и упражнениях. — М.: Логос, 2000. — 240 с.
  11. Ф.А. Дискретная математика для программистов. — СПб.: Питер, 2000. — 304с.
  12. А.Д. Дискретная математика. — М.: Новое знание, 2005. — 288 с.
  13. Р. Дискретная математика для программистов — М.: Техносфера, 2003. — 320 с.
  14. О.Е. Дискретная математика. Логика, группы, графы. — М.: Лаборатория базовых знаний, 2001. — 376 с.
  15. Н. Теория графов: алгоритмический подход. — М.: Мир, 1978. — 432 с.
Заполнить форму текущей работой

Пора сдавать?