План урока на тему:

Деревья и дискретные игры

Информатика11 класс64 раздела
Деревья и дискретные игры

Информатика · 11 класс · Комбинированный · 45 мин

Деревья. Дискретные игры двух игроков с полной информацией

Цели и задачи

  • Цель по SMART: к концу урока научиться строить дерево игры для дискретной игры двух игроков с полной информацией, определять выигрышную стратегию первого или второго игрока и обосновывать её анализом позиций.
  • Сформировать представление о дереве игры как модели последовательности ходов, состояний и возможных исходов.
  • Научиться различать выигрышные и проигрышные позиции и применять правило анализа с конца игры.
  • Развивать умение строить рассуждение по алгоритму, проверять стратегию на всех возможных ответах соперника и аргументировать вывод в паре.
  • Показать связь алгоритмов решения игр с рекурсивными процедурами, перебором состояний и задачами повышенной сложности ЕГЭ по информатике.

Планируемые результаты

Личностные

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

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

  • Строить информационную модель игры в виде дерева состояний и переходов между ними.
  • Выделять существенные условия задачи: начальную позицию, допустимые ходы, условие выигрыша и порядок ходов.
  • Планировать решение от конечных позиций к начальной, фиксируя результаты анализа в таблице или на схеме.
  • Работать в паре, задавать уточняющие вопросы, приводить контрпример и аргументированно защищать вывод.
  • Осуществлять самопроверку по критериям: полнота дерева, корректность конечных позиций, доказанность стратегии.

Предметные

  • Знать понятия «вершина», «ребро», «лист», «корень», «позиция», «ход», «выигрышная позиция» и «проигрышная позиция».
  • Уметь представлять последовательность ходов двух игроков в виде дерева игры.
  • Уметь определять тип позиции по результатам возможных ходов: позиция выигрышная, если существует ход в проигрышную позицию; позиция проигрышная, если все ходы ведут в выигрышные позиции.
  • Уметь находить выигрышную стратегию одного из игроков и объяснять, почему соперник не может ей помешать.
  • Владеть алгоритмом анализа небольшой дискретной игры с полной информацией от листьев дерева к корню.

Универсальные учебные действия (УУД)

Личностные УУД

  • Определяют личный уровень понимания темы и формулируют затруднение после диагностического задания.
  • Соотносят результат решения с требованием доказать стратегию для всех ответов соперника.
  • Проявляют ответственность за собственный вклад в парную исследовательскую работу.
  • Формулируют учебную мотивацию через связь деревьев игр с алгоритмическим мышлением.

Регулятивные УУД

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

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

  • Выделяют состояние игры и возможные переходы из него.
  • Классифицируют позиции по результату при оптимальной игре.
  • Устанавливают причинно-следственную связь между конечными позициями и стратегией.
  • Моделируют игру с помощью дерева, таблицы и рекурсивного описания.
  • Проверяют гипотезу построением полного набора ответов соперника.

Коммуникативные УУД

  • Распределяют роли в паре: один строит дерево, другой проверяет полноту ходов.
  • Формулируют вопросы к условию и уточняют смысл выигрышной позиции.
  • Объясняют партнёру каждый переход в дереве и приводят доказательство стратегии.
  • Сравнивают два решения и корректно указывают на контрпример или пропущенный ход.
  • Представляют итоговое решение классу в сжатой логической форме.

Подготовка учителя к уроку

  • Подготовить презентацию или интерактивную доску с обозначениями вершины, ребра, листа и корня дерева.
  • Распечатать карточки для парной работы: по одной карточке базового уровня и одной карточке повышенного уровня на каждую пару.
  • Подготовить индивидуальный лист самопроверки с алгоритмом: построить дерево, отметить листья, определить позиции снизу вверх, записать стратегию.
  • Вывести на доску условие стартовой игры: на столе лежит одна куча из 7 фишек; за ход игрок добавляет 1 или 2 фишки; выигрывает тот, кто первым получает ровно 10 фишек.
  • Подготовить отдельную схему с правилами: «есть ход в проигрышную позицию — позиция выигрышная» и «все ходы ведут в выигрышные позиции — позиция проигрышная».
  • Распечатать по одному листу с критериями оценивания на ученика и по одному листу-эталону на пару.
  • Подготовить маркеры двух цветов или виртуальные инструменты доски для обозначения выигрышных и проигрышных позиций.
  • Организовать таймер на 2–4 минуты для диагностических и парных заданий.
  • Подготовить домашнее задание трёх уровней в виде таблицы на экране или в раздаточном материале.
  • Оборудование: компьютер учителя, проектор или интерактивная доска, доска, маркеры, карточки, листы самопроверки.

