Ученики на Учителя.com


Конспект урока "Алгоритмы сжатия информации" 11 класс

Урок с ИКТ "Алгоритмы сжатия информации"
11-й класс
Цель урока: познакомить учащихся с принципами сжатия текстовой информации
для экономии и надежности при хранении и передаче.
Задачи урока:
образовательные – научиться сжимать текстовую информацию, используя
префиксный код Хаффмана;
развивающие – развивать логику мышления, интерес к познавательной
деятельности, творческую инициативу и активность;
воспитательные – воспитывать трудолюбие, дисциплину,
самостоятельность, навыки организации рабочего места.
Оборудование: мультимедийный проектор, MS PowerPoint 2003
Ход урока
I. 0рганизационный момент
Проверка готовности учащихся к уроку.
П. Проверка домашнего задания
Обсуждается выполнение упражнений, учащиеся отвечают на вопросы к
параграфу.
III. Объявление темы и цели урока, объяснение нового материала
Объяснение нового материала сопровождается показом презентации
(Приложение 1)
На предыдущем уроке был рассмотрен вопрос построения кода, обеспечивающего
обнаружение и исправление ошибок в процессе передачи информации по каналам связи
или записи ее на информационные носители. Однако существует еще одна задача,
возникающая при кодировании информации – обеспечение экономичности кодирования.
Решение этой задачи позволяет сократить место, необходимое для хранения информации
на информационных носителях, а при передаче – сократить время передачи и уменьшить
вероятность возникновения ошибки.
Для достижения экономичности кода используют алгоритмы сжатия или упаковки
информации, например, в программах-архиваторах. Принцип сжатия основывается на
том, что в информационных сообщениях, как правило, используется лишь часть символов,
входящих в стандартные кодовые таблицы.
Сжатие – это кодирование информации с помощью специального кода, приводящее
к уменьшению ее объема. Эффективность сжатия информации при кодировании можно
оценить с помощью коэффициента сжатия, который определяется по формуле:
,
где V
0
– объем исходного сообщения, а V
1
– объем сжатого сообщения.
Сжатие текстовой информации при кодировании основывается на том, что текст
может содержать далеко не все символы, входящие в кодовую таблицу. Например, текст
может содержать только числовую информацию. В этом случае необходимо закодировать
10 цифр, а также, возможно, знаки “+”, “- ” и десятичную запятую. Для кодирования
каждого символа в этом тексте можно обойтись 4 битами, что дает двукратную экономию
по сравнению со стандартными кодовыми таблицами.
Учащиеся на примере текстовой фразы “КОЛ ОКОЛО КОЛОКОЛА, А КОЛОКОЛ
ОКОЛО КОЛА” проводят кодирование текста, которое можно выполнить, используя
всего 3 бита на один символ, определяют объем получившегося кода и коэффициент его
сжатия, оценивают его эффективность по сравнению с ASCII-кодированием.
Далее учащимся сообщается, что указанный алгоритм сжатия является далеко не
единственным и не самым эффективным алгоритмом. Большую экономию при
кодировании дают неравномерные коды, принцип построения которых основывается на
том, что в информационных сообщениях, особенно на естественных языках, различные
символы встречаются с разной частотой. В этом случае для символов, которые часто
встречаются в тексте, кодовые слова должны быть более короткими, нежели для редко
встречающихся символов. Однако в этом случае возникают проблемы при декодировании
сообщений, записанных таким кодом. Эти проблемы были решены американскими
учеными К. Шенноном и Р. М. Фано, которые сформулировали условие, достаточное для
однозначного декодирования сообщений с переменной длиной кодовых слов: никакое
кодовое слово не может быть началом другого кодового слова.[1] Обычно это условие
называют условием Шеннона-Фано, а код, удовлетворяющий этому условию –
префиксным кодом.
Каждому набору кодовых слов можно поставить в соответствие ориентированный
граф (орграф), определяющий этот код. Демонстрируется построение орграфа,
соответствующего заданной кодовой таблице, содержащей набор кодовых слов, не
являющихся префиксным кодом. Далее демонстрируется построение графа для
префиксного кода по заданной кодовой таблице. Учащиеся делают вывод об особенностях
графа для префиксного кода, сравнивая два графа.
Наиболее эффективными неравномерными кодами являются префиксные коды.
Математиками доказано, что самый эффективный префиксный код получается с помощью
алгоритма Хаффмана. Чтобы получить код Хаффмана нужно построить орграф
следующим образом:
Все символы кодируемой информации образуют вершины-листья. Каждой вершине
приписывается вес, равный количеству вхождений данного символа в сжимаемое
сообщение.
Среди вершин, которым приписаны веса, выбираются две с наименьшими весами
(если таких пар несколько, выбирается любая из них).
Создается следующая вершина графа, из которой выходят две дуги к выбранным на
предыдущем шаге вершинам; одна дуга помечается символом 0, другая – символом
1.Созданной вершине приписывается вес, равный сумме весов выбранных вершин, а веса
этих двух вершин стираются.
К вершинам, которым приписаны веса, применяются шаги 2 и 3 до тех пор, пока не
останется одна вершина с весом, равным сумме весов исходных символов.
Пример кодирования заданной фразы “на дворе трава, на траве дрова” кодом
Хаффмана представлен на презентации. (Приложение 1, слайды 7-17)
Оценку эффективности построенного кода дают учащиеся, сравнивая его с кодом,
полученным путем стандартного способа кодирования с помощью кодовых таблиц и с
кодом, полученным путем кодирования с помощью равномерного кода.
IV. Закрепление материала
Учащиеся отвечают на вопросы и самостоятельно выполняют задание, в котором
требуется выполнить кодирование заданной фразы “от топота копыт пыль по полю
летит” с помощью стандартной кодовой таблицы КОИ-8, сжать текст равномерным
кодом и кодом Хаффмана, оценить эффективность кодирования с помощью вычисления
коэффициента сжатия и сделать вывод.
V. Подведение итогов урока
Формулировка выводов об эффективности и применении алгоритмов сжатия
текстовой информации.
Выставление оценок за работу на уроке.
Задание на дом (дифференцированно).
СПИСОК ЛИТЕРАТУРЫ
1. Информатика и ИКТ. 11 класс : учеб. Для общеобразовательных
учреждений : базовый и профил. Уровни / А.Г. Гейн, А.И. Сенокосов. – М. :
Просвещение, 2009.
Скачать материал

Информатика - еще материалы к урокам: