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