Ход урока

Этап 1. Организационный момент и мотивация (3 мин)

Цель этапа: включить учащихся в исследовательскую деятельность и показать практическую ценность анализа игры.
Время
Действие учителя
Действие учеников
1 мин
Учитель приветствует класс и обращается к ученикам: "Сегодня мы будем не просто решать игру, а доказывать, что выбранная стратегия работает при любом ответе соперника. Это важное отличие алгоритмического решения от догадки. Проверьте, что у вас есть тетрадь, ручка и лист для схемы."
Проверяют готовность, записывают дату и тему урока: «Деревья. Дискретные игры двух игроков с полной информацией». Формулируют ожидание: «Нужно научиться находить гарантированный выигрыш».
2 мин
Учитель показывает на доске позицию: "На столе 7 фишек. Игрок за ход добавляет 1 или 2 фишки. Побеждает тот, кто первым получит ровно 10. Как вы думаете, может ли первый игрок гарантировать победу? Не называйте пока только ответ — объясните, что должен учитывать игрок." Учитель принимает несколько гипотез и фиксирует их без оценки.
Индивидуально формулируют гипотезу, затем обсуждают её с соседом 30 секунд. Предполагают: «Нужно учитывать оба возможных хода соперника», «Первый игрок может заранее оставить сопернику неудобное количество фишек».
Завершение этапа: учитель подводит итог: "Мы увидели, что одного удачного продолжения недостаточно: соперник может выбрать другой ход. Чтобы проверить стратегию полностью, нам понадобится специальная модель — дерево игры."

Этап 2. Актуализация знаний и выявление затруднения (6 мин)

Цель этапа: актуализировать понятия дерева и алгоритма перебора вариантов, зафиксировать трудность полного доказательства стратегии.
Время
Действие учителя
Действие учеников
2 мин
Учитель показывает схему небольшого дерева: "Посмотрите на доску. Как называются точка, соединяющая два состояния, конечная вершина и самая верхняя вершина схемы? Вспомните, где деревья встречаются в информатике."
Указывают на элементы схемы и отвечают: «Вершина», «ребро», «лист», «корень». Называют применения: «файловая система», «дерево решений», «перебор вариантов».
2 мин
Учитель возвращается к игре: "Перечислите возможные состояния после первого хода и возможные ответы соперника. Почему нельзя рассмотреть только одну последовательность?" Учитель записывает на доске слово «полнота».
В тетради перечисляют состояния и ответы. Объясняют: «У соперника есть несколько вариантов, поэтому нужно проверить каждую ветвь».
2 мин
Учитель предлагает приём «Подумай — обсуди в паре — поделись»: "Сформулируйте, что должно быть в каждой вершине дерева игры. Подумайте самостоятельно, обсудите с партнёром и назовите общий вариант."
Сначала записывают собственную формулировку, затем обсуждают её в паре и предлагают классу: «Текущее состояние, игрок, которому принадлежит ход, и допустимые переходы».
Завершение этапа: учитель подводит итог: "Мы вспомнили структуру дерева и поняли, что дерево игры должно содержать все допустимые продолжения. Теперь определим, как по этому дереву отличать позицию, из которой можно гарантировать победу, от позиции, где победа невозможна."

Этап 3. Постановка проблемы и целеполагание (4 мин)

Цель этапа: вывести правило классификации игровых позиций и совместно сформулировать план решения.

Посмотрите план целиком

Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.

Время
Действие учителя
Действие учеников
2 мин
Учитель показывает два конечных состояния: "Если ход приводит к тому, что соперник уже проиграл и не может сделать разрешённый ход, как назовём исходную позицию? А если из позиции любой ход отдаёт сопернику возможность выиграть?" Учитель подводит к различию «существует» и «для всех».
Формулируют: «Первая позиция выигрышная, потому что существует удачный ход», «Вторая проигрышная, потому что любой ход ведёт к выигрышной позиции соперника».
2 мин
Учитель записывает на доске план: "1. Построить все ходы. 2. Отметить конечные позиции. 3. Двигаться от листьев к корню. 4. Найти первый ход и доказать ответы на каждый ход соперника. Согласны ли вы с таким планом? Что добавим?"
Соглашаются или предлагают дополнение: «Нужно проверить, что не пропущены допустимые ходы». Записывают план решения в тетрадь.
Завершение этапа: учитель подводит итог: "Цель урока сформулирована: научиться строить дерево и доказывать выигрышную стратегию. Переходим к открытию правила анализа позиций снизу вверх."

Этап 4. Открытие нового знания: дерево игры и правило анализа (10 мин)

