Двоичное кодирование. Условие Фано
Цели и задачи
- Цель по SMART: к концу урока научиться проверять двоичные кодовые наборы на выполнение условия Фано и применять это условие при решении не менее четырёх практических задач разного уровня сложности.
- Сформировать представление о двоичном кодировании как способе представления информации с помощью кодовых слов из символов 0 и 1.
- Научиться сравнивать кодовые слова, находить ситуацию, когда одно слово является началом другого, и формулировать вывод о декодируемости сообщения.
- Развивать умение работать в парах, аргументировать решение, использовать электронные таблицы или интерактивную доску для проверки результатов.
- Показать связь кодирования с информатикой, математикой, передачей данных и профессиональными задачами программиста или инженера.
Планируемые результаты
Личностные
- Проявляют осознанный интерес к способам передачи и хранения информации в цифровой среде.
- Понимают значение точности, однозначности и проверки результата в информационных технологиях.
- Осознают связь изучаемого материала с будущей профессиональной деятельностью в сфере программирования, связи и анализа данных.
- Готовы принимать самостоятельное решение о выборе уровня практического задания и оценивать собственный прогресс.
Метапредметные
- Познавательные: выделяют признак префиксного отношения между кодовыми словами и строят логическое рассуждение.
- Регулятивные: планируют последовательность проверки, контролируют промежуточный результат и исправляют найденную ошибку.
- Коммуникативные: распределяют роли в паре, формулируют доказательство и задают уточняющие вопросы.
- Работают с информацией в текстовой и цифровой форме, представляют результат в таблице и делают вывод.
- Переносят способ проверки на новый набор данных и объясняют применённый алгоритм.
Предметные
- Знать понятия «код», «кодовое слово», «двоичное кодирование», «условие Фано».
- Уметь определять, является ли одно кодовое слово началом другого.
- Уметь проверять набор двоичных кодовых слов на выполнение условия Фано.
- Уметь объяснять, почему выполнение условия Фано обеспечивает однозначность декодирования последовательности.
- Владеть алгоритмом решения практических задач на проверку и построение двоичного кода.
Универсальные учебные действия (УУД)
Личностные УУД
- Осмысливают практическую ценность надёжного кодирования сообщений.
- Связывают точность кодирования с ответственностью разработчика цифровых систем.
- Проявляют готовность к самостоятельному выбору сложности задания.
- Оценивают собственную уверенность в применении алгоритма проверки условия Фано.
Регулятивные УУД
- Формулируют цель проверки кодового набора.
- Планируют сравнение кодовых слов попарно.
- Используют критерий условия Фано для самопроверки.
- Находят и исправляют ошибку в собственном решении.
- Оценивают результат по заданным критериям.
Познавательные УУД
- Сравнивают двоичные строки и выделяют общую начальную часть.
- Классифицируют наборы кодов как удовлетворяющие или не удовлетворяющие условию Фано.
- Моделируют процесс последовательного декодирования сообщения.
- Используют таблицу или электронный инструмент для систематизации проверки.
- Строят доказательное объяснение на основе конкретного контрпримера.
Коммуникативные УУД
- Распределяют роли «проверяющий» и «объясняющий» в парной работе.
- Согласовывают общий алгоритм решения.
- Аргументируют ответ с использованием терминов темы.
- Задают вопросы о спорных кодовых словах.
- Корректно принимают замечания партнёра и уточняют решение.
Подготовка учителя к уроку
- Подготовить презентацию или экранную таблицу с примерами двоичных кодовых слов и двумя неоднозначно декодируемыми сообщениями.
- Распечатать карточки трёх уровней сложности: по одной карточке на каждого ученика и по одному комплекту на пару.
- Подготовить лист самооценки с пунктами «нахожу префикс», «проверяю все пары», «могу объяснить вывод».
- Вывести на доску памятку: «Условие Фано: ни одно кодовое слово не является началом другого».
- Подготовить электронную таблицу или простой скрипт для попарного сравнения кодовых слов; предусмотреть работу без компьютера.
- Подготовить проектор, компьютер учителя, интерактивную доску и таймер.
- Разместить на экране схему: кодовый алфавит {0, 1} → кодовые слова → сообщение.
- Подготовить межпредметный пример передачи команд роботу или датчику с использованием коротких двоичных сигналов.
- Раздать каждой паре два маркера или два листа для записи кодовых слов и общего вывода.
Ход урока
Этап 1. Организационный момент и мотивация (4 мин)
Цель этапа: включить учащихся в практическую проблему надёжной передачи двоичного сообщения и обозначить личную значимость темы.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель приветствует класс и показывает на экране две последовательности: 010 и 01. Реплика: "Представьте, что это команды для робота или пакеты данных, поступающие по каналу связи. Если мы видим последовательность 010, можем ли мы уверенно понять, где заканчивается один код и начинается следующий? Сегодня нам потребуется не угадать ответ, а доказать его." | Рассматривают последовательности, предполагают: "Без правил границы кодовых слов могут быть неясны". |
2 мин | Учитель организует приём «Подумай — обсуди в паре — поделись»: "Сначала 30 секунд подумайте самостоятельно, затем обсудите с соседом, почему одинаковый набор нулей и единиц может передавать разные сообщения. После этого две пары озвучат свои версии." | Индивидуально формулируют гипотезу, затем обсуждают её в паре и сообщают: "Проблема возникает, если одно кодовое слово является началом другого". |
1 мин | Учитель формулирует мотивационный вопрос: "Как заранее проверить код, чтобы сообщение декодировалось однозначно? В конце урока мы вернёмся к этому вопросу и проверим его на практических наборах." | Записывают проблемный вопрос или фиксируют его в листе урока. |
Завершение этапа: учитель подводит итог: "Мы увидели, что короткая двоичная запись сама по себе ещё не гарантирует понятную передачу сообщения. Сначала вспомним, как устроено двоичное кодирование, а затем найдём точное правило проверки."
Этап 2. Актуализация знаний (5 мин)
Цель этапа: актуализировать понятия двоичного алфавита, кодового слова и последовательности кодов.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель показывает на доске обозначение {0, 1} и спрашивает: "Что называют алфавитом кодирования? Чем кодовое слово отличается от всего сообщения? Приведите пример кодового слова длины три." | Отвечают: "Алфавит состоит из 0 и 1; кодовое слово соответствует одному символу; пример — 101". |
2 мин | Учитель раздаёт мини-карточку с вопросами: "Посчитайте длину слов 0, 11, 1011. Составьте сообщение из кодовых слов 10, 0, 111, не добавляя разделителей. Почему после удаления границ может возникнуть трудность?" | Записывают длины 1, 2 и 4, составляют последовательность 100111 и объясняют: "Без известного разбиения нельзя сразу понять границы слов". |
1 мин | Учитель проводит быструю проверку «Светофор»: "Зелёная карточка — уверенно объясняю, жёлтая — нужна подсказка, красная — пока затрудняюсь." | Поднимают карточку самооценки и фиксируют вопрос, если он возник. |
Завершение этапа: учитель подводит итог: "Мы вспомнили, что сообщение строится из кодовых слов, а границы слов должны восстанавливаться однозначно. Теперь специально создадим пример, в котором это правило нарушено, и найдём причину."
Этап 3. Постановка проблемы и целеполагание (4 мин)
Цель этапа: выявить признак неоднозначного кодирования и совместно сформулировать алгоритм проверки.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель записывает набор кодов: A — 0, Б — 01, В — 11. Реплика: "Рассмотрим последовательность 01. Как её можно прочитать? Какие два кодовых слова конфликтуют? Не называйте только ответ — укажите, какое слово начинается с другого." | Находят слова 0 и 01, формулируют: "0 является началом слова 01, поэтому граница сообщения неоднозначна". |
2 мин | Учитель задаёт цепочку вопросов в формате «Сократовского диалога»: "Достаточно ли сравнить длины? Что именно нужно сравнивать? Какой вывод можно сделать, если ни одно слово не начинается с другого?" На доске фиксирует цель: научиться проверять условие Фано и обосновывать результат. | Отвечают: "Нужно сравнивать начало строк; если ни одно слово не является началом другого, декодирование однозначно". Записывают цель урока. |
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Завершение этапа: учитель подводит итог: "Проблема стала точной: нам нужно не просто смотреть на кодовые слова, а проверять каждую возможную пару. Сейчас выведем правило и сразу применим его на небольших наборах."
Этап 4. Открытие нового знания и алгоритма (9 мин)
Цель этапа: сформулировать условие Фано и освоить пошаговую процедуру проверки двоичного кода через работу в парах и ИКТ.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель показывает на экране три набора: {0, 10, 110}, {01, 10, 11}, {1, 10, 100}. Реплика: "Сравнивайте слова не по числовому значению, а по расположению символов. Если короткое слово полностью совпадает с началом длинного, это нарушение. Запишите формулировку: код удовлетворяет условию Фано, если ни одно кодовое слово не является началом другого." | В тетрадях записывают определение, подчёркивают слова «началом другого», обсуждают примеры. |
3 мин | Учитель демонстрирует алгоритм на наборе {0, 10, 110}: "Шаг первый — выпишем слова. Шаг второй — сравним каждое слово с более длинными. Шаг третий — проверим совпадение начальных символов. Здесь 0 не является началом 10 и 110, 10 не является началом 110. Значит, условие выполняется." | Следят по таблице, называют проверяемые пары: "0 и 10; 0 и 110; 10 и 110". Формулируют вывод: "Нарушений нет". |
3 мин | Учитель включает электронную таблицу с колонками «короткое слово», «длинное слово», «начало длинного слова», «результат». Реплика: "В парах внесите слова из набора {1, 10, 100}. В последней колонке поставьте «нарушение» только тогда, когда короткое слово совпадает с началом длинного. Если компьютера нет, выполните ту же таблицу на бумаге." | В парах распределяют роли, вносят три слова и обнаруживают пары 1–10 и 1–100. Делают вывод: "Условие Фано не выполняется". |
Запись в тетрадях
Условие Фано: в наборе кодовых слов ни одно слово не является началом другого. Алгоритм проверки: 1) выписать кодовые слова; 2) сравнивать каждое слово с более длинными; 3) проверить совпадение начальных символов; 4) сделать вывод о выполнении условия.
Завершение этапа: учитель подводит итог: "Мы получили правило и проверили его цифровым и бумажным способом. Теперь каждая пара применит алгоритм к собственному набору, а результат будет подтверждён конкретной парой слов или полным отсутствием таких пар."
Этап 5. Первичное закрепление в парах (8 мин)
Цель этапа: закрепить алгоритм проверки условия Фано на заданиях базового и повышенного уровня.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель раздаёт карточки базового уровня: "Проверьте наборы A = {0, 11, 101} и B = {01, 10, 001}. Для каждого набора запишите хотя бы две проверенные пары и итоговый вывод." | В парах сравнивают слова, записывают пары и выводы. Для A формулируют: "Условие выполняется"; для B находят: "01 является началом 001, условие не выполняется". |
3 мин | Учитель предлагает задание среднего уровня: "Для набора C = {00, 01, 10, 11} объясните, выполняется ли условие Фано. Затем придумайте ещё одно кодовое слово, которое можно добавить без нарушения условия." | Проверяют все слова одинаковой длины, делают вывод: "Условие выполняется". Предлагают, например, слово 000, и обнаруживают, что оно нарушит условие, либо объясняют невозможность добавить слово длины более двух без конфликта с выбранным полным набором. |
3 мин | Учитель предлагает желающим повышенное задание: "Найдите ошибку в рассуждении: ‘В наборе {0, 10, 110} условие Фано нарушено, потому что 0 меньше 10’. Объясните, почему числовое сравнение здесь не подходит." Учитель организует взаимопроверку по схеме «Две звезды и пожелание». | Исправляют рассуждение: "Сравнивать нужно не числовые значения, а совпадение начальной части". Пишут партнёру две сильные стороны решения и один совет. |
Эталон решения
Для набора $B = \{01, 10, 001\}$ сравниваем более короткие слова с более длинными. Слово 01 является началом слова 001, поскольку первые два символа 001 образуют 00, а не 01; следовательно, эта пара конфликта не создаёт. Слово 10 не является началом 001. Других более длинных слов нет, поэтому условие Фано выполняется.
Завершение этапа: учитель подводит итог: "Вы увидели, что даже похожие слова не обязательно создают конфликт. Важна точная проверка символ за символом. Перейдём к индивидуальной работе: теперь каждый покажет, умеет ли самостоятельно выбрать алгоритм и обосновать ответ."
Этап 6. Самостоятельная практическая работа с самопроверкой (9 мин)
Цель этапа: индивидуально проверить сформированность умения применять условие Фано и дифференцировать задания по сложности.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель объясняет выбор: "Выполните обязательное задание базового уровня. Если закончите раньше и уверены в ответе, переходите к среднему или продвинутому уровню. Записывайте не только ‘да’ или ‘нет’, но и пару слов, подтверждающую вывод." | Выбирают карточку или уровень, записывают алгоритм проверки. |
4 мин | Учитель раздаёт варианты. Базовый: проверить {0, 11, 101, 110}. Средний: проверить {00, 01, 10, 100} и указать все конфликтующие пары. Продвинутый: построить набор из четырёх двоичных слов, удовлетворяющий условию Фано, включая слово 0 или 1, и доказать результат. | Индивидуально решают задания. В базовом варианте сравнивают пары; в среднем находят 00–100; в продвинутом подбирают слова, не начинающиеся с выбранного короткого слова. |
2 мин | Учитель выводит на экран эталон: "Сначала проверьте наличие короткого слова, затем сравните его с каждым более длинным. Не забывайте: совпадение первых символов должно продолжаться на всей длине короткого слова." | Сверяют решение с эталоном, отмечают исправления другим цветом. |
2 мин | Учитель просит заполнить лист самооценки: "Поставьте плюс напротив действия, которое выполняете без подсказки, и запишите одну причину возможной ошибки." | Заполняют лист: «нахожу префикс», «сравниваю все нужные пары», «обосновываю вывод». |
Эталон решения
Для набора $\{0, 11, 101, 110\}$ слово 0 не является началом ни 11, ни 101, ни 110, поскольку все эти слова начинаются с 1. Слово 11 не является началом 101, а слово 101 не является началом 110. Следовательно, условие Фано выполняется.
Завершение этапа: учитель подводит итог: "Индивидуальная проверка показала, что алгоритм можно применять к наборам разного размера. Осталось обобщить, зачем это правило нужно при декодировании сообщений и где подобные идеи встречаются за пределами сегодняшнего примера."
Этап 7. Межпредметное применение и рефлексия (6 мин)
Цель этапа: связать условие Фано с передачей данных, математической логикой и алгоритмами, а также осмыслить результат урока.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель показывает схему передачи команды от датчика к устройству: "В математике мы сравниваем строки по признаку начального фрагмента, а в программировании такой признак позволяет быстро обнаружить неоднозначный код. Представьте, что датчик передаёт команды 0, 10 и 11. Почему такой набор удобен для восстановления команд?" | Отвечают: "Ни одно слово не является началом другого, поэтому границы можно восстановить однозначно". |
2 мин | Учитель возвращается к мотивационному вопросу и проводит приём «Одноминутка»: "За одну минуту запишите правило проверки своими словами и приведите один набор, который ему удовлетворяет." | Записывают определение и пример, например {0, 10, 11}, затем обмениваются листами с соседом для быстрой проверки. |
2 мин | Учитель задаёт вопросы рефлексии: "Что оказалось самым важным шагом? Где можно ошибиться? Какой уровень задания вы готовы решить самостоятельно на следующем уроке?" Затем сообщает домашнее задание. | Формулируют ответы: "Нужно сравнивать начало слов"; называют типичную ошибку «сравнение числовых значений вместо строк» и выбирают уровень домашней работы. |
Завершение этапа: учитель подводит итог: "Сегодня мы превратили проблему неоднозначного сообщения в чёткий алгоритм сравнения кодовых слов. Условие Фано помогает заранее проверить, можно ли восстановить границы кодов без разделителей. На следующем уроке мы продолжим исследовать эффективность кодирования и сравним коды разной длины."
Критерии оценивания практической работы
- «5» — правильно решены обязательное и выбранное дополнительное задание, проверены необходимые пары кодовых слов, выводы обоснованы термином «начало кодового слова», существенных ошибок нет.
- «4» — правильно решено обязательное задание и большинство дополнительных проверок, но допущена одна неточность в записи пары или объяснении, не повлиявшая на общий вывод.
- «3» — правильно определён результат хотя бы для одного набора, но проверка выполнена не полностью или вывод приведён без достаточного обоснования.
- Ниже базового уровня — не проведено сравнение кодовых слов или перепутано числовое сравнение с проверкой начальной части строки.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Как своими словами сформулировать условие Фано? | Проверка осознания ключевого определения урока. |
Какую пару кодовых слов вы проверяли особенно внимательно и почему? | Выявление понимания механизма поиска конфликта. |
Какая ошибка наиболее вероятна при проверке двоичного кода? | Диагностика типичных затруднений и неверных стратегий. |
Какое задание вы готовы решить самостоятельно на следующем уроке? | Субъективная оценка уровня освоения и готовности к усложнению. |
Завершающее слово учителя
"Сегодня мы увидели, что надёжность двоичного кода определяется не количеством нулей и единиц, а отношением между кодовыми словами. Главное правило — ни одно слово не должно быть началом другого. Типичная ошибка заключается в сравнении слов как чисел, хотя нужно сравнивать их символы слева направо. На следующем уроке мы рассмотрим, как выбирать код с учётом длины сообщений и эффективности передачи данных."
Домашнее задание
Уровень | Что задать | Зачем |
|---|---|---|
Базовый (обязательный) | Проверить условие Фано для четырёх наборов по 4–5 двоичных кодовых слов; для каждого набора указать одну подтверждающую пару или написать, что конфликтующих пар нет. | Закрепляет алгоритм попарного сравнения; при проверке обратить внимание на полноту и точность вывода. |
Средний (повышающий) | Решить 3 задачи: найти все конфликтующие пары в заданном наборе, исправить один набор удалением минимального числа слов и построить набор из пяти кодовых слов, удовлетворяющий условию Фано. | Развивает анализ, коррекцию решения и применение правила при проектировании кода. |
Продвинутый (дополнительный) | Написать краткое объяснение на 8–10 предложений о том, почему условие Фано важно при передаче команд устройству, и привести собственный пример двоичного кода с доказательством его корректности. | Формирует межпредметную связь с программированием и инженерными системами, развивает аргументацию. |
Контрольные вопросы перед выходом: «Что называется кодовым словом? Как проверить, является ли одно слово началом другого? Какой вывод делается при обнаружении хотя бы одной такой пары? Почему сравнение числовых значений 0 и 10 не заменяет сравнение строк?»
