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