Структура информации: списки, графы, деревья и построение дерева решений
Цели и задачи
- Цель урока по SMART: за 45 минут научиться выбирать подходящую структуру данных для описания задачи и построить дерево решений по заданному алгоритму, проверив его работу минимум на трёх примерах.
- Сформировать умение различать списки, графы и деревья по числу связей, наличию циклов и характеру отношений между объектами.
- Освоить алгоритм построения дерева решений: выделить признаки, определить варианты ответов, выбрать порядок вопросов, записать листья-решения и проверить дерево на тестовых случаях.
- Развивать алгоритмическое и критическое мышление через практическое моделирование и поиск ошибок в готовой схеме.
- Формировать ответственное отношение к точности цифровых моделей и сотрудничеству при решении практической задачи.
Планируемые результаты
Личностные
- Ученик осознаёт практическую ценность структур данных для программирования, анализа информации и будущей профессиональной деятельности.
- Проявляет готовность проверять корректность цифровой модели, а не принимать результат без доказательства.
- Осознаёт значение точности формулировок вопросов и критериев при принятии решений.
- Принимает ответственность за собственный вклад в групповую работу и итоговое решение.
Метапредметные
- Умеет выделять объекты, свойства и связи в условии практической задачи.
- Планирует последовательность построения модели и проверяет её на тестовых данных.
- Использует цифровые инструменты для создания схемы, совместного редактирования и представления результата.
- Аргументирует выбор структуры данных и оценивает эффективность предложенного дерева решений.
- Смыслово читает условие, преобразует текстовую информацию в графическую модель и формулирует вывод.
Предметные
- Знать признаки списка, графа и дерева как способов представления структурированной информации.
- Уметь определять вершины, рёбра, корень, ветви, листья и путь в дереве.
- Уметь строить дерево решений по заданным признакам и вариантам ответов.
- Уметь проверять дерево решений на конкретных наборах исходных данных и находить неоднозначные или лишние ветви.
- Владеть навыком представления дерева решений в графическом редакторе или среде построения схем.
Универсальные учебные действия (УУД)
Личностные УУД
- Определяют личный интерес к применению структур данных в программировании, аналитике или искусственном интеллекте.
- Оценивают собственную готовность самостоятельно проверять алгоритмические решения.
- Осознают необходимость корректного и понятного представления информации для другого пользователя.
- Проявляют инициативу при выборе способа визуализации дерева решений.
Регулятивные УУД
- Формулируют цель практической работы и критерии готового результата.
- Планируют построение дерева от общей характеристики к частным решениям.
- Осуществляют пошаговый самоконтроль по чек-листу.
- Сравнивают результат с условием, обнаруживают ошибки и вносят коррективы.
- Оценивают качество модели по полноте, однозначности и удобству использования.
Познавательные УУД
- Выделяют существенные признаки объектов и классифицируют их по типу структуры.
- Сравнивают список, граф и дерево по заданным свойствам.
- Строят модель информационной задачи в виде иерархической схемы.
- Анализируют пути от корня дерева к листьям и выявляют противоречия.
- Работают с текстовой, графической и табличной информацией в цифровой среде.
Коммуникативные УУД
- Распределяют роли в группе: аналитик, проектировщик, проверяющий и докладчик.
- Формулируют вопросы к условию и аргументируют выбор признаков.
- Согласуют варианты построения дерева и корректно объясняют найденные ошибки.
- Представляют цифровую модель классу в течение установленного времени.
Подготовка учителя к уроку
- Подготовить компьютеры или ноутбуки по одному на пару, проверить доступ к графическому редактору, редактору схем или презентаций.
- Создать общую папку или доску для сдачи файлов и назвать заготовки по группам.
- Распечатать карточки с тремя практическими ситуациями — по одной на группу.
- Распечатать чек-лист проверки дерева решений — по одному на каждого ученика.
- Подготовить на экране краткую памятку: «объекты → признаки → вопросы → ветви → листья → проверка».
- Подготовить таблицу сравнения списка, графа и дерева с незаполненными ячейками.
- Подготовить три тестовых набора данных для проверки готовых деревьев.
- Организовать на доске область для фиксации критериев: полнота, однозначность, отсутствие лишних вопросов, проверяемость.
- Подготовить таймер и проектор или интерактивную доску для демонстрации цифровых схем.
Ход урока
Этап 1. Организационный момент и постановка практической задачи (3 мин)
Цель этапа: включить учеников в практическую деятельность и показать, что структура данных помогает принимать решения по формальному алгоритму.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель приветствует класс и проверяет готовность компьютеров: «Здравствуйте, ребята. Сегодня мы не будем долго пересказывать определения. Наша задача — превратить реальную ситуацию в цифровую модель, которую сможет использовать другой человек. Проверьте, что компьютер включён, файл для схемы открывается, а в тетради есть место для алгоритма работы». | Проверяют компьютер, открывают редактор схем или презентаций, записывают дату и тему урока. |
2 мин | Учитель показывает на экране пример онлайн-рекомендации: «Представьте сервис, который советует фильм, маршрут или способ решения задачи. Он задаёт вопросы и по ответам приходит к результату. Как представить такую последовательность вопросов, чтобы она была понятна и проверяема? Сегодня мы построим дерево решений». | Формулируют предположения: «Нужно записать вопросы и варианты ответов», «Нужна схема с ветвями», «Каждый путь должен приводить к одному решению». |
Завершение этапа: учитель подводит итог: «Мы определили практическую проблему: нужно представить последовательность выбора так, чтобы не потерять варианты и не получить противоречивый результат. Сначала вспомним, какие структуры информации уже умеем распознавать».
Этап 2. Актуализация знаний: список, граф и дерево (5 мин)
Цель этапа: актуализировать признаки основных структур и подготовить критерии выбора модели.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель выводит на экран три схемы: последовательность покупок, сеть дорог между городами и иерархию папок. «Рассмотрите схемы молча в течение тридцати секунд. Подумайте, что в каждой из них является объектами, а что — связями. Затем обсудите вывод с соседом по парте». | Индивидуально рассматривают схемы, затем в парах называют объекты и связи: «товары и порядок в списке», «города и дороги», «папки и вложенность». |
3 мин | Учитель заполняет на доске таблицу и задаёт вопросы: «Какая структура задаёт порядок элементов? Где возможны циклы? Какая структура имеет корень и не содержит замкнутых путей? Почему сеть дорог обычно нельзя назвать деревом?» | Заполняют таблицу в тетради, отвечают: «Список задаёт порядок», «В графе возможны циклы», «У дерева есть корень и единственный путь от корня к вершине», «В сети между городами могут быть замкнутые маршруты». |
Запись в тетрадях
Список — упорядоченная последовательность элементов. Граф — множество вершин и соединяющих их рёбер. Дерево — связный граф без циклов, в котором выделена корневая вершина; от корня к каждой вершине ведёт единственный путь.
Завершение этапа: учитель подводит итог: «Теперь мы умеем отличать структуру, задающую порядок, структуру произвольных связей и иерархическую структуру без циклов. Для дерева решений особенно важны корень, ветви и листья. Перейдём к алгоритму его построения».
Этап 3. Инструктаж по алгоритму построения дерева решений (6 мин)
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Цель этапа: сформировать пошаговый алгоритм построения дерева решений и критерии проверки результата.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель показывает памятку: «Запишите алгоритм. Шаг 1 — определить, какое решение должно выдаваться. Шаг 2 — перечислить объекты и признаки. Шаг 3 — выбрать первый вопрос, который лучше всего разделяет варианты. Шаг 4 — добавить ветви ответов. Шаг 5 — повторять вопросы до получения однозначных листьев. Шаг 6 — проверить каждый путь на тестовом примере». | Записывают шесть шагов алгоритма, подчёркивают слова «признак», «ветвь», «лист», «проверка». |
3 мин | Учитель демонстрирует мини-пример на доске: «Нужно решить, брать ли зонт. Первый вопрос: есть ли осадки? Если нет — зонт не нужен. Если да — второй вопрос: сильный ли дождь? При положительном ответе берём зонт, при отрицательном решение зависит от выбора пользователя. Почему нельзя оставить ветвь без листа?» | Объясняют: «Каждая ветвь должна завершаться решением», «Иначе алгоритм не выдаёт результата». Предлагают уточнить вопрос или добавить конечное решение. |
Запись в тетрадях
Алгоритм построения дерева решений: 1) определить множество решений; 2) выделить признаки; 3) выбрать корневой вопрос; 4) построить ветви ответов; 5) довести каждый путь до листа; 6) проверить дерево на тестовых данных.
Завершение этапа: учитель подводит итог: «Хорошее дерево не просто красиво выглядит. Оно задаёт однозначный путь от исходных данных к решению, содержит все необходимые варианты и не задаёт лишних вопросов. Сейчас каждая группа проверит этот алгоритм на собственной задаче».
Этап 4. Практикум в группах: проектирование дерева решений (12 мин)
Цель этапа: построить цифровое дерево решений по жизненной ситуации, распределив роли и применив полный алгоритм.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель делит класс на группы по четыре человека и раздаёт карточки. «В каждой группе назначьте аналитика, проектировщика, проверяющего и докладчика. Аналитик выписывает признаки, проектировщик создаёт схему, проверяющий ищет пропуски и противоречия, докладчик готовит объяснение. Выберите одну ситуацию: рекомендация способа добраться до школы, выбор формата хранения файла или определение подходящего варианта учебного курса». | Распределяют роли, выбирают карточку и выписывают объект решения, возможные признаки и конечные варианты. |
3 мин | Учитель напоминает: «Не начинайте сразу с рисования. Сначала составьте список признаков и решите, какой вопрос сильнее всего разделит варианты. Например, для маршрута важны расстояние, погода, наличие транспорта и время. Не включайте признак, который не влияет на решение». | Составляют перечень признаков, исключают несущественные, выбирают корневой вопрос и объясняют его группе. |
5 мин | Учитель консультирует группы: «Проверьте, что у каждого ответа есть продолжение. Если вопрос допускает больше двух вариантов, покажите их отдельными ветвями или сформулируйте вопрос точнее. Не оставляйте слова “другое” без пояснения, какое решение принимает алгоритм». | Создают дерево в цифровом редакторе, подписывают корень, ветви и листья, добавляют все существенные варианты. |
2 мин | Учитель запускает таймер и предлагает контроль: «Проведите по дереву минимум три тестовых объекта. Запишите ответы на вопросы и конечное решение. Если два одинаковых объекта приводят к разным листьям, найдите ошибку в формулировке признака». | Проверяющий прогоняет три тестовых случая, фиксирует пути и исправляет неполные или противоречивые ветви. |
Эталон проверки дерева решений
Для каждого тестового объекта: 1) выписать исходные признаки; 2) ответить на вопрос в корне; 3) перейти по соответствующей ветви; 4) повторять переходы до листа; 5) сравнить полученное решение с ожидаемым. Если путь обрывается, вопрос сформулирован неоднозначно или один объект попадает в разные листья, дерево необходимо исправить.
Завершение этапа: учитель подводит итог: «Группы уже создали рабочие модели и проверили их на примерах. Теперь каждая команда кратко покажет результат, а остальные оценят не оформление, а логику: полноту, однозначность и обоснованность признаков».
Этап 5. Представление и взаимная проверка цифровых моделей (7 мин)
Цель этапа: научить представлять модель, задавать уточняющие вопросы и оценивать дерево решений по критериям.
Время | Действие учителя | Действие учеников |
|---|---|---|
4 мин | Учитель приглашает две группы к демонстрации: «У вас есть две минуты на представление. Назовите задачу, объясните выбор корневого вопроса и проведите по дереву один тестовый пример. Остальные группы отмечают в чек-листе, есть ли у дерева корень, подписанные ветви, конечные решения и проверяемые пути». | Докладчики демонстрируют схемы, проводят тестовые случаи и объясняют выбор первого вопроса. Остальные заполняют чек-лист и записывают по одному сильному месту и одному вопросу. |
3 мин | Учитель организует приём «Две звезды и пожелание»: «Назовите две сильные стороны чужой модели и одно конкретное улучшение. Говорите о структуре: например, “полностью учтены варианты”, “короткие пути”, “нужно разделить неоднозначную ветвь”». | Формулируют обратную связь: «Две сильные стороны — понятный корень и проверка примерами. Пожелание — уточнить ветвь “другое”». |
Завершение этапа: учитель подводит итог: «Мы увидели, что одна и та же задача может иметь несколько деревьев. Лучшим будет не самое большое дерево, а то, которое даёт правильный результат, не содержит лишних вопросов и понятно пользователю. Теперь каждый индивидуально проверит понимание алгоритма».
Этап 6. Индивидуальная практическая работа с самопроверкой (8 мин)
Цель этапа: проверить индивидуальное умение выбрать структуру и построить фрагмент дерева решений.
Время | Действие учителя | Действие учеников |
|---|---|---|
5 мин | Учитель раздаёт карточки трёх уровней: «Выберите уровень, который позволит показать ваши реальные возможности. Минимум: определить структуру для трёх описаний. Базовый: построить дерево для выбора способа хранения файла по признакам “размер”, “нужен совместный доступ”, “требуется резервная копия”. Повышенный: найти лишний вопрос в готовом дереве и перестроить его». | Выполняют выбранное задание индивидуально. Для базового варианта строят дерево с решениями «локальное хранение», «облачное хранение» или «резервная копия» и подписывают пути. |
3 мин | Учитель показывает эталон-критерии: «Проверьте себя: структура соответствует задаче; все вершины подписаны; каждая ветвь имеет ответ; каждый путь заканчивается решением; на тестовом примере результат однозначен. Исправьте одну найденную ошибку другим цветом». | Сверяют работу с чек-листом, проводят один тестовый путь, отмечают исправления и сдают файл или фотографию схемы в общую папку. |
Завершение этапа: учитель подводит итог: «Индивидуальная работа показала, что построение дерева — это последовательность проверяемых действий, а не рисование произвольной схемы. Осталось зафиксировать, что получилось, где возникло затруднение и как этот навык связан с дальнейшим изучением алгоритмов».
Этап 7. Рефлексия и домашнее задание (4 мин)
Цель этапа: осмыслить освоенный алгоритм, выявить затруднения и определить направление дальнейшей работы.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель предлагает «Билет на выход»: «Запишите три коротких ответа: чем дерево отличается от произвольного графа; какой вопрос является корневым; как проверить, что дерево решений работает корректно». Затем отметьте цветом: зелёный — могу построить сам, жёлтый — нужна проверка, красный — требуется объяснение». | Пишут ответы на билетах, выбирают цвет самооценки и передают лист учителю. |
2 мин | Учитель объявляет домашнее задание: «Выберите один бытовой или учебный процесс, который можно представить деревом решений. Опишите признаки, постройте дерево в цифровом редакторе и проверьте его минимум на трёх примерах. Для желающих добавьте оценку: какой вопрос можно переставить ближе к корню и почему». | Записывают задание, задают уточняющие вопросы, называют возможные темы: выбор маршрута, подбор тарифа, диагностика неисправности, выбор способа подготовки к контрольной. |
Критерии оценивания практической работы
- «5» — корректно выбрана структура, построено полное дерево решений, все ветви подписаны, каждый путь заканчивается однозначным решением, проведены минимум три проверки, цифровая схема читаема и объяснена.
- «4» — дерево в целом корректно, но допущена одна неточность в подписи ветви, порядке вопросов или проверке; основная логика решения сохранена.
- «3» — выделены основные признаки и создано неполное дерево, однако пропущена ветвь, отсутствует часть проверки или конечное решение сформулировано неоднозначно.
- Ниже базового уровня — структура выбрана без обоснования, дерево не позволяет пройти путь от корня к однозначному решению или работа не проверена на тестовом примере.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Как по одному признаку отличить дерево от произвольного графа? | Проверка понимания отсутствия циклов и наличия иерархической структуры. |
Какой шаг алгоритма построения дерева оказался самым сложным? | Выявление точек затруднения: выделение признаков, выбор корня или проверка. |
Как вы проверяли, что каждый объект получает однозначное решение? | Оценка сформированности навыка тестирования алгоритма. |
Где в будущей учёбе или профессии может пригодиться дерево решений? | Осмысление практической ценности темы и связь с профессиональной мотивацией. |
Завершающее слово учителя
«Сегодня вы убедились, что структура информации определяет способ решения задачи. Список помогает хранить порядок, граф — описывать произвольные связи, а дерево — представлять иерархию и последовательность выбора. Самая частая ошибка при построении дерева — оставить ветвь без конечного решения или задать вопрос, который не разделяет варианты. На следующем уроке мы продолжим работать с алгоритмами и рассмотрим, как оценивать эффективность разных способов представления информации».
Домашнее задание
Уровень | Что задать | Зачем |
|---|---|---|
Базовый (обязательный) | Составить в тетради сравнение списка, графа и дерева по четырём признакам: порядок элементов, наличие циклов, корневая вершина, тип связей. Привести по одному примеру применения каждой структуры. | Закрепляет распознавание структур; при проверке обратить внимание на точность признаков и соответствие примеров. |
Средний (повышающий) | Построить цифровое дерево решений для бытовой или учебной задачи с не менее чем четырьмя признаками, минимум шестью листьями и тремя тестовыми примерами. К каждому тесту записать путь от корня к решению. | Закрепляет полный алгоритм построения и навык пошагового тестирования; проверить отсутствие обрывающихся ветвей и неоднозначных листьев. |
Продвинутый (дополнительный) | Создать два дерева для одной задачи, изменив корневой вопрос. Сравнить их по числу вопросов в трёх тестовых путях и обосновать, какое дерево удобнее пользователю. | Развивает анализ и оценку алгоритмических моделей; при проверке учитывать аргументированность выбора и корректность сравнения. |
Контрольные вопросы перед выходом: «Какую структуру называют деревом? Что находится в корне дерева решений? Почему каждый путь должен завершаться листом? Какими тестовыми примерами вы проверите корректность собственной модели?»