Цель этапа: сформировать алгоритм анализа дискретной игры двух игроков с полной информацией на конкретном примере.
Время
Действие учителя
Действие учеников
3 мин
Учитель строит на доске дерево для игры с 7 фишками и целью получить ровно 10. Обращается к классу: "Обозначим состояние числом фишек. Из состояния 7 возможны переходы в 8 и 9. Из каждой следующей позиции снова выписываем все разрешённые ходы, пока не получим 10. Лист 10 означает окончание игры. Следите, чтобы каждая ветвь была продолжена до конца."
Перерисовывают в тетрадь часть дерева, подписывают состояния 7, 8, 9 и 10. Проверяют, что из каждой позиции добавляется 1 или 2 фишки.
3 мин
Учитель выделяет конечные позиции: "Рассмотрим позицию, в которой игрок должен ходить, а после любого его хода соперник получает 10. Такая позиция проигрышная. Если же существует ход, после которого соперник оказывается в проигрышной позиции, исходная позиция выигрышная. Запишем это как правило."
Записывают правило: «Позиция выигрышная, если есть ход в проигрышную позицию. Позиция проигрышная, если все ходы ведут в выигрышные позиции». Объясняют разницу между «есть хотя бы один» и «для каждого».
2 мин
Учитель задаёт сократительный вопрос: "Почему анализ начинаем с конца, а не с начальной позиции? Представьте, что мы уже знаем статус всех ближайших состояний. Как определить статус текущего?"
Отвечают: «На конечных позициях результат очевиден; затем статус текущей позиции определяется по статусам её потомков». Формулируют связь с рекурсивным алгоритмом.
2 мин
Учитель предлагает мини-проверку: "Если из позиции есть два хода: один ведёт в проигрышную позицию соперника, другой — в выигрышную, какой статус у текущей позиции? А если оба хода ведут в выигрышные позиции?"
Отвечают: «В первом случае позиция выигрышная, потому что можно выбрать первый ход; во втором — проигрышная».

Запись в тетрадях

Дерево игры — ориентированное дерево, в котором вершины соответствуют игровым позициям, а рёбра — допустимым ходам. Проигрышная позиция: все допустимые ходы ведут в выигрышные позиции соперника. Выигрышная позиция: существует ход в проигрышную позицию соперника. Анализ выполняется от конечных позиций к начальной.
Завершение этапа: учитель подводит итог: "Теперь у нас есть не только схема, но и правило классификации каждой позиции. Проверим его на полном дереве и убедимся, что стратегия должна учитывать любой ответ соперника."

Этап 5. Первичное закрепление в парах (8 мин)

Цель этапа: применить правило анализа к небольшой игре и проговорить доказательство стратегии в паре.
Время
Действие учителя
Действие учеников
1 мин
Учитель раздаёт парам карточки: "Работаем в парах. В игре на столе 5 фишек. За ход можно добавить 1 или 2 фишки. Побеждает тот, кто первым получает ровно 8 фишек. Постройте дерево от 5 до 8. Один участник строит ветви, второй проверяет, что каждый допустимый ход учтён."
Распределяют роли в паре, читают условие и начинают строить дерево состояний 5, 6, 7, 8.
4 мин
Учитель напоминает алгоритм: "Сначала отметьте конечные позиции, затем двигайтесь к корню. Используйте два цвета: одним отметьте выигрышные позиции, другим — проигрышные. После этого запишите первый ход и ответ на каждый возможный ход соперника." Учитель проходит между парами и задаёт вопросы: "Почему эта позиция проигрышная? Все ли ходы вы проверили?"
В парах строят полное дерево, отмечают позиции цветами, объясняют партнёру каждую отметку. Формулируют стратегию и находят возможный первый ход.
3 мин
Учитель организует краткую проверку: "Пара, готовая объяснить решение, представьте его у доски. Не называйте только ответ: покажите ветви и используйте слова «существует» и «для всех». Остальные пары ищут возможный контрпример."
Одна пара представляет дерево. Остальные сверяют схемы, задают вопросы и проверяют, не существует ли ответа соперника, нарушающего стратегию.

Эталон решения

Для игры с 5 фишками и целью получить 8 конечная позиция 8 является выигрышной для игрока, который сделал последний ход. Перед ней позиции 6 и 7 позволяют завершить игру ходом до 8, поэтому они выигрышные для игрока, которому предстоит ход. Из позиции 5 можно перейти в 6 или 7, то есть в каждом случае соперник получает выигрышную позицию. Следовательно, позиция 5 проигрышная для игрока, который начинает с неё. Вывод: гарантированной победы у первого игрока нет; при правильной игре второй игрок использует ответ, дополняющий ход первого до достижения 8.
Завершение этапа: учитель подводит итог: "Вы применили правило к дереву и увидели, что проигрышная позиция определяется не интуицией, а проверкой всех ходов. Теперь каждый самостоятельно решит новую игру и покажет полный ход рассуждений."

