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