СДЕЛАЙТЕ СВОИ УРОКИ ЕЩЁ ЭФФЕКТИВНЕЕ, А ЖИЗНЬ СВОБОДНЕЕ

Благодаря готовым учебным материалам для работы в классе и дистанционно

Скидки до 50 % на комплекты
только до

Готовые ключевые этапы урока всегда будут у вас под рукой

Организационный момент

Проверка знаний

Объяснение материала

Закрепление изученного

Итоги урока

Практическое занятие № 8 "Нахождение кратчайшего пути в графе с помощью алгоритма Дейкстры"

Категория: Математика

Нажмите, чтобы узнать подробности

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

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

 

Просмотр содержимого документа
«Практическое занятие № 8 "Нахождение кратчайшего пути в графе с помощью алгоритма Дейкстры"»

ИНСТРУКЦИОННАЯ КАРТА

на выполнение практического занятия № 8

по МДК.01.02 Математический аппарат для построения компьютерных сетей (тема 1. Теория графов)

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

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

После выполнения работы студент должен

знать: алгоритма Дейкстры нахождения кратчайшего пути в графе;

уметь: находить пути в графе с помощью алгоритма Дейкстры.

Материально-техническое оснащение рабочего места: инструкционные карты, конспект.

Инструктаж по технике безопасности

Рекомендованная литература:

  1. Спирина М.С., Дискретная математика: Учебник для студ. Учреждений сред. проф. образования / М.С.Спирина, П.А.Спирин. –М.: Издательский центр «Академия», 2004. –368 с.

  2. Александров А. В. и др. Прикладные алгоритмы на графах. Учебное пособие, ВлГУ, 2005

  3. Харари Фрэнк. Теория графов / Харари Фрэнк ; Пер. с англ. В.П.Козырева; Под ред. Г.П.Гаврилова. - 4-е изд. - М. : URSS : Либроком, 2009. - 296 с

  4. Битюцкий В. П. Электронный учебник: Дискретная математика / http://ait.ustu.ru/uploaded/materialy-po-disciplinam/discret-mathematics/el_ucheb/index.htm

  5. Справочные данные по математике: Элементы теории графов. [Электронный ресурс]. – Режим доступа: http://book.itep.ru/10/grap1021.htm, свободный. – Загл. с экрана.

Содержание и порядок выполнения задания

Задание 1. Требуется найти кратчайшие расстояния от 1 -й вершины до всех остальных для графа, представленного на рисунке:


Задани2 ( по вариантам).


Найти кратчайшие расстояния от 1 -й вершины до всех остальных для графа, представленного на рисунке. (вес ребра брать положительный)







Вопросы для самоконтроля:


  1. Дайте определение понятию поиск кратчайшего пути?

  2. Между какими вершинами в графе алгоритм Дейкстры позволяет находить кратчайший путь?

  3. В чем заключается идея алгоритма поиска пути Дейкстры?

  4. К какому виду алгоритма поиска пути («в глубину» или «в ширину») относится алгоритм Дейкстры и почему?

  5. Какое условие должно выполняться для применения алгоритма Дейкстры?


Краткие сведения по теоретической части работы

Нахождение кратчайшего пути на сегодняшний день является жизненно необходимой задачей и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до колледжа), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в сетях и т.п. Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом. Поиск кратчайшего пути ведется между двумя заданными вершинами в графе. Результатом является путь, то есть последовательность вершин и ребер, инцидентных двум соседним вершинам, и его длина. Описываемый в данном разделе алгоритм позволяет находить в графе кратчайший путь между двумя выделенными вершинами s и t при положительных длинах дуг. Этот алгоритм, предложенный в 1959 г. Дейкстрой, считается одним из наиболее эффективных алгоритмов решения задачи. Алгоритм работает только для графов без рёбер отрицательного веса. Любая задача, требующая нахождения оптимальных маршрутов может быть выполнена с помощью алгоритма Дейкстры. Это касается и сетей, и транспортных потоков, и обработка графов. Очень часто используется не сам алгоритм в чистом виде, а его модификация.
Методические рекомендации по выполнению и оформлению

Порядок выполнения работы:

1. Изучить инструкцию к практической работе.

2. Выполнить задание.

3. Оформить отчет.


Содержание отчета о занятии:

1. Тема.

2. Цель.

4. Практическое задание.

5. Ответ на 1 контрольный вопрос (по указанию преподавателя).


Инструкционная карта составлена преподавателем: Шнаревой Г.В.


Скачать

Рекомендуем курсы ПК и ППК для учителей

Вебинар для учителей

Свидетельство об участии БЕСПЛАТНО!