Алгоритмы сжатия. Алгоритм построения орграфа Хаффмана

Продолжительность учебного занятия: урок 45 минут

Тип учебного занятия: комбинированный (объяснение нового материала +практическая работа)

Цели (образовательная, развивающая, воспитательная) и задачи учебного занятия:

Образовательная:

1. Построить орграф Хаффмана.
2. Исследовать этот орграф Хаффмана.
3. Определить коэффициент сжатия.

Развивающая:

1. Развивать у учащихся познавательный интерес к курсу «Математические основы информатики».
2. Развивать алгоритмическое мышление, память.
3. Развитие практических навыков.

Воспитательная:

1. Способствовать воспитанию у учащихся внимательности.
2. Воспитывать аккуратность ведения записей в тетради.
3. Привитие навыка самостоятельности в работе.
4. Воспитание трудолюбия и чувства уважения к науке.

Оборудование: АРМ учителя, мультимедийный проектор, интерактивная доска.

Программное обеспечение: операционная система WinXP,  Microsoft Office, Smart Board.

Дидактические материалы к учебному занятию: мультимедийная презентация «Алгоритмы сжатия.  Алгоритм построения орграфа Хаффмана»,  конспект урока, опорный конспект.

Подготовка к уроку:  подбор материалов для теоретической информации, практической, подбор материалов для презентации, создание опорного конспекта.

Педагогическая технология:  урок-исследование/

Методы обучения:

1. Словесные (объяснение)
2. Наглядные (презентация)
3. Практические (упражнения)

Ключевые слова,  опорные понятия:  орграф, дуга (ветвь), корень,  дерево, орграф Хаффмана.

Ход учебного занятия:

1. Организация начала урока  (2 мин)
2. Подготовка учащихся к усвоению(5 мин)
3. Изучение нового материала (15 мин).
4. Закрепление  знаний (выполнение практической работы) (15мин)(в перерыве –физкультминутка)
5.  Подведение итогов урока. (3 мин)
6. Информация о домашнем задании (5 мин)

Формы: лекция, практикум

Ход урока:

1. Организация начала урока.

Приветствие учителя.

2. Подготовка учащихся к усвоению.

Повтор предыдущего урока.

Вопросы учащимся:

- дать определение префиксному коду;

- дать определение ориентированному графу (орграфу);

- дать определение корню (дереву);

-дать определение дуге (ветви).

3. Изучение нового материала (лекция).

Построить код Хаффмана для фразы «НА_ ДВОРЕ_ ТРАВА,_ НА_ ТРАВЕ_ ДРОВА». Определить коэффициент сжатия для данной фразы и  сравнить его, если каждый символ кодируется в ASCII.

Сжатие информации - проблема, имеющая достаточно давнюю историю, гораздо более давнюю, нежели история развития вычислительной техники, которая (история) обычно шла параллельно с историей развития проблемы кодирования и шифровки информации.

Все алгоритмы сжатия оперируют входным потоком информации, минимальной единицей которой является бит, а максимальной - несколько бит, байт или несколько байт.

Целью процесса сжатия, как правило, есть получение более компактного выходного потока информационных единиц из некоторого изначально некомпактного входного потока при помощи некоторого их преобразования.

Построение алгоритма Хаффмана.

Коды или Алгоритм Хаффмана (Huffman codes) — широко распространенный и очень эффективный метод сжатия данных, который, в зависимости от характеристик этих данных, обычно позволяет сэкономить от 20\% до 90\% объема.
Рассматриваются данные, представляющие собой последовательность символов. В  алгоритме Хаффмана используется таблица, содержащая частоты появления тех или иных символов.