Технологическая карта урока "Поиск кратчайших путей в графе"

Технологическая карта урока

Тема урока: ПОИСК КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ

1.                  Предмет: информатика

2.                  Класс: 11 класс.

3.                  Учебник:                                                                                                                                                               

            Информатика: учебник для 11 класса. Часть 2. Углубленный уровень. / К.Ю. Поляков, Е.А. Еремин  – М.: БИНОМ. Лаборатория знаний, 2019.

4.                  Длительность урока: 45 минут.

Тема урока	Поиск кратчайших путей в графе
Тип урока	Урок решения задач
Цель урока	Разобрать известные алгоритмы для поиска кратчайших путей в графе.
Планируемый результат обучения, в том числе формирование УУД	Предметные                 умение находить оптимальное решение при использовании различных алгоритмов; Метапредметные Познавательные УУД:  формирование представления о графе как о наглядном средстве представления состава и структуры системы;   формирование представления о способе реализации решения задач оптимизации с помощью различных алгоритмов; Коммуникативные УУД: организация самостоятельной работы, работы в группе (самостоятельно определять цели, роли, задавать вопросы, вырабатывать решения). Учет разных мнений и стремление к координации различных позиций в сотрудничестве; Личностные УУД: выработка культуры общения, взаимопомощь обучающихся, формирование интеллектуальной и эмоциональной активности обучающихся, воспитание чувства ответственности за результаты своего труда; Регулятивные УУД:  определение целей, проблемы в своей деятельности. Выдвижение версии, выбор средства достижения цели. Работа по плану, сверяясь с целью, нахождение и исправление ошибки, в т.ч. самостоятельно. Личностные Выработка уважительно-доброжелательных отношений между обучающимися, учет различных мнений, творческое отношение к процессу обучения.
Основные понятия	-     понятия «жадный» алгоритм, -     минимальное остовное дерево, -     алгоритм Прима-Крускала; -     алгоритм Дейкстра; -     граф, ребро, дуга, дерево, цикл.
Межпредметные связи	Экономика, математика
Ресурсы	интерактивная доска, мультимедийный проектор, ЭОР для интерактивной доски,   тестовые задания на ПК, приложения.
Этапы урока	Формируемые УУД	Деятельность учителя	Деятельность учащегося
Оргмомент	личностные	Приветствие	Настраиваются на урок
Целеполагание и мотивация	регулятивные	Прежде, чем мы начнем наш урок, хочу напомнить слова выдающегося немецкого философа и драматурга Г.Э.Лессинга: «Спорьте, заблуждайтесь, ошибайтесь, но ради бога, размышляйте, и хотя и криво, да сами». Я бы хотела, чтобы вы об этом помнили, не смущались, если что-то сразу не получится.
Актуализация знаний	регулятивные	Давайте вспомним, с какими основными понятиями и определениями вы познакомились при изучении темы «Графы и Деревья».  Для этого предлагаю выполнить тест. Завершаем работу с тестом и послушаем небольшое сообщение о семи мостах Кенигсберга. Если учесть, что Эйлер родился в самом начале XVIII века (1707 г.), то конечно можно сделать вывод о том, что уже в те времена существовала теория графов. В настоящее время существует целый раздел науки о  Эйлеровых графах, циклах и цепях. Вспомним 10 класс. Мы учились решать задачи на поиск количества путей в графе и анализ информационных моделей. Это задания № 3 и15 в ЕГЭ по информатике. Давайте вспомним, как мы это делали. Для этого  выполним следующие задание: №3. На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта Б в пункт К.	Обучающихся выполняют тест на компьютере. Слушают выступление. Предположения детей. Выполняют задания на интерактивной доске.
постановка цели деятельности (постановка учебной задачи)	регулятивные	Попробуйте сформулировать проблему урока. Запишем тему урока: «Поиск кратчайших путей в графе» А сейчас вернемся к прошлому уроку, когда мы учились применять алгоритмы к поиску кратчайших путей в графах. Вспомним эти алгоритмы и сделаем общий вывод к которому мы пришли. 1)      Что такое «жадный алгоритм»?  (стр. 97_Уч) (алгоритм состоит в том, чтобы на каждом шаге многоходового процесса выбирать наилучший в данный момент вариант, не думая о том, что впоследствии этот выбор может привести к худшему решению) 2)      Сформулируйте алгоритм Прима-Краскала    (стр. 98_Уч);   (это «жадный» алгоритм, который всегда приводит к правильному решению. В теории графов – эта задача называется задачей построения минимального остовного дерева, т.е. дерева, связывающего все вершины) Остовное дерево для связного графа с N вершинами имеет  N-1 ребро. 1. начальное дерево – пустое;      2. на каждом шаге к дереву добавляется ребро минимального веса, которое ещё не входит в дерево и не приводит к появлению цикла. 3)    В чем заключается алгоритм Дейкстры?    (стр. 100-101_Уч) (алгоритм  нахождения кратчайшего расстояния от одной  вершины графа до всех остальных. Если сумма весов  xz+zy меньше, чем вес   xy, то из вершины   X лучше ехать в вершину  Y не напрямую, а через вершину Z). Вывод: не всякий алгоритм дает оптимальное решение. Решим следующую задачу: требуется найти кратчайшее расстояние от 1-й вершины до 6 используя «жадный алгоритм».      1) Жадный алгоритм              Жадные алгоритмы – это общее название подхода к решению задач оптимизации. Вопрос: в какой области науки решают задачи по оптимизации? 2)Алгоритм Прима-Крускала 3) Алг. Дейкстра:                                             1 2 3 4 5 6 0 ¥ ¥ ¥ ¥ ¥ 7 9 ¥ ¥ 14 9 22 ¥ 14 20 ¥ 11 20 20 20 Результат работы алгоритма: кратчайший путь от вершины 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. И так пока не дойдем до начала. Если в результате такого обхода у нас на каком-то шаге совпадут значения для нескольких вершин, то можно взять любую из них — несколько путей будут иметь одинаковую длину.	Ответы детей Ответы детей. В экономике для достижения максимальной прибыли при наименьших затратах.
		Физкультминутка	Выполняют  аутомануальный комплекс
