Урок по теме "Поиск кратчайших путей в графе"
план-конспект урока по информатике и икт (11 класс)

Тема урока

Поиск кратчайших путей в графе.

Тип урока

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

Цель урока

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

Планируемый

результат обучения,

в том числе

формирование УУД

Предметные        

умение находить оптимальное решение при использовании различных алгоритмов;

Метапредметные

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

Коммуникативные УУД: организация самостоятельной работы, работы в группе (самостоятельно определять цели, роли, задавать вопросы, вырабатывать решения). Учет разных мнений и стремление к координации различных позиций в сотрудничестве;

Личностные УУД: выработка культуры общения, взаимопомощь обучающихся, формирование интеллектуальной и эмоциональной активности обучающихся, воспитание чувства ответственности за результаты своего труда;

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

Личностные

Выработка уважительно-доброжелательных отношений между обучающимися, учет различных мнений, творческое отношение к процессу обучения.

Основные понятия

• понятия «жадный» алгоритм,
• минимальное остовное дерево,
• алгоритм Прима-Крускала;
• алгоритм Дейкстра;
• граф, ребро, дуга, дерево, цикл.

Межпредметные связи

 Экономика, математика

Ресурсы

интерактивная доска, мультимедийный проектор, ЭОР для интерактивной доски,   тестовые задания на ПК, приложения.

Этапы урока

Формируемые УУД

Деятельность учителя

Деятельность учащегося

Оргмомент

личностные

Приветствие

Настраиваются на урок

Целеполагание и мотивация

регулятивные

Прежде, чем мы начнем наш урок, хочу напомнить слова выдающегося немецкого философа и драматурга Г.Э.Лессинга «Спорьте, заблуждайтесь, ошибайтесь, но ради бога, размышляйте, и хотя и криво, да сами».

Я бы хотела, чтобы вы об этом помнили, не смущались, если что-то сразу не получится.

Актуализация знаний

регулятивные

Давайте вспомним, с какими основными понятиями и определениями вы познакомились при изучении темы «Графы».  Для этого предлагаю выполнить тест.

Завершаем работу с тестом и послушаем небольшое сообщение о семи мостах Кенигсберга. (Приложение 2)

Если учесть, что Эйлер родился в самом начале XVIII века (1707 г.), то конечно можно сделать вывод о том, что уже в те времена существовала теория графов. В настоящее время существует целый раздел науки о  Эйлеровых графах, циклах и цепях.

Вернемся в  10 класс. Мы учились решать задачи на поиск количества путей в графе и анализ информационных моделей. Это задания № 3 и15 в ЕГЭ по информатике. Давайте вспомним, как мы это делали. Для этого  выполним следующие задание:.

Обучающихся выполняют тест. (Приложение 1)

Слушают выступление.

Предположения детей.

Выполняют задания на интерактивной доске.

постановка цели деятельности (постановка учебной задачи)

регулятивные

Попробуйте сформулировать проблему урока. 

Запишем тему урока: « Поиск кратчайших путей в графе»

А сейчас вернемся к прошлому уроку, когда мы учились применять алгоритмы к поиску кратчайших путей в графах. Вспомним эти алгоритмы и сделаем общий вывод к которому мы пришли.

1. «жадный алгоритм»;

(алгоритм, который, на каждом шагу принимают локально оптимальное решение, не заботясь о том, что будет дальше)

2. сформулируйте алгоритм Прима-Крускала;

(это «жадный» алгоритм, который всегда приводит к правильному решению. В теории графов – это построение минимального остовного дерева, т.е. дерева, связывающего все вершины)

1.начальное дерево – пустое

     2.на каждом шаге добавляется ребро минимального веса, которое ещё не входит в дерево и не приводит к появлению цикла

3. в чем заключается алгоритм Дейкстра?

(алгоритм, нахождения кратчайшего расстояния от одной из вершин графа до всех остальных).

Вывод: не всякий алгоритм дает оптимальное решение.

Решим следующую задачу: требуется найти кратчайшее расстояние от 1-й вершины до 6 используя «жадный алгоритм».      

1) Жадный алгоритм              

Жадные алгоритмы – это общее название подхода к решению задач оптимизации. Вопрос: в какой области науки решают задачи по оптимизации?

2)Алгоритм Прима-Крускала

Общая длина равна 33.

 3) Алг. Дейкстра:                                            

Результат работы алгоритма: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й — 9, до 4-й — 20, до 5-й — 20, до 6-й — 11.

      Займемся выводом кратчайшего пути. Мы знаем длину пути для каждой вершины, и теперь будем рассматривать вершины с конца. Рассматриваем конечную вершину (в данном случае — вершина 5), и для всех вершин, с которой она связана, находим длину пути, вычитая вес соответствующего ребра из длины пути конечной вершины.
