Алгоритмы сжатия данных: как уместить невозможное
Цели и задачи
- Цель: к концу урока учащиеся смогут объяснить принципы работы алгоритмов сжатия без потерь (RLE, алгоритм Хаффмана), самостоятельно построить дерево Хаффмана для короткой строки и оценить эффективность сжатия различных типов данных.
- Образовательная задача: изучить теоретические основы избыточности информации и механизмы работы основных алгоритмов сжатия.
- Развивающая задача: развивать навыки логического мышления и анализа через решение задач на построение оптимальных кодов.
- Воспитательная задача: формировать культуру работы с данными и понимание ценности вычислительных ресурсов в профессиональной деятельности.
- Профориентационная задача: показать связь темы с задачами Data Science и разработки высоконагруженных систем.
Планируемые результаты
Личностные
- Готовность к осознанному выбору будущей профессии в сфере IT.
- Понимание роли информационных процессов в современном обществе.
- Способность к самооценке на основе критериев успешности учебной деятельности.
Метапредметные
- Познавательные: умение выбирать наиболее эффективные способы решения задач в зависимости от конкретных условий (выбор алгоритма сжатия).
- Регулятивные: владение навыками самоконтроля и коррекции своих действий при выполнении практической работы.
- Коммуникативные: умение организовывать учебное сотрудничество в парах, аргументировать свою точку зрения.
Предметные
- Знание понятий «избыточность информации», «сжатие с потерями» и «сжатие без потерь».
- Умение применять алгоритм RLE для кодирования последовательностей.
- Владение алгоритмом построения префиксного кода Хаффмана.
- Понимание связи темы с заданием №4 ЕГЭ по информатике (условие Фано).
Универсальные учебные действия (УУД)
Личностные УУД
- Смыслообразование (связь между целью сжатия и экономией ресурсов).
- Нравственно-этическая ориентация (этика использования данных).
Регулятивные УУД
- Целеполагание как постановка учебной задачи на основе соотнесения того, что уже известно, и того, что еще неизвестно.
- Оценка — выделение и осознание учащимся того, что уже усвоено и что еще подлежит усвоению.
Познавательные УУД
- Поиск и выделение необходимой информации из практического эксперимента.
- Моделирование — преобразование объекта из чувственной формы в модель (построение дерева).
- Анализ объектов с целью выделения признаков (частотный анализ).
Коммуникативные УУД
- Инициативное сотрудничество в поиске и сборе информации.
- Умение с достаточной полнотой и точностью выражать свои мысли в соответствии с задачами и условиями коммуникации.
Подготовка учителя к уроку
- Подготовить презентацию с визуализацией построения дерева Хаффмана.
- Распечатать рабочие листы для парной работы (текст для сжатия, таблица частот) — 15 экземпляров.
- Подготовить набор файлов разных форматов (.txt, .bmp, .jpg, .docx) для экспериментального сжатия на ПК.
- Проверить наличие установленных архиваторов (7-Zip или WinRAR) на рабочих станциях учащихся.
- Выписать на доску ключевые термины: Redundancy, Lossless, Lossy, RLE, Huffman coding.
Ход урока
Этап 1. Мотивация и «Крючок» (3 мин)
Цель этапа: вызвать познавательный интерес через осознание масштабов проблемы хранения данных.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель: «"Добрый день, коллеги! Представьте, что каждую секунду человечество генерирует около 2 петабайт данных. Если бы мы записывали их на CD-диски и складывали в стопку, она бы достигла Луны за пару недель. Почему же наши жесткие диски еще не переполнились, а видео в 4K загружается на смартфон за секунды? Сегодня мы заглянем под капот цифрового мира и узнаем, как информатика побеждает пространство и время с помощью алгоритмов сжатия. Как вы думаете, можно ли сжать файл бесконечно?"» | Ученики включаются в диалог, предлагают свои варианты ответов на вопрос о бесконечном сжатии. Высказывают предположения о том, что данные имеют предел сжатия, связанный с их энтропией. |
Завершение этапа: учитель подводит итог: «"Ваши догадки интересны, но чтобы ответить точно, нам нужно понять, что именно в данных является 'лишним'. Переходим к поиску избыточности."»
Этап 2. Актуализация знаний и фиксация затруднения (5 мин)
Цель этапа: повторить базовые знания о кодировании и столкнуть учеников с проблемой неэффективности равномерного кода.
Время | Действие учителя | Действие учеников |
|---|---|---|
5 мин | Учитель использует прием "Интеллектуальная разминка": «"Давайте вспомним: если у нас есть алфавит из 4 символов (А, Б, В, Г), сколько бит нам нужно на один символ при равномерном кодировании? Правильно, 2 бита. А теперь представьте строку: ААААААААААБВ. В ней 12 символов. При обычном подходе это 24 бита. Попробуйте в парах за 30 секунд предложить способ записать эту строку короче, не теряя ни одной буквы."» | Ученики работают в парах. Большинство предлагает вариант типа "10А1Б1В". Учитель фиксирует это на доске. |
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Запись в тетрадях
Равномерный код: N символов * i бит. Избыточность — наличие в сообщении повторяющихся фрагментов или предсказуемых структур.
Завершение этапа: учитель подводит итог: «"Вы только что изобрели алгоритм RLE. Но что, если символы не идут подряд, а просто встречаются с разной частотой? Например, в русском языке буква 'о' встречается часто, а 'ф' — редко. Как это использовать?"»
Этап 3. Открытие нового знания: Алгоритм Хаффмана (12 мин)
Цель этапа: изучить алгоритм построения оптимального неравномерного кода.
Время | Действие учителя | Действие учеников |
|---|---|---|
12 мин | Учитель объясняет алгоритм Хаффмана, используя визуализацию на слайдах: «"Дэвид Хаффман в 1952 году предложил гениальную вещь: давать самым частым символам самые короткие коды. Давайте построим дерево для слова 'МАТЕМАТИКА'. Шаг 1: считаем частоты. Шаг 2: выбираем два самых редких символа и объединяем их в узел..."» Учитель демонстрирует построение дерева на доске, комментируя каждый выбор. | Ученики следят за построением, задают уточняющие вопросы. Затем в парах на рабочих листах пробуют построить дерево для короткой фразы «КОЛОКОЛ». Один ученик считает частоты, второй рисует ветви дерева. |
Эталон решения
Слово «КОЛОКОЛ»: К-2, О-3, Л-2. 1) Соединяем К(2) и Л(2) -> узел (4). 2) Соединяем узел (4) и О(3) -> корень (7). Коды: О = 0, К = 10, Л = 11. Проверка условия Фано: ни одно кодовое слово не является началом другого.
Завершение этапа: учитель подводит итог: «"Мы получили коды разной длины, и теперь наше сообщение стало компактнее. Но работает ли это одинаково для всех типов файлов? Проверим на практике."»
Этап 4. Практикум: ИКТ-эксперимент (10 мин)
Цель этапа: экспериментально подтвердить эффективность сжатия для разных типов данных.
Время | Действие учителя | Действие учеников |
|---|---|---|
10 мин | Учитель дает задание: «"Садитесь за компьютеры. В папке 'Data' лежат 4 файла: текстовый документ, несжатое фото (.bmp), сжатое фото (.jpg) и исполняемый файл (.exe). Ваша задача — сжать их архиватором 7-Zip и заполнить таблицу: исходный размер, размер после сжатия, коэффициент сжатия. Подумайте, почему результаты такие разные?"» | Ученики выполняют практическую работу, архивируют файлы, вычисляют проценты сжатия. Обнаруживают, что .jpg почти не сжимается, а .txt и .bmp сжимаются очень сильно. |
Завершение этапа: учитель подводит итог: «"Вы увидели, что сжатие зависит от природы данных. Межпредметная связь: в лингвистике это называется избыточностью языка, в математике — статистической зависимостью."»
Этап 5. Включение в систему знаний и связь с ЕГЭ (5 мин)
Цель этапа: показать практическое применение знаний в рамках подготовки к экзаменам.
Время | Действие учителя | Действие учеников |
|---|---|---|
5 мин | Учитель выводит на экран задание №4 из КИМ ЕГЭ: «"Посмотрите на задачу. Здесь требуется подобрать код для буквы так, чтобы сообщение было минимальной длины и допускало однозначное декодирование. Это и есть упрощенный принцип Хаффмана. Давайте решим её устно, используя метод построения дерева."» | Ученики анализируют условие, строят в черновиках дерево Фано, находят кратчайший свободный код для искомого символа. Отвечают с места, аргументируя выбор. |
Завершение этапа: учитель подводит итог: «"Как видите, алгоритмы сжатия — это не просто теория, это база, которая поможет вам набрать баллы на экзамене и понять, как работают протоколы интернета."»
Этап 6. Рефлексия и домашнее задание (5 мин)
Цель этапа: обобщить изученный материал и провести самооценку.
Время | Действие учителя | Действие учеников |
|---|---|---|
5 мин | Учитель проводит рефлексию «Билет на выход»: «"Прежде чем уйти, ответьте на один вопрос на стикере: какой алгоритм — RLE или Хаффмана — эффективнее для сжатия фотографии звездного неба (много черных пикселей подряд)? И почему?"» Учитель раздает задание на дом. | Ученики пишут ответ на стикере (ожидается ответ про RLE из-за длинных цепочек одинаковых пикселей), приклеивают на край парты и записывают домашнее задание. |
Критерии оценивания практической работы
- «5» — Верно построены дерево Хаффмана и коды для тестовой строки; корректно проведено экспериментальное сжатие 4-х типов файлов, сделан правильный вывод о причинах разницы в сжатии.
- «4» — Допущены незначительные ошибки в построении дерева (например, перепутаны 0 и 1), или не полностью заполнена таблица эксперимента.
- «3» — Ученик понимает принцип сжатия, но не может самостоятельно построить коды Хаффмана; таблица эксперимента заполнена частично.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Какой этап построения дерева Хаффмана был самым сложным? | Выявление затруднений в алгоритмическом мышлении. |
Почему JPEG почти не сжался архиватором? | Проверка понимания разницы между сжатием с потерями и без потерь. |
Где в вашей будущей профессии могут пригодиться знания об оптимизации данных? | Формирование профессиональной мотивации. |
Завершающее слово учителя
«"Сегодня мы приоткрыли завесу тайны над тем, как информация становится компактной. Мы узнали, что за каждой 'zip-папкой' стоит строгая математика и логика. На следующем уроке мы разберем алгоритмы сжатия с потерями — те самые, что позволяют нам смотреть видео на YouTube даже при слабом интернете. Если сегодня вам было сложно с деревом Хаффмана — не переживайте, это одна из самых красивых и глубоких тем в информатике, мы еще потренируемся на практикуме. До встречи!"»
Домашнее задание
Уровень сложности | Задания | Описание |
|---|---|---|
Базовый (обязательный) | Параграф 2.3 учебника, задачи 5-7 после параграфа. | Повторение теории, решение простых задач на RLE. |
Средний (повышающий) | Построить код Хаффмана для своей фамилии. | Индивидуальная практика построения дерева для уникального набора данных. |
Продвинутый (дополнительный) | Написать на Python скрипт для реализации простейшего RLE-сжатия. | Развитие навыков программирования и реализации алгоритмов. |