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