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

Бинарное дерево и выигрышные стратегии в дискретных играх

Информатика10 класс63 раздела
Бинарное дерево и выигрышные стратегии в дискретных играх

Информатика · 10 класс · Открытие нового · 45 мин

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

Цели и задачи

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

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

Личностные

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

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

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

Предметные

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

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

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

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

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

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

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

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

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

  • Распределяют роли в паре и согласовывают обозначения позиций и ходов.
  • Формулируют вопрос сопернику так, чтобы проверить устойчивость его стратегии.
  • Объясняют, почему стратегия гарантирует победу независимо от ответа соперника.
  • Корректно принимают замечания и уточняют доказательство.

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

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

Ход урока

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

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

Этап 2. Актуализация знаний (5 мин)

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

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

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

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

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

Завершение этапа: учитель подводит итог: "Цель определена: от игровой ситуации мы должны прийти к доказанной стратегии. Начнём с построения модели, где каждый ход будет виден как отдельная ветвь."

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

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

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

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

Этап 5. Первичное закрепление: анализ дерева и таблицы стратегии (8 мин)

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

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

Позиция 0 проигрышная. Позиции 1 и 2 выигрышные, поскольку игрок сразу забирает последний камень. Позиция 3 проигрышная: из неё можно перейти в 2 или 1, а обе позиции выигрышны для соперника. Позиции 4 и 5 выигрышные, так как из 4 можно оставить 3, а из 5 — также оставить 3. Позиция 6 проигрышная: оба хода ведут в 5 или 4. Позиция 7 выигрышная: первый игрок берёт один камень и оставляет 6. После этого на каждый ход соперника из двух камней первый игрок отвечает так, чтобы суммарно за два хода было взято три камня: если соперник взял один, взять два; если соперник взял два, взять один.
Завершение этапа: учитель подводит итог: "Таблица дала тот же результат, что и дерево, но позволила компактно описать позиции и ответные ходы. Теперь каждый самостоятельно проверит, умеет ли он построить часть дерева и записать стратегию без подсказки пары."

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

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

Этап 7. Включение в систему знаний и рефлексия (7 мин)

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

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

  • «5» — без ошибок построено дерево или заполнена таблица для позиций 0–8, правильно отмечены выигрышные и проигрышные позиции, приведено полное доказательство стратегии для семи или восьми камней.
  • «4» — правильно определено не менее 7 из 9 статусов и указана выигрышная стратегия, но допущена одна неточность в объяснении ветви или ответного хода.
  • «3» — правильно определено не менее 5 из 9 статусов, построена основная часть дерева и сформулирована идея выигрышной позиции, однако доказательство стратегии неполное.
  • Ниже базового уровня — отсутствует полный перебор вариантов или перепутаны определения выигрышной и проигрышной позиции; требуется повторная работа с фрагментом дерева от 0 до 3.

Рефлексия

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

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

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

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

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

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

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

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

Представление целых и вещественных чисел в памяти компьютераЛогический квест «Логические основы компьютера»Блоки питанияТроичная уравновешенная система счисленияОсновные устройства компьютераСистемы, компоненты систем и их взаимодействиеТекстовый процессор. Редактирование и форматирование; Проверка орфографии и грамматики. Средства поиска и автозамены; Использование стилей. Структурированные документы. Сноски, оглавление; ОблачныеСоздание таблиц в текстовом редактореФайловая система компьютераПринципы работы компьютера. Персональный компьютер; Виды программного обеспечения и их назначение; Выбор конфигурации компьютера в зависимости от решаемых задачДвоичная, восьмеричная и шестнадцатеричная системы и переводы между ними; Арифметические операции в позиционных системах счисленияАлфавитный подход к оценке количества информации

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

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

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

Как скачать план урока «Бинарное дерево и выигрышные стратегии в дискретных играх»?

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

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

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

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

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