Программное обеспечение компьютера. Алгоритм Хаффмана
Цели и задачи
- Цель: сформировать понимание принципа оптимального кодирования информации и научить строить дерево Хаффмана для сжатия данных без потерь.
- Образовательная задача: изучить алгоритм построения префиксного кода переменной длины и его связь с условием Фано.
- Развивающая задача: развивать логическое мышление и аналитические способности при поиске оптимального пути сжатия сообщения.
- Воспитательная задача: способствовать развитию навыков командной работы и интереса к будущей профессиональной деятельности в сфере IT.
- Профориентационная задача: показать практическое применение алгоритмов сжатия в реальном ПО (архиваторы, форматы изображений).
Планируемые результаты
Личностные
- Готовность к осознанному выбору будущей профессии на основе понимания роли алгоритмов в современном цифровом мире.
- Способность к самооценке своих достижений в изучении сложных алгоритмических структур.
- Установка на поиск наиболее эффективных способов решения практических задач.
- Развитие критического мышления в оценке качества программного обеспечения.
Метапредметные
- Умение создавать и преобразовывать модели (деревья) для решения задач сжатия данных.
- Навык смыслового чтения при анализе алгоритмических описаний.
- Способность соотносить свои действия с планируемыми результатами и осуществлять контроль.
- Умение аргументированно представлять результаты своей исследовательской деятельности.
Предметные
- Знать определение оптимального кода и условие Фано.
- Уметь вычислять частоту встречаемости символов в тексте.
- Владеть навыком построения дерева Хаффмана по заданному набору символов.
- Уметь кодировать и декодировать сообщения, используя полученную таблицу кодов.
Универсальные учебные действия (УУД)
Личностные УУД
- Смыслообразование: понимание ценности эффективных алгоритмов для экономии ресурсов памяти.
- Самоопределение: осознание своих возможностей в решении задач олимпиадного уровня и ЕГЭ.
Регулятивные УУД
- Целеполагание как постановка учебной задачи на основе соотнесения того, что уже известно, и того, что еще неизвестно.
- Оценка — выделение и осознание учащимся того, что уже усвоено и что еще подлежит усвоению.
Познавательные УУД
- Моделирование: построение двоичного дерева как знаково-символического средства.
- Поиск и выделение необходимой информации из предложенных кейсов.
- Логические действия: анализ объектов с целью выделения признаков, синтез как составление целого из частей.
Коммуникативные УУД
- Инициативное сотрудничество в поиске и сборе информации.
- Умение с достаточной полнотой и точностью выражать свои мысли в соответствии с задачами коммуникации.
Подготовка учителя к уроку
- Распечатать рабочие листы с таблицами частот для практической работы (по одному на каждого ученика).
- Подготовить презентацию с визуализацией этапов построения дерева Хаффмана.
- Подготовить набор карточек с буквами и их частотами для фронтальной работы у доски.
- Проверить работоспособность проектора и интерактивной доски.
- Подготовить примеры файлов разных форматов (txt, docx, zip) для демонстрации эффективности сжатия.
Ход урока
Этап 1. Мотивация и самоопределение (3 мин)
Цель этапа: создать условия для возникновения внутренней потребности включения в учебную деятельность через проблемную ситуацию.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель: "Здравствуйте! Представьте, что вы работаете в космическом агентстве. Вам нужно отправить текстовое сообщение на Марс. Стоимость передачи 1 мегабайта данных — 10 миллионов рублей. Ваше сообщение занимает 100 Мб. Бюджет ограничен 500 миллионами. Как нам выполнить задачу, не потеряв ни одного символа? Какие программы мы используем в повседневной жизни для уменьшения объема файлов?" | Ученики: "Нужно сжать данные! Мы используем архиваторы: WinRAR, 7-Zip. Еще есть сжатие в форматах картинок и видео, но там могут быть потери. А нам нужно без потерь." |
Завершение этапа: учитель подводит итог: "Верно, нам нужны алгоритмы сжатия без потерь. Сегодня мы 'изобретем' один из самых известных алгоритмов, который лежит в основе большинства современных архиваторов — алгоритм Хаффмана."
Этап 2. Актуализация знаний (5 мин)
Цель этапа: повторить базовые понятия кодирования и зафиксировать затруднение в использовании равномерного кода.
Время | Действие учителя | Действие учеников |
|---|---|---|
5 мин | Учитель: "Давайте вспомним, как компьютер кодирует текст обычно. Если у нас алфавит из 4 символов (А, Б, В, Г), сколько бит нам нужно на один символ при равномерном кодировании? Запишите возможные коды." Учитель рисует на доске таблицу: А-00, Б-01, В-10, Г-11. "А теперь представьте, что в нашем тексте буква А встречается 100 раз, а буква Г — всего 1 раз. Рационально ли тратить на них одинаковое количество бит?" | Ученики: "Нам нужно 2 бита на символ. Если А встречается чаще, логично дать ей код покороче, например '0', а редким буквам — коды подлиннее. Но тогда возникнет проблема: как понять, где заканчивается одна буква и начинается другая, если у них разная длина?" |
Завершение этапа: учитель подводит итог: "Вы нащупали главную проблему: как сделать код разной длины, чтобы он оставался однозначно декодируемым. Это и будет нашей целью."
Этап 3. Выявление места и причины затруднения (3 мин)
Цель этапа: сформулировать проблему невозможности случайного выбора кодов разной длины.
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель: "Давайте попробуем: пусть А = 0, Б = 01, В = 1. Закодируйте слово 'АВ'. Что получится? 01. Но 01 — это же буква Б! Как же нам составить коды так, чтобы ни один код не был началом другого? Помните, как называется это условие в задачах ЕГЭ?" | Ученики: "Это условие Фано! Оно гласит, что никакой код не должен быть префиксом другого. Но как построить такой код, чтобы он был еще и самым коротким для всего текста? Мы не знаем системы." |
Завершение этапа: учитель подводит итог: "Итак, нам нужен системный метод построения префиксных кодов переменной длины, зависящий от частоты букв. Сформулируем тему урока."
Этап 4. Построение проекта выхода из затруднения (3 мин)
Цель этапа: поставить цель урока и наметить план действий по открытию алгоритма.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель: "Какова цель нашего урока?" Учитель помогает сформулировать: "Цель — научиться строить оптимальный код Хаффмана. Нам понадобится: 1. Посчитать частоты букв. 2. Найти способ их объединения. 3. Построить схему (дерево). 4. Снять коды. Давайте приступим к исследованию." | Ученики: "Цель — узнать алгоритм Хаффмана и научиться сжимать текст. План: сначала анализируем частоту, потом строим дерево, потом получаем коды." |
Завершение этапа: учитель подводит итог: "План готов. Начинаем наше исследование с небольшого эксперимента."
Этап 5. Реализация проекта — 'Открытие' алгоритма (12 мин)
Цель этапа: через исследовательскую деятельность под руководством учителя вывести шаги алгоритма Хаффмана.
Время | Действие учителя | Действие учеников |
|---|---|---|
12 мин | Учитель: "Представим слово 'МАТЕМАТИКА'. Давайте посчитаем, сколько раз встречается каждая буква." Учитель записывает на доске: М(2), А(3), Т(2), Е(1), И(1), К(1). "У нас есть идея: самые редкие буквы должны быть в самом низу дерева, чтобы их путь был длиннее. Какие буквы самые редкие?" Учитель показывает приём 'Слияние': "Давайте объединим Е(1) и И(1) в группу ЕИ с суммарным весом 2. Теперь у нас есть: М(2), А(3), Т(2), К(1) и ЕИ(2). Кто теперь самые редкие?" Учитель продолжает диалог, пока не построится всё дерево. "Теперь присвоим левым ветвям 0, а правым 1. Прочитайте код для буквы А и буквы Е." | Ученики: "Самые редкие Е, И и К. Объединяем Е и И, получаем вес 2. Теперь самые редкие К(1) и, например, Т(2). Или К(1) и М(2). Объединяем К с группой ЕИ или с другой буквой..." Ученики под руководством учителя строят дерево в тетрадях, суммируя веса. В конце считывают коды: "Для А получилось 01, для Е — 1100 (пример). Коды разные по длине!" |
Запись в тетрадях
- Алгоритм Хаффмана — алгоритм оптимального префиксного кодирования.
- Шаги: 1. Подсчет частот. 2. Сортировка по возрастанию. 3. Объединение двух узлов с минимальными весами. 4. Повторение до создания корня. 5. Присвоение 0 и 1 ребрам.
Эталон решения
Для набора весов {1, 1, 2, 2, 3}: 1) (1+1)=2. Набор: {2, 2, 2, 3}. 2) (2+2)=4. Набор: {2, 3, 4}. 3) (2+3)=5. Набор: {4, 5}. 4) (4+5)=9. Корень. Длина кода для веса 1 будет наибольшей.
Завершение этапа: учитель подводит итог: "Мы получили дерево, где ни один путь не является началом другого. Это и есть префиксный код. Проверим, как это работает на практике."
Этап 6. Первичное закрепление (7 мин)
Цель этапа: применить алгоритм для решения типовой задачи, аналогичной заданию ЕГЭ.
Время | Действие учителя | Действие учеников |
|---|---|---|
7 мин | Учитель раздает карточки с задачей: "Для кодирования букв Л, М, Н, О используются двоичные коды. Частоты: Л-10, М-20, Н-30, О-40. Постройте дерево Хаффмана и определите код для каждой буквы. Какова будет длина всего сообщения?" Учитель контролирует процесс, проходя по рядам. Используется приём 'Think-Pair-Share': сначала решают сами, потом сверяются с соседом. | Ученики: "Сначала берем Л(10) и М(20), объединяем — получаем узел 30. Теперь у нас есть узел 30, Н(30) и О(40). Объединяем узел 30 и Н(30) — получаем 60. Наконец, 60 и О(40) дают 100. Код О будет самым коротким — всего один бит!" |
Завершение этапа: учитель подводит итог: "Отлично! Вы заметили, что самая частая буква О получила код '1' (или '0'), что значительно экономит место. Теперь попробуйте сделать это полностью самостоятельно."
Этап 7. Самостоятельная работа с самопроверкой (7 мин)
Цель этапа: индивидуальная проверка усвоения алгоритма и умения декодировать сообщение.
Время | Действие учителя | Действие учеников |
|---|---|---|
7 мин | Учитель: "На экране вы видите дерево и закодированную последовательность 01101001. Используя дерево, декодируйте слово. Затем постройте свое дерево для слова 'КОЛОКОЛ' и проверьте себя по эталону на обороте карточки." Учитель выводит эталон на экран через 5 минут. | Ученики: "Декодируем: идем по дереву от корня. 0... 1... это буква К. Дальше 1... 0... это О. Получается слово 'КОКОС'. Теперь строим дерево для 'КОЛОКОЛ': К(2), О(3), Л(2). Объединяем К и Л..." Выполняют задание и сверяют с эталоном на экране. |
Завершение этапа: учитель подводит итог: "Поднимите зеленые карточки те, у кого дерево совпало с эталоном. Желтые — если есть одна ошибка в цифре. Красные — если принцип остался непонятен."
Этап 8. Рефлексия и домашнее задание (5 мин)
Цель этапа: осознание учащимися своей учебной деятельности, самооценка результатов.
Время | Действие учителя | Действие учеников |
|---|---|---|
5 мин | Учитель: "Наш урок подходит к концу. Мы сегодня были в роли разработчиков алгоритмов. Что было самым сложным? Где в реальной жизни вы встретитесь с результатами работы этого алгоритма?" Учитель объясняет домашнее задание разных уровней. | Ученики: "Сложно было не запутаться в суммировании весов. Алгоритм Хаффмана работает в ZIP-архивах и даже в JPEG. Мы теперь понимаем, почему некоторые файлы сжимаются лучше других." Записывают домашнее задание. |
Критерии оценивания практической работы
- "5" — дерево Хаффмана построено верно, веса узлов рассчитаны без ошибок, коды символов выписаны правильно, сообщение декодировано верно.
- "4" — алгоритм построения дерева соблюден, но допущена одна арифметическая ошибка в весах или при считывании кода.
- "3" — дерево построено частично верно, допущены ошибки в логике объединения узлов, но продемонстрировано понимание условия Фано.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Какой этап алгоритма показался вам наиболее 'умным' или необычным? | Осознание эстетики и логики алгоритма, развитие интереса к предмету. |
Смогли бы вы объяснить этот алгоритм другу за 1 минуту? | Проверка степени интериоризации знаний и навыка сжатого изложения. |
Как знание алгоритма Хаффмана поможет вам при подготовке к ЕГЭ? | Связь темы с практическими целями ученика (задание №4). |
Завершающее слово учителя
"Сегодня мы убедились, что информатика — это не только умение пользоваться программами, но и глубокая математическая логика, позволяющая экономить ресурсы. Алгоритм Хаффмана — это классика, которая уже 70 лет не теряет актуальности. Если вы поняли его принцип, вам будет гораздо проще разобраться с любыми методами сжатия данных. На следующем уроке мы обсудим программное обеспечение для защиты информации. До встречи!"
Домашнее задание
Уровень | Что задать | Зачем |
|---|---|---|
Базовый | Построить дерево Хаффмана для фразы из 15-20 символов (например, 'ИНФОРМАТИКА - ЭТО КРУТО'), выписать коды всех букв. | Закрепление базового навыка построения дерева и считывания префиксных кодов. |
Средний | Сравнить объем сообщения в битах при использовании равномерного 8-битного кода и кода Хаффмана для той же фразы. | Осознание эффективности (коэффициента сжатия) изученного алгоритма. |
Продвинутый | Исследовать вопрос: в каком случае алгоритм Хаффмана не даст выигрыша в памяти по сравнению с равномерным кодом? Привести пример. | Развитие аналитического мышления и понимания границ применимости алгоритма. |
Контрольный вопрос: "Может ли код одной буквы быть 01, а другой 011 в алгоритме Хаффмана? Почему?"
