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