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

Графы и деревья

Подтемы: Дискретные игры двух игроков с полной информацией, Графы. Основные понятия. Виды графов, Построение оптимального пути между вершинами графа, Количество различных путей в ориентированном ациклическом графе, Деревья. Бинарное дерево, Дерево перебора вариантов. Описание стратегии игры в табличной форме, Выигрышные стратегии

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

Информатика · 11 класс · Открытие нового · 45 мин · Подтемы: Дискретные игры двух игроков с полной информацией, Графы. Основные понятия. Виды графов, Построение оптимального пути между вершинами графа, Количество различных путей в ориентированном ациклическом графе, Деревья. Бинарное дерево, Дерево перебора вариантов. Описание стратегии игры в табличной форме, Выигрышные стратегии

Дискретные игры, графы и выигрышные стратегии

Цели и задачи

  • Цель урока по 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.

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

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

Этап 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 мин. Учитель уточняет правила маркировки и просит не ограничиваться одним примером: «Для каждой позиции запишите допустимые ходы и статус результата. Затем сформулируйте стратегию первого игрока в виде таблицы: текущая позиция, ход, ожидаемая позиция». Ученики заполняют таблицу, обсуждают спорные позиции и формулируют стратегию: «Нужно оставлять сопернику проигрышную позицию; ход выбирается по таблице, а не угадывается».

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

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

Этап 6. Межпредметная групповая практика (10 мин)

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

Этап 7. Самостоятельная работа, рефлексия и домашнее задание (5 мин)

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

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

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

Рефлексия

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

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

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

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

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

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

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

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

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

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

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

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

Как скачать план урока «Дискретные игры двух игроков с полной информацией; Графы. Основные понятия. Виды графов; Построение оптимального пути между вершинами графа; Количество различных путей в ориентированном ациклическом»?

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

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

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

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

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