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

Рыжих Светлана Николаевна

Урок по учебнику К.Ю. Полякова и Е.А. Еремина (углубленный уровень)

Скачать:

ВложениеРазмер
Файл tehnologicheskaya_karta.docx529.04 КБ
Файл prilozhenie_6.docx169.38 КБ
Файл prilozhenie_5.docx80.29 КБ
Файл prilozhenie_4.docx10.9 КБ
Файл prilozhenie_2.docx96.05 КБ
Файл prilozhenie_1.pptm252.76 КБ

Предварительный просмотр:

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

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

ФИО (полностью): Рыжих Светлана Николаевна

  1. Место работы: МБОУ «Средняя общеобразовательная школа № 35 им. К.Д. Воробьева» г. Курска
  2. Должность: учитель информатики
  3. Предмет: информатика
  4. Класс: 11 класс.
  5. Тема и номер урока: «Алгоритмизация и программирование», урок № 86
  6. Учебник:                                                                                                                               

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

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

Тема урока

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

Тип урока

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

Цель урока

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

Планируемый

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

в том числе

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

Предметные        

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

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

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

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

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

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

Личностные

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

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

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

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

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

Ресурсы

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

Этапы урока

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

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

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

Оргмомент

личностные

Приветствие

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

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

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

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

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

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

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

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

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

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

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

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).
http://kpolyakov.spb.ru/cms/images/84.gifТак как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта Б в пункт Д.

(Ответ 8)

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

A

B

C

D

E

F

Z

A

4

6

30

B

3

4

C

11

27

D

4

7

10

E

4

8

F

2

Z

29

Сколько существует таких маршрутов из A в Z, которые проходят через 6 и более населенных пунктов? Пункты A и Z при подсчете учитывать. Два раза проходить через один пункт нельзя. (Ответ 5)

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, С, Х, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город Т?

http://kpolyakov.spb.ru/cms/images/315.gif

(Ответ: 66)

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 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. И так пока не дойдем до начала.
Если в результате такого обхода у нас на каком-то шаге совпадут значения для нескольких вершин, то можно взять любую из них — несколько путей будут иметь одинаковую длину.

Ответы детей

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

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

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

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

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

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

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

         

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

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

А

В

С

D

E

0

1

5

3

4

5

3

4

4

4

   

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

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

закрепление

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

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

Ответ:

a

b

h

i

c

g

f

d

e

0

4

8

8

12

15

12

9

15

12

11

15

12

25

21

15

19

21

19

21

21

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

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

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

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

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

Задание: используя алгоритм Прима-Крускала найдите на графе минимальное остовное дерево.  Является ли оно универсальным?http://urban-sanjoo.narod.ru/kruskal/g_kruskal00.gif

http://urban-sanjoo.narod.ru/kruskal/g_kruskal07.gif

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

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

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

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) получается новое минимальное остовное дерево.

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

Ответ:http://files3.vunivere.ru/workbase/00/01/16/69/images/image004.gif

http://files3.vunivere.ru/workbase/00/01/16/69/images/image001.gifhttp://files3.vunivere.ru/workbase/00/01/16/69/images/image001.gifhttp://files3.vunivere.ru/workbase/00/01/16/69/images/image001.gifhttp://files3.vunivere.ru/workbase/00/01/16/69/images/image001.gifhttp://files3.vunivere.ru/workbase/00/01/16/69/images/image001.gifhttp://files3.vunivere.ru/workbase/00/01/16/69/images/image001.gifhttp://files3.vunivere.ru/workbase/00/01/16/69/images/image001.gif

        

        

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

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

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

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

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

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

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

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

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

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

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

Рефлексия.

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

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

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

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

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

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

 "Я сумел…";

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

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

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

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

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

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

Ответы детей



Предварительный просмотр:

Задача коммивояжёра

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

Доподлинно неизвестно, когда задача коммивояжера была поставлена в первый раз. Но в 1832 году появилась книга «Коммивояжёр — как он должен вести себя и что должен делать для того, чтобы доставлять товар и иметь успех в своих делах — советы старого курьера», и в ней описывалась данная проблема.

Условия задачи говорят о критерии выгодности маршрута (с точки зрения расстояния, дешевизны и других составляющих). Маршрут должен проходить только один раз через каждый город, а после – возвращаться в начальную точку.

Начиная с 1960 года, задачу коммивояжера начали изучать программисты, экономисты, химики, биологи и представители других наук. А все по той простой причине, что к ее решению сводятся и решения огромного количества практических задач в разных областях науки и жизни.

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

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

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

 По сей день известно только одно надежное решение – полный перебор вариантов, число которых равно факториалу значения N-1. Это число с увеличением N растет очень быстро, быстрее чем любая степень N. Уже для N=20 такое решение требует огромного времени вычислений: компьютер, проверяющий 1000 вариантов в секунду, будет решать задачу «в лоб» около четырех миллионов лет. Поэтому математики прилагали большие усилия для того, чтобы сократить перебор – не рассматривать те варианты, которые заведомо не дают лучших результатов, чем уже полученные.

задача коммивояжера

        https://im0-tub-ru.yandex.net/i?id=4dd2d78ec397b9668c75ec16e2ceb239&n=13

        https://im0-tub-ru.yandex.net/i?id=16211fccf1423e6819f4eac5111684d2&n=33&w=287&h=150



Предварительный просмотр:

Самостоятельно:

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

Задача: найдите кратчайшее расстояние между вершиной 1 и 6.

http://files3.vunivere.ru/workbase/00/01/16/69/images/image001.gif

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

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

        



