Мастер-класс для педагогов на тему: «Сжатие информации»
материал по информатике и икт

Мастер-класс для педагогов.

Дата проведения:  22 ноября 2017 г.

Место проведения: ГУ ДПО «Институт развития образования Забайкальского края»,       г. Чита, каб. №1.

Проводит: Чупрова Н.П. – учитель информатики и математики

I квалификационной категории  МБОУ Шелопугинской СОШ.

Тема: «Сжатие информации»

Цель: познакомить педагогов с принципами сжатия текстовой информации для экономии и надежности при хранении и передаче.

Задачи:

• научиться сжимать текстовую информацию, используя префиксный код Шеннона-Фано;
• развивать логику мышления, интерес к познавательной деятельности, творческую инициативу и активность;
• воспитывать трудолюбие, самостоятельность, навыки организации рабочего места.

Ход мастер-класса.

1.Вступительная часть.

- Скажите, пожалуйста, какие фразы или слова мы употребляем каждый день и очень часто. (Добрый день, здравствуйте, Доброе утро, как дела? и т.д.)

- Спасибо большое за сказанное, запомните эти варианты слов, они нам дальше пригодятся.

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

- То, что я вам показала, попробуйте перевести, используя  «язык» информатики.

Тема моего мастер класса «Сжатие информации». Принцип сжатия информации: чем чаще встречается эта информация, тем короче она должна быть.

Вспомните слова, которые вы перед этим проговаривали:  Добрый день, Здравствуйте, Доброе утро, Как дела? и т.д.

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

2. Теоретическо - демонстрационная часть.

Рассмотрим, например, русскую скороговорку:

Проворонила ворона вороненка.

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

Ну, а мы с вами используем этот прием, чтобы эту скороговорку хорошо сжать.

Какие буквы встречаются здесь наиболее часто?

Всего: 28 символов. А это значит, что если мы будем хранить их в памяти компьютера, то в лучшем случае она займет 28 байт или 224 бита.

Сейчас мы будем сжимать текст по одному из существующему методу - метод Шеннона-Фано.

Это один из первых алгоритмов сжатия, который впервые сформулировали американские ученые Клод Шеннон и Роберт Фано. Данный метод сжатия имеет большое сходство с алгоритмом Хаффмана, который появился на несколько лет позже и является логическим продолжением алгоритма Шеннона.

Код Шеннона — Фано строится с помощью дерева. Построение этого дерева начинается от корня. Всё множество кодируемых элементов соответствует корню дерева (вершине первого уровня). Оно разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Эти подмножества соответствуют двум вершинам второго уровня, которые соединяются с корнем.

Далее каждое из этих подмножеств разбивается на два подмножества с близко одинаковым суммарным числом появлений. Подобным образом поступаем до тех пор, пока не получим все концевые вершины. Ветви кодового дерева размечаем символами 1 и 0, как в случае кода Хаффмана.

Разделяем линиями разной длины, 1 самая длинная, 2 – по короче и т.д., это связано с тем, что если запись повернуть, то образуется бинарное дерево.

1. Считаем  каждую букву и записываем, сколько раз повторяется:

2. Выстраиваем по убыванию количества:

3. Делим на две части, чтобы суммы повторов были приблизительно одинаковые.

28 символов = 28 байт = 224 бита

После сжатия:

7*2 + 4*3 + 4*3 + 3*3 + 3*3 + 2*4 + 4*5 + 1*4 = 14 + 12 + 12 + 9 + 9 + 8 + 20 + 4 = =88 бит

k (коэффициент сжатия) = 88/224*100% ~ 39%

Применение:

ЕГЭ по информатике

Задание 5 № 9185

Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К – кодовое слово 10. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Пояснение.

Нельзя использовать кодовые слова, которые начинаются с 0 или с 10. 11 также не можем использовать, поскольку тогда мы больше не сможем взять никакое другое кодовое слово, а нам их нужно пять. Поэтому берём трёхзначное 110. 111 опять же не можем использовать, потому что понадобиться ещё одно кодовое слово, а вместе с этим не останется больше свободных. Теперь осталось взять всего два слова и это будут 1110 и 1111. Итого имеем 0, 10, 110, 1110 и 1111 — 14 символов.

3. Практическая часть.

Выполнить самостоятельно по группам:

Постройте код Шеннона-Фано для фраз и сравните объем информации до и после сжатия.

1. Мама_мыла_раму
2. ШЛА_САША_ПО_ШОССЕ_И СОСАЛА_СУШКУ
3. А_роза_упала_на_лапу_азора
4. НА_ ДВОРЕ_ ТРАВА_ НА_ ТРАВЕ_ ДРОВА

Ответ:

4. Подведение итогов.

        Я считаю,  что человека ничему нельзя научить, можно только помочь ему раскрыться, показать ему его внутренние силы и возможности  и только тогда он научит себя всему сам. Когда мы начинаем какое-то дело, то должны представить результат, который хотим получить. Не для школы, для жизни учимся. Спасибо.

Самоанализ мастер-класса

проведенного Чупровой Ниной Павловной

 для педагогов информатики 22.11.2017 г.

на тему: «Сжатие информации»

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

Поставленные задачи были выполнены полностью. Были рассмотрены основные этапы работы над сжатием текста. Педагоги познакомились с приемом, помогающим сжимать текст по алгоритму Шеннона-Фано на примере скороговорки. Были созданы условия для участников мастер-класса для развития фантазии, творческого мышления, освоения выполнения сжатия текстовой информации.

Мастер-класс был проведен в форме лекции с элементами презентации плюс практическая работа с педагогами.

 Вступительная часть состояла из определения темы мастер-класса.

В теоритическо - демонстрационной части были рассмотрены этапы выполнения сжатия текстовой информации по алгоритму Шеннона-Фано, вычисление объема информации до сжатия и после сжатия.

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

В завершении был подведен итог, составлен алгоритм продуктивной творческой деятельности. Учителя сравнили объем информации до сжатия и после сжатия текста.

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

Чупрова Н.П.