Моделирование: графы и поиск оптимального пути
Цели и задачи
- Цель урока по SMART: к концу урока учащиеся научатся различать материальные и информационные модели, представлять отношения в виде таблиц и графов, составлять весовую матрицу и находить оптимальный путь в небольшом графе, объясняя выбор алгоритма.
- Различать материальные и информационные модели, определять назначение модели и приводить примеры задач, решаемых с помощью моделирования.
- Представлять простое отношение между объектами в виде таблицы, графа и весовой матрицы.
- Различать вершину, ребро, путь, ориентированный и неориентированный граф; определять длину пути как сумму весов рёбер.
- Находить кратчайший путь перебором вариантов и проверять результат по весовой матрице; сотрудничать в паре и создавать собственную модель реальной ситуации.
Планируемые результаты
Личностные
- Осознают практическую ценность моделирования при планировании маршрутов, навигации и принятии решений.
- Проявляют ответственное отношение к проверке результата модели и понимание того, что модель отражает не все свойства реального объекта.
- Снижают тревожность перед заданиями ОГЭ благодаря освоению понятного алгоритма работы с таблицами и графами.
- Проявляют интерес к применению информатики в профессиях, связанных с транспортом, логистикой, программированием и анализом данных.
Метапредметные
- Выделяют существенные свойства объекта и выбирают подходящую форму информационной модели.
- Преобразуют информацию из текста в таблицу, граф и весовую матрицу.
- Планируют последовательность поиска пути, сравнивают варианты и аргументируют вывод.
- Работают в паре, распределяют роли, используют электронную доску или презентацию для проверки результата.
Предметные
- Знать различия между материальными и информационными моделями и назначение моделирования.
- Уметь распознавать табличную модель как представление отношения между объектами.
- Знать понятия «вершина», «ребро», «путь», «ориентированный граф», «неориентированный граф», «вес ребра».
- Уметь строить простой граф по описанию маршрутов и составлять его весовую матрицу.
- Уметь находить оптимальный путь в небольшом взвешенном графе, складывая веса рёбер и сравнивая результаты.
Универсальные учебные действия (УУД)
Личностные УУД
- Определяют личный смысл изучения графов через задачу выбора наиболее короткого или дешёвого маршрута.
- Оценивают собственную готовность применять алгоритм и формулируют область, где это умение может пригодиться.
- Понимают необходимость критически проверять результаты компьютерной модели.
Регулятивные УУД
- Формулируют цель практической работы и планируют шаги построения графа.
- Контролируют правильность обозначения вершин, рёбер и направления дуг.
- Сверяют длины найденных путей с эталоном и исправляют ошибки в матрице.
- Оценивают результат по критериям и фиксируют затруднение для дальнейшей работы.
Познавательные УУД
- Классифицируют модели по способу представления и назначению.
- Устанавливают соответствие между текстом, таблицей, графом и матрицей.
- Анализируют несколько маршрутов, вычисляют их длину и выбирают оптимальный.
- Моделируют реальную транспортную сеть и преобразуют её в формальную структуру.
Коммуникативные УУД
- Распределяют роли в паре: аналитик проверяет вычисления, оформитель строит граф.
- Задают уточняющие вопросы о направлении движения и значении веса ребра.
- Аргументируют выбор оптимального пути, используя численные данные.
- Согласуют итоговую модель и корректно комментируют решение другой пары.
Подготовка учителя к уроку
- Подготовить презентацию или интерактивную доску с изображениями глобуса, схемы маршрута, таблицы связей и двух графов: ориентированного и неориентированного.
- Распечатать карточки для парной работы с транспортной сетью из пяти вершин и шестью дорогами, указав длину каждой дороги; подготовить по одной карточке на пару.
- Распечатать лист самооценки и задания трёх уровней по одному комплекту на каждого ученика.
- Вывести на доску памятку: «вершина — объект; ребро — связь; путь — последовательность рёбер; длина пути — сумма весов».
- Подготовить пустой шаблон весовой матрицы размером 5 на 5 для каждой пары и один увеличенный шаблон для демонстрации.
- Подготовить компьютеры или планшеты с интерактивной доской/редактором схем; при отсутствии устройств использовать бумажные карточки и маркеры.
- Раздать цветные стикеры двух цветов для обозначения вершин и рёбер, линейки и маркеры на каждую группу.
- Подготовить творческое задание: придумать сеть из четырёх-пяти объектов, представить её графом и предложить задачу поиска оптимального пути.
- Разместить на доске контрольный вопрос ОГЭ-формата: «Какова длина кратчайшего пути между двумя вершинами при заданных весах рёбер?»
Ход урока
Этап 1. Организационный момент и мотивация (3 мин)
Цель этапа: включить учащихся в практическую задачу и показать применение графов в повседневной жизни.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель приветствует класс и показывает на экране схему маршрутов между пятью пунктами. «Здравствуйте, ребята. Сегодня мы попробуем решить задачу, с которой ежедневно работают навигаторы, службы доставки и транспортные компании. На схеме несколько дорог, у каждой есть длина. Как выбрать маршрут, чтобы пройти из пункта А в пункт Е быстрее всего?» | Рассматривают схему, называют возможные варианты: «Нужно сравнить длины маршрутов», «Найти самый короткий путь». |
2 мин | Учитель объявляет приём «Проблемный вопрос»: «Пока не используем готовое правило. Сначала предположите, какая модель поможет записать все связи и не потерять ни одну дорогу. В конце урока мы вернёмся к этому вопросу и решим его точно. Знание графов также встречается в заданиях ОГЭ, поэтому будем работать так, как требуется при экзаменационном анализе данных». | Формулируют предположения: «Таблица», «Схема», «Граф». Записывают тему урока и отмечают, что хотят научиться находить кратчайший маршрут. |
Завершение этапа: учитель подводит итог: «Мы увидели реальную задачу выбора маршрута. Теперь вспомним, что такое модель и какие задачи с её помощью решают».
Этап 2. Актуализация знаний о моделях и табличном представлении (6 мин)
Цель этапа: актуализировать понятия «модель», «материальная модель», «информационная модель» и связь таблицы с отношением объектов.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель показывает изображения глобуса, макета здания, схемы метро и таблицы расписания. «Рассмотрите четыре изображения. Что из них можно потрогать, а что существует только как описание или схема? Какое общее назначение у всех этих объектов? Не нужно воспроизводить определение дословно — объясните смысл». | Классифицируют примеры: «Глобус и макет — материальные модели; схема и расписание — информационные». Формулируют: «Модель заменяет реальный объект или процесс и сохраняет важные для задачи свойства». |
2 мин | Учитель организует «Подумай — обсуди в паре — поделись». «Сначала за 30 секунд самостоятельно назовите задачу, которую можно решить с помощью модели. Затем обсудите ответ с соседом и выберите один пример для класса». | Индивидуально записывают пример, затем обсуждают его в паре. Представляют варианты: «Рассчитать маршрут», «спроектировать дом», «предсказать погоду», «рассчитать расход материалов». |
2 мин | Учитель выводит таблицу отношения: «Город отправления — город назначения — время в пути». «Что обозначают строки? Можно ли из таблицы получить сведения о связях между объектами? Как изменится таблица, если дорога действует только в одном направлении?» | Называют строки описаниями связей между объектами. Делают вывод: «Таблица может показывать отношение. При одностороннем движении нужно учитывать направление от одного объекта к другому». |
Завершение этапа: учитель подводит итог: «Модель выбирают под задачу, а таблица позволяет точно записать отношения между объектами. Но для сети дорог нам нужна форма, в которой связи видны сразу. Постараемся её открыть».
Этап 3. Постановка проблемы и целеполагание (4 мин)
Цель этапа: выявить затруднение при выборе оптимального маршрута и сформулировать план открытия нового знания.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель раздаёт парам карточку с отношениями: А—Б 4 км, А—В 2 км, Б—В 1 км, Б—Г 3 км, В—Г 6 км, Г—Д 2 км, В—Д 10 км. «Попробуйте быстро назвать кратчайший путь от А до Д. Записывайте не только названия пунктов, но и сумму расстояний. Что мешает сделать это сразу и без ошибок?» | Пары перебирают маршруты, например: «А–В–Д = 12 км», «А–Б–Г–Д = 9 км», «А–В–Б–Г–Д = 8 км». Формулируют затруднение: «Нужно не забыть варианты и правильно представить связи». |
2 мин | Учитель фиксирует на доске вопросы: «Как называется такая схема? Что в ней является объектами и связями? Как записать веса? Как найти оптимальный путь?» Затем говорит: «Сформулируйте цель урока одним предложением и предложите порядок действий». | Формулируют цель: «Научиться строить граф и находить кратчайший путь». Предлагают план: выделить вершины, соединить их рёбрами, указать направления и веса, составить матрицу, сравнить длины путей. |
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Завершение этапа: учитель подводит итог: «Проблема ясна: одной интуиции недостаточно, нужна точная модель и алгоритм. Переходим к открытию понятий графа и его элементов».
Этап 4. Открытие нового знания: граф и весовая матрица (10 мин)
Цель этапа: сформировать представление о графе, его элементах, направлениях рёбер, весе и весовой матрице.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель строит на доске граф по карточке. «Кружки обозначают вершины — пункты сети, линии между ними — рёбра, то есть связи. Последовательность вершин, соединённых рёбрами, называется путём. Если можно двигаться по дороге в обе стороны, граф неориентированный. Если стрелка разрешает движение только от А к Б, граф ориентированный. Посмотрите на схему и назовите её элементы». | Называют вершины А, Б, В, Г, Д, перечисляют рёбра и один путь: «А–Б–Г–Д». Определяют граф как неориентированный, потому что дороги имеют двустороннее движение. |
3 мин | Учитель подписывает длины рёбер. «Число рядом с ребром называется его весом. Вес может означать расстояние, время, стоимость или расход топлива. Длина пути равна сумме весов входящих в него рёбер. Например, для пути А–Б–Г–Д получаем $4+3+2=9$ км. Что будет весом, если мы ищем самый дешёвый маршрут?» | Вычисляют длины предложенных путей. Отвечают: «Весом будет стоимость участка, а оптимальным — путь с минимальной общей стоимостью». |
4 мин | Учитель выводит шаблон матрицы. «В строке указываем начальную вершину, в столбце — конечную. В клетке записываем вес ребра. Если непосредственной дороги нет, ставим прочерк или условное обозначение бесконечности, принятое в задании. На главной диагонали ставим 0: путь из вершины в неё же не требует движения. Для неориентированного графа матрица симметрична». Учитель вместе с классом заполняет строки А и Б. | Заполняют в тетрадях первые строки матрицы: для А в столбцах Б и В записывают 4 и 2, в остальных клетках — отсутствие связи; для Б в столбцах А, В, Г записывают 4, 1, 3. Замечают симметрию матрицы. |
0,5 мин | Учитель показывает стрелочный вариант одного ребра. «Если направление изменилось, запись А→Б не означает автоматически Б→А. Поэтому при ориентированном графе матрица может быть несимметричной». | Сравнивают два варианта и формулируют различие: «В ориентированном графе направление учитывается отдельно». |
0,5 мин | Учитель задаёт проверочный вопрос ОГЭ-формата: «Если путь проходит по рёбрам с весами 5, 2 и 7, какова его длина? Что нужно сделать перед сравнением двух путей?» | Отвечают: «14». Формулируют правило: «Сложить веса каждого пути, затем сравнить суммы». |
Запись в тетрадях
Модель — упрощённое представление объекта, процесса или явления, сохраняющее существенные для задачи свойства. Граф состоит из вершин и рёбер. Путь — последовательность вершин, соединённых рёбрами. Вес пути равен сумме весов его рёбер. В неориентированном графе движение по ребру возможно в обе стороны, в ориентированном — только по стрелке. В весовой матрице строка и столбец соответствуют вершинам, а клетка показывает вес непосредственного ребра.
Завершение этапа: учитель подводит итог: «Мы построили граф и научились читать его матрицу. Теперь применим новые понятия к полной задаче: построим модель, проверим варианты и выберем оптимальный путь».
Этап 5. Практическая работа в парах: поиск оптимального пути (9 мин)
Цель этапа: закрепить построение графа, составление весовой матрицы и поиск кратчайшего пути в сотрудничестве.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель раздаёт карточки с условием: «Есть пункты А, Б, В, Г, Д. Дороги имеют длины: А–Б 4 км, А–В 2 км, Б–В 1 км, Б–Г 3 км, В–Г 6 км, Г–Д 2 км, В–Д 10 км. Все дороги двусторонние. Постройте граф и обозначьте веса». Учитель напоминает роли: аналитик проверяет числа, оформитель строит схему. | Распределяют роли. Наносят пять вершин, соединяют их семью рёбрами и подписывают веса. |
3 мин | Учитель даёт инструкцию: «Заполните весовую матрицу. На диагонали поставьте 0, в клетках отсутствующих прямых дорог — прочерк. Проверьте симметрию: если в А–Б стоит 4, что должно быть в Б–А?» | Заполняют матрицу, отвечают: «В Б–А тоже должно быть 4». Сверяют матрицу в паре. |
3 мин | Учитель предлагает найти путь от А до Д: «Перечислите не менее трёх простых маршрутов, вычислите длину каждого и выберите минимальный. Не утверждайте, что первый найденный путь оптимален, пока не сравнили варианты». Учитель консультирует пары и фиксирует типичные ошибки. | Записывают и сравнивают варианты: А–В–Д: $2+10=12$ км; А–Б–Г–Д: $4+3+2=9$ км; А–В–Б–Г–Д: $2+1+3+2=8$ км. Делают вывод: кратчайший найденный путь — А–В–Б–Г–Д, 8 км. |
1 мин | Учитель организует взаимопроверку: «Обменяйтесь листами с соседней парой. Проверьте три пункта: все ли рёбра есть, симметрична ли матрица, совпадает ли сумма выбранного пути». | Проверяют работу соседней пары по трём критериям, отмечают одну сильную сторону и одну возможную коррекцию. |
Эталон решения
1. Строим граф с вершинами А, Б, В, Г, Д и заданными рёбрами. 2. Перечисляем допустимые простые пути от А до Д. 3. Вычисляем длины: $L(А–В–Д)=2+10=12$ км; $L(А–Б–Г–Д)=4+3+2=9$ км; $L(А–В–Б–Г–Д)=2+1+3+2=8$ км. 4. Сравниваем значения: $8<9<12$. Оптимальный путь — А–В–Б–Г–Д, его длина равна 8 км.
Завершение этапа: учитель подводит итог: «Вы убедились, что граф превращает текстовую задачу в точную модель, а матрица помогает не пропустить связь. Теперь каждый самостоятельно проверит, умеет ли применять этот алгоритм без подсказки пары».
Этап 6. Самостоятельная работа с ИКТ и творческое задание (8 мин)
Цель этапа: индивидуально проверить освоение алгоритма и применить его в новой ситуации через создание собственной модели.
Время | Действие учителя | Действие учеников |
|---|---|---|
4 мин | Учитель предлагает индивидуальную карточку: «Дан ориентированный граф: А→Б с весом 3, А→В с весом 7, Б→В с весом 2, Б→Г с весом 6, В→Г с весом 1. Найдите кратчайший путь из А в Г. Сначала выпишите возможные маршруты, затем посчитайте их длины». На экране размещён таймер и критерии: правильное направление, полный маршрут, верная сумма. | Самостоятельно находят маршруты: А→Б→Г: $3+6=9$, А→В→Г: $7+1=8$, А→Б→В→Г: $3+2+1=6$. Записывают ответ: «Кратчайший путь А→Б→В→Г, длина 6». |
2 мин | Учитель просит выполнить самопроверку по эталону на экране. «Сравните не только итоговое число, но и направление рёбер. Если у вас получился путь В→Б, объясните, есть ли такая стрелка в условии». | Сверяют решение, исправляют ошибки, отмечают результат в листе самооценки. |
2 мин | Учитель даёт творческое задание: «Создайте мини-модель сети из четырёх объектов: остановок, комнат, сайтов или пунктов доставки. Нарисуйте вершины и рёбра, добавьте веса, сформулируйте вопрос о кратчайшем или самом дешёвом пути. Используйте бумажный шаблон или редактор схем на компьютере». | Индивидуально или в мини-паре создают граф. Например: сеть остановок с расстояниями 2, 4, 5 и 3 км. Подписывают задачу и предлагают один оптимальный маршрут. |
Завершение этапа: учитель подводит итог: «Алгоритм работает и для готовой схемы, и для созданной вами модели. Осталось осмыслить, какие понятия стали инструментами решения и где возникли затруднения».
Этап 7. Рефлексия, оценивание и домашнее задание (5 мин)
Цель этапа: обобщить изученное, провести самооценку и обеспечить перенос навыка в самостоятельную работу.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель проводит рефлексию «Светофор». «Поднимите зелёную карточку, если можете построить граф и найти кратчайший путь; жёлтую — если нужна тренировка матрицы или направлений; красную — если пока не можете объяснить различия. Назовите конкретный шаг, который вызвал затруднение». | Показывают карточку, называют затруднения: «Путаю ребро и путь», «не всегда учитываю направление», «ошибаюсь в сумме весов». |
1 мин | Учитель предлагает билет на выход: «Запишите две короткие фразы: что такое весовая матрица и как проверить, что путь оптимален». | Записывают: «Матрица показывает веса прямых связей между вершинами»; «Нужно сравнить длины допустимых путей или применить алгоритм поиска кратчайшего пути». |
2 мин | Учитель объясняет домашнее задание и критерии. «Выберите обязательный уровень, а желающие выполняют повышающий или творческий. Номера страниц и конкретный учебник не нужны: используйте материал урока и любую подходящую схему из вашей образовательной линии». | Записывают выбранный уровень домашней работы, задают уточняющие вопросы и сдают билет на выход. |
Критерии оценивания практической работы
- «5» — правильно построен граф, указаны все семь рёбер и их веса, весовая матрица заполнена без ошибок, найден кратчайший путь А–В–Б–Г–Д длиной 8 км и приведено сравнение не менее трёх маршрутов.
- «4» — граф и оптимальный путь определены верно, но допущена одна неточность в матрице или не полностью записано сравнение вариантов; вычисление длины пути выполнено правильно.
- «3» — различены вершины и рёбра, построена основа графа, но допущены ошибки в весах, направлении или выборе оптимального пути; ученик исправляет решение после подсказки.
- Творческое задание оценивается дополнительно: 1 балл за связную модель, 1 балл за корректные веса, 1 балл за сформулированную задачу, 1 балл за обоснованный оптимальный путь.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Что такое вершина, ребро и путь в графе? | Проверка осознания базовых понятий графовой модели. |
Как изменяется весовая матрица, если граф становится ориентированным? | Выявление понимания роли направления и возможной несимметричности матрицы. |
Какие действия нужно выполнить, чтобы доказать оптимальность найденного пути? | Проверка понимания алгоритма сравнения маршрутов. |
Какой шаг сегодня оказался самым сложным и почему? | Выявление точек затруднения и планирование последующей коррекции. |
Завершающее слово учителя
«Сегодня мы научились превращать сеть объектов и связей в графовую модель. Вы различали вершины, рёбра и пути, учитывали направление и вес, заполняли матрицу и находили кратчайший маршрут. Типичная ошибка — выбрать первый подходящий путь или сложить не те рёбра, поэтому всегда записывайте полный маршрут и проверяйте сумму. На следующем уроке мы продолжим работать с алгоритмами обработки графов и рассмотрим более эффективные способы поиска оптимального решения».
Домашнее задание
Уровень | Что задать | Зачем |
|---|---|---|
Базовый (обязательный) | Выполнить 3 задания: классифицировать пять примеров моделей как материальные или информационные; построить неориентированный граф по описанию сети из четырёх объектов; найти кратчайший путь между двумя заданными вершинами и вычислить его длину. | Закрепляет различия между видами моделей, элементы графа и алгоритм сложения весов. При проверке смотреть на полноту графа, подписи рёбер и правильность маршрута. |
Средний (повышающий) | Решить 4 задачи по графам: составить таблицу отношения для сети, преобразовать её в граф, заполнить весовую матрицу и найти оптимальный путь в ориентированном графе с пятью вершинами. | Формирует умение преобразовывать информацию между представлениями и учитывать направление. При проверке смотреть на соответствие таблицы, графа и матрицы. |
Продвинутый (дополнительный) | Создать модель реальной сети из пяти-шести объектов: остановок, пунктов доставки, комнат или веб-страниц. Назначить рёбрам расстояния, время или стоимость, представить сеть графом и матрицей, сформулировать задачу и обосновать оптимальный путь. | Развивает творческое моделирование, функциональную грамотность и аргументацию. При проверке смотреть на реалистичность связей, корректность весов и доказательство выбора пути. |
Контрольные вопросы перед выходом: «Чем материальная модель отличается от информационной? Что обозначают вершины и рёбра? Как определить длину пути? Почему в ориентированном графе нельзя автоматически двигаться по ребру в обратную сторону? Какие действия подтверждают, что найденный путь оптимален?»
