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