Этап 6. Самостоятельная работа с самопроверкой (9 мин)

Цель этапа: проверить индивидуальное умение строить дерево и находить выигрышную стратегию.
Время
Действие учителя
Действие учеников
1 мин
Учитель раздаёт индивидуальные карточки: "Решите задачу самостоятельно. В начале на столе 4 фишки. За ход можно добавить 1 или 2 фишки. Побеждает тот, кто первым получает ровно 7 фишек. Запишите дерево, отметьте типы позиций и укажите, кто выигрывает при правильной игре."
Записывают условие и строят дерево состояний от 4 до 7.
5 мин
Учитель напоминает критерии: "В решении должны быть все допустимые ходы, обозначения конечных позиций и объяснение стратегии. Если вы считаете, что выигрывает второй игрок, объясните, какой ответ он выбирает после каждого хода первого."
Индивидуально анализируют дерево, отмечают выигрышные и проигрышные позиции, записывают стратегию и проверяют её по всем ветвям.
3 мин
Учитель выводит эталон на доску: "Сверьте не только итог, но и логику переходов. Поставьте себе отметку по трём вопросам: дерево полное? позиции определены снизу вверх? стратегия доказана для любого ответа соперника?"
Сравнивают решение с эталоном, отмечают совпадения и ошибки, исправляют пропущенные ветви или неверные обозначения.

Эталон решения

Конечная позиция 7 означает завершение игры. Из позиций 5 и 6 можно сделать ход в 7, поэтому они выигрышные для игрока, которому предстоит ход. Из позиции 4 возможны переходы в 5 и 6, обе позиции выигрышные для следующего игрока. Следовательно, позиция 4 проигрышная для начинающего. При правильной игре выигрывает второй игрок: после хода первого из 4 в 5 второй добавляет 2, а после хода из 4 в 6 второй добавляет 1 и получает 7.
Завершение этапа: учитель подводит итог: "Самостоятельная работа показала, умеете ли вы переходить от схемы к доказательству. Важно не перепутать победу в одной ветви с гарантированной стратегией. Завершим урок проверкой понимания и планом дальнейшей работы."

Этап 7. Рефлексия, оценивание и домашнее задание (5 мин)

Цель этапа: осмыслить способ решения, выявить затруднения и зафиксировать домашнюю исследовательскую задачу.
Время
Действие учителя
Действие учеников
2 мин
Учитель проводит приём «Светофор»: "Покажите цветом уровень понимания: зелёный — могу построить и проанализировать дерево; жёлтый — понимаю правило, но ошибаюсь в ветвях; красный — нужна помощь с различием выигрышной и проигрышной позиции. Одним предложением объясните свой выбор."
Поднимают карточку выбранного цвета и формулируют самооценку: «Мне нужно потренироваться проверять все ходы соперника» или «Я могу доказать стратегию от листьев к корню».
1 мин
Учитель предлагает «Билет на выход»: "Запишите два коротких ответа: что означает выигрышная позиция и почему при доказательстве нужно рассматривать все ходы соперника?"
Записывают ответы на листе и сдают учителю при выходе.
2 мин
Учитель показывает таблицу домашнего задания: "Выберите уровень по своей готовности. Обязательная часть предназначена для всех, повышающая требует полного дерева, дополнительная предлагает описать алгоритм. Перед уходом проверьте, что записали условие и критерии проверки."
Записывают выбранный уровень и контрольные вопросы, уточняют непонятные требования.

Критерии оценивания практической работы

  • «5» — полностью построено дерево игры, учтены все допустимые ходы, корректно определены выигрышные и проигрышные позиции, стратегия доказана для каждого ответа соперника.
  • «4» — дерево и основной вывод верны, но допущена одна неточность в обозначении позиции или недостаточно подробно объяснён один переход; стратегия в целом подтверждена.
  • «3» — построена только часть дерева, верно определены отдельные конечные позиции, но доказательство стратегии неполное или присутствует одна существенная ошибка.
  • «2» — дерево не отражает условие игры, типы позиций определены случайно, стратегия не обоснована.

Рефлексия