Так, вершина 5 имеет длину пути 20. Она связана с вершинами 6 и 4.
Для вершины 6 получим вес 20 — 9 = 11 (совпал).
Для вершины 4 получим вес 20 — 6 = 14 (не совпал).
Если в результате мы получим значение, которое совпадает с длиной пути рассматриваемой вершины (в данном случае — вершина 6), то именно из нее был осуществлен переход в конечную вершину. Отмечаем эту вершину на искомом пути.
Далее определяем ребро, через которое мы попали в вершину 6. И так пока не дойдем до начала.
Если в результате такого обхода у нас на каком-то шаге совпадут значения для нескольких вершин, то можно взять любую из них — несколько путей будут иметь одинаковую длину.

Ответы детей

Ответы детей.

В экономике для достижения максимальной прибыли при наименьших затратах.

Физкультминутка (Приложение 4)

Выполняют  Аутомануальный комплекс

Реализация построенного проекта

Познавательные

Задание:  Используя алгоритм Прима-Крускала найдите на графе минимальное остовное дерево. Является ли оно универсальным?

Ответ (решение не универсально)

Задание: используя алгоритм Дейкстра найдите кратчайшие расстояния между вершиной А и всеми другими вершинами.

Чему равен порядок графа и что это такое? (Ответ: порядок графа – это число вершин, равно 5)

Чему равен размер графа и что это такое (Ответ: размер – это количество дуг или ребер, равно 8)

закрепление

познавательные

Задание: используя алгоритм Дейкстра, найдите кратчайшие расстояния между вершиной а всеми другими вершинами. Определите порядок и размер графа.

Ответ:

Порядок – 9, размер – 14

Самостоятельно: используя алгоритм Прима-Крускала, постройте минимальное остовное дерево.

Вернемся снова к заданию ЕГЭ и решим его применив алгоритм Дейкстра

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

Работа с кейсами:   (Приложение 5)

Задание: используя алгоритм Прима-Крускала найдите на графе минимальное остовное дерево.  Является ли оно универсальным?

Ответ: (является)

Используя жадный алгоритм и алгоритм Дейкстра найдите кратчайшее расстояние от А до К. Сделайте вывод.

1) Жадный:  ответ - 69

2) Алгоритм Дейкстра

Задача: имеется n городов, которые нужно объединить в единую телефонную сеть. Для этого достаточно проложить (n-1) телефонных линий между городами. Как соединить города так, чтобы суммарная стоимость соединений (телефонного кабеля) была минимальна? Является ли решение универсальным?

Ответ: (не является)

 Суммарный вес дерева равен 37. Это минимальное остовное дерево не уникально: удалением ребра (c,d) и добавлением ребра (a,b) получается новое минимальное остовное дерево.

Задача: удалите лишние ребра и получите минимальное остовное дерево.

Ответ:

С графами связаны некоторые классические задачи. Самая известная из них – задача коммивояжёра.

Коммивояжёр (фр. commis voyageur) — бродячий торговец. Задача коммивояжёра — важная задача транспортной логистики, отрасли, занимающейся планированием транспортных перевозок. Коммивояжёру, чтобы распродать нужные и не очень нужные в хозяйстве товары, следует объехать n пунктов и в конце концов вернуться в исходный пункт. Требуется определить наиболее выгодный маршрут объезда. В качестве меры выгодности маршрута (точнее говоря, невыгодности) может служить суммарное время в пути, суммарная стоимость дороги, или, в простейшем случае, длина маршрута. 

Выполняют задание

Сообщение учащегося, владеющего навыками решения задачи.

(Приложение 6)

Домашнее задание

§ 44 стр. 109-112, № 2 стр. 119

Дополнительно: сформулируйте критерий минимальности остова.

(Ответ: Критерий минимальности остова: остов является минимальным тогда и только тогда, когда для любого ребра, не принадлежащего остову, цикл, образуемый этим ребром при добавлении к остову, не содержит рёбер тяжелее этого ребра. В самом деле, если для какого-то ребра оказалось, что оно легче некоторых рёбер образуемого цикла, то можно получить остов с меньшим весом (добавив это ребро в остов, и удалив самое тяжелое ребро из цикла). Если же это условие не выполнилось ни для одного ребра, то все эти рёбра не улучшают вес остова при их добавлении.)

записывают домашнее задание

Включение в систему знаний и повторение.

Рефлексия.

коммуникативные

Подведем итоги нашего урока.  

Предлагаю устно закончить следующие предложения.

"На сегодняшнем уроке я понял, я узнал, я разобрался…";

 "Я похвалил бы себя…";

 "Сегодня мне удалось…";

 "Я сумел…";

"Было интересно…";

"Было трудно…";

"Я понял, что…";

"Теперь я могу…";

"Я научился…".

Закончить наш урок хочу словами Шарля де Голля, французского генерала второй мировой войны и выдающегося политика: "Всегда выбирайте самый трудный путь, на нем вы не встретите конкурентов!".

Ответы детей