Предварительный просмотр:

Аутомануальный комплекс (массаж) 

Разогреть ладони энергичным потиранием. Указательными пальцами осуществлять вкручивающие движения по часовой и против часовой стрелке – 6-8 раз в каждую сторону. 
• Точка на лбу между бровями. 
• По краям крыльев носа. 
• В среднюю линию между нижней губой и верхним краем подбородка. 
• В височной ямке (парные). 
• В области козелка (парные). 
• Чуть выше роста волос под основанием черепа. 



Предварительный просмотр:

ЗАДАЧА О СЕМИ МОСТАХ КЕНИГСБЕРГА

Известно, что великий швейцарский математик Эйлер создал целое направление науки, решая задачу о семи кенигсбергских мостах. Существует легенда, что жители Кенигсберга любили прогуливаться по улицам трех "слившихся" в единое целое средневековых городов: Альштадта, Лебенихта и Кнайпхофа - но терпеть не могли зря топтать свои башмаки. А города эти были соединены между собой семью мостами. И вот будто бы экономные горожане однажды задумались: а можно ли пройти по всем мостам так, чтобы на каждом из них побывать лишь один раз и вернуться к месту, откуда начал прогулку?

Эйлера задача заинтересовала. "Никто еще до сих пор не смог это проделать, но никто и не доказал, что это невозможно... Для решения недостаточны ни геометрия, ни алгебра, ни комбинаторское искусство", - так писал он своему коллеге, итальянскому математику и инженеру...

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

На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:http://lmatrix.ru/uploads/images/130380594910.jpg

 

Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.

Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.

Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

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

Созданная Эйлером теория графов нашла очень широкое применение: например, её используют при изучении транспортных и коммуникационных систем, в частности, для маршрутизации данных в Интернете.

          Любопытно, что другое решение задачи предложил кайзер Вильгельм. На приёме ему поднесли карту Кёнигсберга и предложили решить загадку семи мостов. Вильгельм не растерялся, а тут же приказал построить восьмой мост. После чего задача стала легкорешаемой. 

Третье решение придумали речники. За небольшую плату они предлагают перевезти всех, кому не хватает моста для решения задачки.

Источник: http://www.liveinternet.ru/users/vl866911/post254869616/   


Предварительный просмотр:


Подписи к слайдам:

Слайд 1

мин. 4 Время тестирования Начать тестирование 6 Всего заданий Введите фамилию и имя Тест по теме Графы

Слайд 2

Далее 1 Задание 1 бал. 1 2 3 Что такое граф? Это объект, в котором вершины связаны между собой по принципу «многие ко многим» Это набор узлов (вершин) и связей между ними (ребер) Это информация об узлах и связях между ними

Слайд 3

Далее 2 Задание 1 бал. 1 2 3 Как называется таблица, в которой хранится информация об узлах и связях графа? Двумерная матрица Весовая матрица Матрица смежности

Слайд 4

Далее 3 Задание 3 бал. Выберите все правильные ответы! 1 2 3 4 Что означает единица на главной диагонали смежной матрицы? Ребро, которое начинается и заканчивается в одной и той же вершине Между узлами нет связи Между узлами есть связь Имеется петля

Слайд 5

Далее 4 Задание 1 бал. Введите ответ: Как называется граф, в котором между парой узлов существует путь – последовательность ребер, по которым можно перейти от одного узла к другому?

Слайд 6

Далее 5 Задание 1 бал. 1 2 3 Чем отличается орграф от неориентированного графа? Матрицей смежности Вместо ребер используют дуги Весом ребра

Слайд 7

Итоги 6 Задание 1 бал. 1 2 3 4 Какой граф называют взвешенным? Построенный с помощью дуг Построенный с помощью ребер На ребрах несущий дополнительную информацию Неориентированный граф

Слайд 8

Затрачено времени Выход Снова бал. Всего заданий Ошибки в выборе ответов на задания: Набранных баллов Правильных ответов Оценка Подождите! Идет обработка данных Результаты тестирования


По теме: методические разработки, презентации и конспекты

Презентация к уроку информатики 3класс по теме "Ориентированный граф"

Урок проходит в игровой форме , учащиеся помогают Бабе яге выполнить задания , тем самым знакомятся с новыми понятиями....

Разработка урока по теме: "Пути в графах"

Данный урок разработан для 9 класса. Цели урока: Обобщить и систематизировать знания о графах ,их видах, свойствах. Методы обучения: наглядный, исследовательский, проблемно-поисковый. Оборуд...

Урок геометрии в 7 классе "Применение граф - схем при решении задач"

Урок  на тему "Применение граф-схем при решении задач". Граф -схемой называется некоторая разветленная сеть, состоящая из направленных стрелок, соединяющих изучаемые понятия и суждения. Граф-схем...

Урок по теме «Графические информационные модели. Графы»

Разработка урока, отражающая преемственность в обучении....

Подготовка к ЕГЭ по информатике. Тест на тему "Поиск путей в графе".

Этот материал по теме "Поиск путей в графе" позволит ученикам, сдающим ЕГЭ по информатике проверить свои знания....

Задача 13 ЕГЭ по информатике и способы ее решения. Количество путей в графе

В типичной задаче 13 из единого государственного экзамена по информатике даётся ориентированный граф и, как правило, просят найти количество путей из одной вершины графа в другую, удовлетвор...

Нахождение кратчайшего пути в графе с ограничениями

Подготовка к ОГЭ. Задание №4 .Построение графа, нахождение кратчайшего пути. Анализ графа....