Вопрос для ученика
Цель вопроса
Что такое выигрышная позиция и чем она отличается от проигрышной?
Проверка осознания ключевого правила классификации позиций.
Почему дерево игры нужно анализировать от конечных позиций к начальной?
Выявление понимания логики обратного анализа и рекурсивной зависимости.
Какой ход или переход оказался самым трудным при построении дерева?
Выявление точек затруднения в моделировании и учёте всех вариантов.
Можете ли вы доказать стратегию, если соперник выбирает любой допустимый ход?
Проверка перехода от догадки к строгому доказательству полной стратегии.

Завершающее слово учителя

"Сегодня мы представили дискретную игру как дерево состояний и научились анализировать её от конечных позиций к начальной. Главное — отличать существование удачного хода от гарантированной стратегии против любого ответа соперника. Типичная ошибка — рассмотреть только одну ветвь и объявить победу, не проверив остальные. На следующем уроке мы продолжим работу с играми и обсудим, как подобные рассуждения записываются в виде алгоритмов и программ."

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

Уровень
Что задать
Зачем
Базовый (обязательный)
Решить 2 игры по схеме урока: в начальной позиции 3 фишки за ход можно добавить 1 или 2, цель — получить 6; в начальной позиции 6 фишек за ход можно добавить 1 или 2, цель — получить 9. Для каждой игры построить дерево или его полную часть, определить выигрышную позицию и указать стратегию.
Закрепляет построение дерева и применение правила «существует ход» / «все ходы». При проверке смотреть на полноту переходов и объяснение стратегии.
Средний (повышающий)
Решить 3 игры с другими начальными значениями и целью, где за ход разрешено прибавлять 1, 2 или 3. Для каждой игры определить, кто выигрывает при правильной игре, и доказать ответ анализом позиций.
Развивает перенос алгоритма на изменённое множество ходов. При проверке смотреть, учтены ли все три варианта хода и не подменено ли доказательство примером одной партии.
Продвинутый (дополнительный)
Описать псевдокод рекурсивного алгоритма, который получает текущее количество фишек, целевое количество и список разрешённых ходов, а затем определяет, является ли позиция выигрышной. Привести небольшой пример работы алгоритма.
Формирует связь дерева игры с рекурсией, перебором состояний и программной реализацией. При проверке смотреть на базовый случай, перебор ходов и корректное различие условий «существует» и «для всех».
Контрольные вопросы перед выходом из класса: «Что записывают вершины дерева игры?», «Как определить проигрышную позицию по её потомкам?», «Почему стратегия должна учитывать каждый возможный ход соперника?», «Какой этап анализа выполняется первым — начальная позиция или конечные позиции?»

Создайте уникальный план урока по своей теме

  • Любая тема, любой уровень
  • Структура по ФГОС
  • 100% уникальный план урока
  • Цели, ход урока, рефлексия
  • Экспорт в PDF и Word
  • Готово за 1 минуту

Другие темы по информатике для 11 класса

Единственность представления чисел в q-ичных системах счисления. Алфавиты позиционных систем счисленияВизуализация данных и интерпретация результатовАнализ правильности скобочного выраженияДискретные игры двух игроков с полной информацией; Графы. Основные понятия. Виды графов; Построение оптимального пути между вершинами графа; Количество различных путей в ориентированном ациклическомСловари (ассоциативные массивы, отображения). Хэш-таблицыДискретные игры двух игроков с полной информациейСервисы машинного перевода и распознавания устной речи; Идентификация и поиск изображений, распознавание лиц; Самообучающиеся системы; Искусственный интеллект в компьютерных играх и обучающихАдресация в сети Интернет. Система доменных имён; Веб-сайт и веб-страница. Взаимодействие браузера с веб-сервером; Сетевое хранение данныхСетевые протоколы. Сеть Интернет; Веб-сайт и веб-страница. Взаимодействие браузера с веб-сервером; Сетевое хранение данных; Принципы построения и аппаратные компоненты компьютерных сетейБазы данныхКомпьютерные сети и ИнтернетРабота в QGIS

Чем удобны планы уроков Нейрум

  • Готовый план, не набросокЦели, ход урока, планируемые результаты, рефлексия — всё по структуре ФГОС, открыли и пошли вести.
  • План урока или техкартаОдин материал — два формата экспорта в PDF. Скачали то, что нужно завучу.
  • Свой план урока за минутуНе нашли нужный? ИИ-конструктор напишет план урока по вашей теме, классу и типу урока.

Вопросы и ответы

Как скачать план урока «Деревья. Дискретные игры двух игроков с полной информацией»?

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

Соответствует ли план урока ФГОС?

Да, структура урока — цели, ход урока, планируемые результаты — построена по ФГОС для 11 класса (информатике).

Можно ли изменить план под свой класс?

Да. После регистрации план урока открывается в конструкторе: этапы и содержание можно отредактировать или перегенерировать.