закрепление	познавательные	Задание: используя алгоритм Дейкстра, найдите кратчайшие расстояния между вершиной а и всеми другими вершинами. Определите порядок и размер графа. Самостоятельно: используя алгоритм Прима-Крускала, постройте минимальное остовное дерево. Вернемся к заданию ЕГЭ и решим его применив алгоритм Дейкстра Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам). Работа с кейсами. Задание: используя алгоритм Прима-Крускала найдите на графе минимальное остовное дерево.  Является ли оно универсальным?   Используя жадный алгоритм и алгоритм Дейкстра найдите кратчайшее расстояние от А до К. Сделайте вывод.    2) Алгоритм Дейкстра A B C D E F G K 0 ¥ ¥ ¥ ¥ ¥ ¥ ¥ 6 17 11 ¥ ¥ ¥ ¥ 17 11 25 ¥ ¥ ¥ 17 25 13 ¥ ¥ 17 25 27 34 27 34 Задача: имеется n городов, которые нужно объединить в единую телефонную сеть. Для этого достаточно проложить (n-1) телефонных линий между городами. Как соединить города так, чтобы суммарная стоимость соединений (телефонного кабеля) была минимальна? Является ли решение универсальным?    Суммарный вес дерева равен 37. Это минимальное остовное дерево не уникально: удалением ребра (c,d) и добавлением ребра (a,b) получается новое минимальное остовное дерево. Задача: удалите лишние ребра и получите минимальное остовное дерево. Ответ:     С графами связаны некоторые классические задачи. Самая известная из них – задача коммивояжёра. Коммивояжёр (фр. commis voyageur) — бродячий торговец. Задача коммивояжёра — важная задача транспортной логистики, отрасли, занимающейся планированием транспортных перевозок. Коммивояжёру, чтобы распродать нужные и не очень нужные в хозяйстве товары, следует объехать n пунктов и в конце концов вернуться в исходный пункт. Требуется определить наиболее выгодный маршрут объезда. В качестве меры выгодности маршрута (точнее говоря, невыгодности) может служить суммарное время в пути, суммарная стоимость дороги, или, в простейшем случае, длина маршрута.	Выполняют задание Сообщение учащегося, владеющего навыками решения задачи
Домашнее задание		§ 44 стр. 109-112, № 2 стр. 119 Дополнительно: сформулируйте критерий минимальности остова.	записывают домашнее задание
Включение в систему знаний и повторение. Рефлексия.	коммуникативные	Подведем итоги нашего урока.   Предлагаю устно закончить следующие предложения. "На сегодняшнем уроке я понял, я узнал, я разобрался…";  "Я похвалил бы себя…";  "Сегодня мне удалось…";  "Я сумел…"; "Было интересно…"; "Было трудно…"; "Я понял, что…"; "Теперь я могу…"; "Я научился…". Закончить наш урок хочу словами Шарля де Голля, французского генерала второй мировой войны и выдающегося политика: "Всегда выбирайте самый трудный путь, на нем вы не встретите конкурентов!"	Ответы детей