Кодирование информации и объём информационных сообщений: алгоритмы решения задач ЕГЭ №4 и №7
Цели и задачи
- Цель: сформировать умение решать задания ЕГЭ №4 на кодирование информации и №7 на вычисление объёма информационных сообщений.
- Образовательная задача: повторить равномерное и неравномерное кодирование, длину кодового слова, количество символов и объём сообщения.
- Развивающая задача: развить логическое мышление и навыки пошагового анализа условий задач.
- Воспитательная задача: сформировать внимательный и последовательный подход к решению экзаменационных задач.
- Профориентационная задача: показать связь кодирования и теории информации с работой программиста и разработчика алгоритмов.
Планируемые результаты
Личностные
- Готовность к осознанному выбору дальнейшей образовательной траектории в сфере IT.
- Умение управлять своим временем и эмоциональным состоянием в условиях подготовки к ЕГЭ.
- Критическое отношение к информации в цифровой среде.
Метапредметные
- Умение структурировать знания и представлять их в виде алгоритмов.
- Навык поиска и выделения необходимой информации из условия задачи.
- Способность выбирать наиболее эффективные способы решения задач в зависимости от условий.
Предметные
- Знание способов кодирования символов и правил определения длины кодового слова.
- Умение вычислять количество информации, объём сообщения и число возможных кодовых комбинаций.
- Умение применять формулы объёма информации к сообщениям и проверять единицы измерения результата.
Универсальные учебные действия (УУД)
Личностные УУД
- Смыслообразование (связь между изучением сетевых протоколов и пониманием работы Интернета).
- Самоопределение (оценка своих возможностей в решении задач повышенной сложности).
Регулятивные УУД
- Целеполагание как постановка учебной задачи на основе соотнесения того, что уже известно, и того, что еще неизвестно.
- Планирование — определение последовательности промежуточных целей с учетом конечного результата (решение задачи ЕГЭ).
- Самоконтроль и коррекция при выполнении вычислений в двоичной системе.
Познавательные УУД
- Построение логической цепи рассуждений.
- Анализ объектов с целью выделения признаков (анализ структуры IP-адреса).
- Выбор знаково-символических средств (использование масок).
Коммуникативные УУД
- Инициативное сотрудничество в поиске и сборе информации.
- Умение с достаточной полнотой и точностью выражать свои мысли в соответствии с задачами и условиями коммуникации.
Подготовка учителя к уроку
- Подготовить карточки с заданиями формата №4 и №7 ЕГЭ — 30 шт.
- Вывести на экран таблицу степеней двойки и примеры равномерного кодирования.
- Подготовить схемы деревьев кодов для объяснения условия Фано.
- Подготовить таймер для контроля времени на этапах решения задач.
- Подготовить раздаточный материал с алгоритмами проверки кодов и типичными ошибками.
Ход урока
Этап 1. Мотивация и самоопределение (3 мин)
Цель этапа: создать условия для возникновения внутренней потребности включения в учебную деятельность.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Здравствуйте! Представьте, что сообщение передаётся в виде последовательности нулей и единиц. Как компьютер понимает, где заканчивается один символ и начинается другой? | Слушают учителя, приводят примеры цифровых кодов. |
2 мин | В ЕГЭ задания №4 и №7 проверяют умение работать с кодами и условием Фано. Сегодня разберём чёткие алгоритмы, которые помогут не терять эти баллы. | Отвечают на вопросы, записывают тему урока и формулируют цель работы. |
Завершение этапа: учитель подводит итог: «Чтобы уверенно решать задачи на кодирование, вспомним двоичную систему и правила представления информации».
Этап 2. Актуализация знаний (5 мин)
Цель этапа: повторить понятия «код», «кодовое слово», равномерное и неравномерное кодирование, а также вспомнить признаки выполнения условия Фано.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | «Вспомним: что называют кодом и кодовым словом? Чем отличается равномерное кодирование от неравномерного? Как найти объём сообщения при известной длине кодового слова?» | Отвечают: код задаёт правила представления информации, кодовое слово — последовательность символов для одного сообщения; при равномерном кодировании длина слов одинакова. |
2 мин | «Что означает условие Фано? Может ли код 0 быть кодовым словом, если уже используется код 01?» | Формулируют правило: ни одно кодовое слово не должно быть началом другого; делают вывод, что код 0 и код 01 несовместимы. |
Завершение этапа: учитель подводит итог: «Мы вспомнили характеристики кодов. Теперь разберём алгоритмы решения заданий на объём сообщения и проверку условия Фано».
Этап 3. Выявление затруднения и построение проекта (5 мин)
Цель этапа: выявить затруднения при выборе длины кодовых слов и проверке того, является ли код префиксным.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | «Даны четыре символа и двоичный код. Как определить минимальную длину равномерного кода? Что изменится, если алфавит содержит 5, 8 или 9 символов?» | Используют степени двойки: подбирают наименьшее число бит, для которого число кодовых комбинаций не меньше мощности алфавита. |
2 мин | «Даны кодовые слова 0, 10, 110 и 111. Выполняется ли условие Фано? Сформулируем план решения». | Проверяют, начинается ли одно слово с другого, и формулируют план: выписать слова, сравнить начала, сделать вывод о выполнении условия Фано. |
Завершение этапа: учитель подводит итог: «План есть: сначала определим параметры кодирования, затем проверим кодовые слова попарно и применим условие Фано».
Этап 4. Открытие нового знания (12 мин)
Цель этапа: изучить алгоритмы решения заданий на кодирование информации и вычисление объёма информационных сообщений.
Время | Действие учителя | Действие учеников |
|---|---|---|
6 мин | Разберём задачу на кодирование: если алфавит содержит N символов, минимальная длина равномерного двоичного кода — наименьшее число k, для которого 2^k ≥ N. При длине кодового слова k и количестве слов m объём сообщения равен m · k бит. | Определяют длину кодового слова по степеням двойки и вычисляют объём сообщения. |
6 мин | Разберём задание №7 на объём информации. Если один символ кодируется i битами, а сообщение содержит k символов, его объём равен k · i бит. При необходимости переводим биты в байты: 1 байт = 8 бит. | Выделяют длину сообщения и объём одного символа, составляют формулу, выполняют вычисления и переводят единицы измерения. |
Запись в тетрадях
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
- Равномерный код: все кодовые слова имеют одинаковую длину.
- Минимальная длина двоичного кода k определяется условием 2^k ≥ N, где N — мощность алфавита.
- Объём сообщения при равномерном кодировании: число кодовых слов умножается на длину одного слова.
- Прямое условие Фано: ни одно кодовое слово не является началом другого.
- Обратное условие Фано: ни одно кодовое слово не является окончанием другого.
Завершение этапа: учитель подводит итог: «Для задач на кодирование сначала определяем длину слова и объём сообщения, а для условия Фано отдельно проверяем начала или окончания кодовых слов — в зависимости от формулировки задания».
Этап 5. Первичное закрепление (7 мин)
Цель этапа: отработать алгоритмы решения типовых заданий ЕГЭ №4 на кодирование информации и №7 на проверку условия Фано.
Время | Действие учителя | Действие учеников |
|---|---|---|
4 мин | Разберём задачу на кодирование: алфавит содержит 9 символов. Какова минимальная длина равномерного двоичного кода? Объясните выбор. | Используют условие 2^k ≥ 9: 2^3 = 8 недостаточно, а 2^4 = 16, поэтому минимальная длина кода — 4 бита. |
3 мин | Разберём задачу на условие Фано: даны кодовые слова 0, 10, 110 и 111. Выполняется ли прямое условие Фано? А обратное? | Проверяют слова попарно. Прямое условие выполняется: ни одно слово не является началом другого. Обратное не выполняется: 10 является окончанием слова 110. |
Эталон решения (задачи №4 и №7)
Задача на кодирование: 9 символов требуют минимальной длины $k$, для которой $2^k \ge 9$. Так как $2^3 = 8 < 9$, а $2^4 = 16 \ge 9$, получаем $k = 4$ бита.
Задача на условие Фано: прямое условие выполняется, поскольку ни одно слово не является началом другого. Обратное условие не выполняется, поскольку слово 10 является окончанием слова 110.
Задача на условие Фано: прямое условие выполняется, поскольку ни одно слово не является началом другого. Обратное условие не выполняется, поскольку слово 10 является окончанием слова 110.
Завершение этапа: учитель подводит итог: «При решении задач на кодирование сначала сравниваем число символов с подходящими степенями двойки. При проверке условия Фано внимательно различаем начало и окончание кодового слова».
Этап 6. Самостоятельная работа (7 мин)
Цель этапа: применить алгоритмы решения задач на кодирование информации и проверки прямого и обратного условий Фано в самостоятельной работе.
Самостоятельная работа (7 минут)
Время | Действие учителя | Действие учеников |
|---|---|---|
5 мин | Раздаю карточки с двумя задачами: первая — на определение минимальной длины равномерного двоичного кода и объёма сообщения, вторая — на проверку прямого и обратного условий Фано. У вас 5 минут. Работайте самостоятельно и записывайте ход решения. | Самостоятельно решают задачи, определяют длину кодовых слов и проверяют кодовые слова на наличие общего начала или окончания. |
2 мин | Время вышло. Выведите на экран эталонные ответы и краткие решения. Проверьте себя: отметьте верные решения знаком «+», а ошибку подчеркните и определите, на каком шаге она возникла. | Сверяют решения с эталоном, выполняют самопроверку и фиксируют затруднения. |
Самостоятельная работа. Два варианта
Вариант 1
1. Алфавит содержит 13 символов. Определите минимальную длину равномерного двоичного кода. Сколько бит потребуется для сообщения из 20 кодовых слов?
2. Кодовые слова: 0, 10, 110, 111. Определите, выполняется ли прямое условие Фано. Выполняется ли обратное условие Фано?
Вариант 2
1. Алфавит содержит 25 символов. Определите минимальную длину равномерного двоичного кода. Сколько бит потребуется для сообщения из 12 кодовых слов?
2. Кодовые слова: 00, 01, 10, 110. Определите, выполняется ли прямое условие Фано. Выполняется ли обратное условие Фано?
Ответы
Вариант 1. 1) $2^3 = 8 < 13$, $2^4 = 16 \ge 13$, поэтому длина кода — 4 бита; объём сообщения — $20 \cdot 4 = 80$ бит. 2) Прямое условие выполняется: ни одно слово не является началом другого. Обратное условие не выполняется: слово 10 является окончанием слова 110.
Вариант 2. 1) $2^4 = 16 < 25$, $2^5 = 32 \ge 25$, поэтому длина кода — 5 бит; объём сообщения — $12 \cdot 5 = 60$ бит. 2) Прямое условие выполняется: ни одно слово не является началом другого. Обратное условие не выполняется: слово 10 является окончанием слова 110.
Вариант 1
1. Алфавит содержит 13 символов. Определите минимальную длину равномерного двоичного кода. Сколько бит потребуется для сообщения из 20 кодовых слов?
2. Кодовые слова: 0, 10, 110, 111. Определите, выполняется ли прямое условие Фано. Выполняется ли обратное условие Фано?
Вариант 2
1. Алфавит содержит 25 символов. Определите минимальную длину равномерного двоичного кода. Сколько бит потребуется для сообщения из 12 кодовых слов?
2. Кодовые слова: 00, 01, 10, 110. Определите, выполняется ли прямое условие Фано. Выполняется ли обратное условие Фано?
Ответы
Вариант 1. 1) $2^3 = 8 < 13$, $2^4 = 16 \ge 13$, поэтому длина кода — 4 бита; объём сообщения — $20 \cdot 4 = 80$ бит. 2) Прямое условие выполняется: ни одно слово не является началом другого. Обратное условие не выполняется: слово 10 является окончанием слова 110.
Вариант 2. 1) $2^4 = 16 < 25$, $2^5 = 32 \ge 25$, поэтому длина кода — 5 бит; объём сообщения — $12 \cdot 5 = 60$ бит. 2) Прямое условие выполняется: ни одно слово не является началом другого. Обратное условие не выполняется: слово 10 является окончанием слова 110.
Завершение этапа: учитель подводит итог: «При самостоятельном решении важно сначала определить, что именно проверяется: длина и объём кода, прямое условие Фано или обратное. Ошибки разберём при подведении итогов».
Этап 7. Рефлексия и домашнее задание (3 мин)
Цель этапа: осознать результаты самостоятельной работы, выявить оставшиеся затруднения и определить направление дальнейшего повторения.
Время | Действие учителя | Действие учеников |
|---|---|---|
1,5 мин | Подведём итоги. Что оказалось самым сложным: определение длины кодового слова, расчёт объёма сообщения, проверка прямого условия Фано или проверка обратного условия Фано? | Называют этап решения, который вызвал затруднение, и объясняют причину ошибки. |
1,5 мин | Запишите домашнее задание: повторить алгоритмы кодирования и условия Фано; решить задачи на минимальную длину кода, объём сообщения, а также отдельно проверить прямое и обратное условия Фано. | Записывают домашнее задание и выбирают, какой алгоритм нужно повторить. |
Критерии оценивания практической работы
- «5» — верно решены обе задачи: определены параметры равномерного кодирования и корректно проверено условие Фано; приведён ход решения.
- «4» — обе задачи решены с одной несущественной ошибкой в вычислениях или формулировке вывода, при этом общий способ решения выбран верно.
- «3» — правильно решена одна задача или в обеих задачах есть отдельные верные шаги, но допущены ошибки при выборе длины кода, вычислении объёма сообщения либо проверке условия Фано.
- «2» — отсутствует верное решение обеих задач или не применены изученные алгоритмы.
- При оценивании учитываются правильность ответа, обоснование решения и различение прямого и обратного условий Фано.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Что оказалось самым сложным: определение длины кодового слова, расчёт объёма сообщения, проверка прямого или обратного условия Фано? | Выявление конкретного затруднения и выбор направления для повторения. |
Какой алгоритм решения ты можешь объяснить самостоятельно? | Проверка осознанности и умения воспроизводить последовательность действий. |
Какую оценку за сегодняшнюю работу ты бы себе поставил и почему? | Формирование навыка самооценки и ответственности за результат. |
Завершающее слово учителя
Сегодня мы разобрали алгоритмы решения заданий ЕГЭ №4 на кодирование информации и №7 на условие Фано. Важно сначала определить, что требуется найти, затем последовательно выполнить вычисления или сравнить кодовые слова. Не забывайте различать прямое условие Фано — проверку начал кодовых слов — и обратное — проверку окончаний. Спасибо за работу!
Домашнее задание
ОТВЕТЫ к ДЗ
Вариант для учащихся, не планирующих сдавать ЕГЭ
1. Минимальная длина кода: 3 бита, так как $2^2 = 4 < 6$, а $2^3 = 8 \ge 6$.
2. Объём сообщения: $15 \cdot 4 = 60$ бит = 7,5 байта.
3. Прямое условие Фано выполняется: ни одно из слов 0, 10, 110, 111 не является началом другого.
Вариант для учащихся, планирующих сдавать ОГЭ
1. Минимальная длина кода: 5 бит, так как $2^4 = 16 < 17$, а $2^5 = 32 \ge 17$. Объём сообщения: $35 \cdot 5 = 175$ бит.
2. Средний объём одного символа: $150 \cdot 8 : 240 = 5$ бит.
3. $3$ Кбайт = $3072$ байта; число символов: $3072 : 2 = 1536$.
4. Прямое условие Фано не выполняется: 0? Нет, среди слов 00, 01, 10, 110, 111 ни одно не является началом другого, поэтому прямое условие выполняется. Обратное условие не выполняется: 10 — окончание слова 110; 11 — окончание слов 111 и 110, но слова 11 в наборе нет, поэтому учитывается только пара 10 и 110.
5. Один из кратчайших префиксных кодов для пяти символов: 0, 10, 110, 1110, 1111.
6. 3 Кбайт = 24576 бит; $24576 : 4096 = 6$ бит на символ. Утверждать, что все символы имеют одинаковую длину кода, нельзя: известно только среднее количество бит на символ, а длина кодов могла быть разной.
Вариант для учащихся, не планирующих сдавать ЕГЭ
1. Минимальная длина кода: 3 бита, так как $2^2 = 4 < 6$, а $2^3 = 8 \ge 6$.
2. Объём сообщения: $15 \cdot 4 = 60$ бит = 7,5 байта.
3. Прямое условие Фано выполняется: ни одно из слов 0, 10, 110, 111 не является началом другого.
Вариант для учащихся, планирующих сдавать ОГЭ
1. Минимальная длина кода: 5 бит, так как $2^4 = 16 < 17$, а $2^5 = 32 \ge 17$. Объём сообщения: $35 \cdot 5 = 175$ бит.
2. Средний объём одного символа: $150 \cdot 8 : 240 = 5$ бит.
3. $3$ Кбайт = $3072$ байта; число символов: $3072 : 2 = 1536$.
4. Прямое условие Фано не выполняется: 0? Нет, среди слов 00, 01, 10, 110, 111 ни одно не является началом другого, поэтому прямое условие выполняется. Обратное условие не выполняется: 10 — окончание слова 110; 11 — окончание слов 111 и 110, но слова 11 в наборе нет, поэтому учитывается только пара 10 и 110.
5. Один из кратчайших префиксных кодов для пяти символов: 0, 10, 110, 1110, 1111.
6. 3 Кбайт = 24576 бит; $24576 : 4096 = 6$ бит на символ. Утверждать, что все символы имеют одинаковую длину кода, нельзя: известно только среднее количество бит на символ, а длина кодов могла быть разной.
Вариант | Задания и ответы | Цель |
|---|---|---|
Для учащихся, не планирующих сдавать ЕГЭ | Задания 1. Алфавит содержит 6 символов. Определите минимальную длину равномерного двоичного кода. 2. Сообщение состоит из 15 символов, каждый кодируется 4 битами. Найдите объём сообщения в битах и байтах. 3. Определите, выполняется ли прямое условие Фано для кодовых слов 0, 10, 110, 111. Объясните ответ. | Закрепить базовые понятия: длину кода, объём сообщения и прямое условие Фано. |
Для учащихся, планирующих сдавать ОГЭ | Задания 1. Алфавит содержит 17 символов. Найдите минимальную длину равномерного двоичного кода и объём сообщения из 35 кодовых слов. 2. Текст содержит 240 символов и занимает 150 байт. Определите среднее количество бит на символ. 3. Сообщение состоит из 3 Кбайт. Сколько в нём символов, если каждый символ кодируется 2 байтами? 4. Для кодовых слов 00, 01, 10, 110, 111 определите, выполняются ли прямое и обратное условия Фано. Приведите нарушающие пары. 5. Постройте двоичный префиксный код для пяти символов, используя как можно более короткие кодовые слова. 6. Сообщение содержит 4096 символов и занимает 3 Кбайт. Можно ли утверждать, что все символы имеют одинаковую длину кода? Обоснуйте ответ. | Закрепить вычисление объёма информации, перевод единиц, анализ прямого и обратного условий Фано и решение комбинированных задач повышенного уровня. |
