Цель урока:
- повторить и обобщить понятие о кодировании текстовой информации.
Задачи урока:
- Повторить и обобщить понятие о кодировании текстовой информации
- На примерах показать использование кодирования в других предметных областях и в повседневной жизни
- Дать (хотя бы на интуитивном уровне) понятие «сжатие информации».
- Ознакомить учащихся с методом Шеннона-Фано.
- Межпредметные связи:
русский язык, математика
Ход урока
1. Организационный момент, проверка домашнего задания
2. Ознакомление учащихся с понятие «сжатие информации» на примерах (см. слайды №2 и №3).
Сжатие информации – это выбор или создание такого
способа ее записи, чтобы при хранении она требовала как можно меньше
места. В повседневной жизни или при изучении разных предметов мы активно
пользуемся этим приемом работы с информацией. Например, число можно
записать в виде текста, а можно – цифрами. Отдельные слова можно
сокращать, и таким образом запись текста станет короче. Из курса
истории, возможно, вам известно, что в древнерусских документах слова
писались без пробелов. Трудно сказать, почему так случилось, но можно
быть уверенными в том, что такая запись позволяет уместить немного
больше текста на странице. Во многих восточных языках присутствуют
иероглифы, которые заменяют при письме не отдельные буквы, а целые слова
или даже предложения. В математике применяются различные сокращения для
часто используемых слов «принадлежит», «существует», «параллельно»,
«больше», «меньше» и других.
Работа по карточкам (Приложение 1) –
учащимся предлагается
вспомнить какие способы сжатия текстовой информации они могли встречать
в младшей школе. Обращается внимание, что не всякое сжатие обратимо, то
есть не всегда возможно по сжатой информации восстановить ее оригинал.
3. Метод Шеннона-Фано (по презентации Приложение 2, см. слайды №№ 4-9)
Как мы уже видели при решении задач, информацию
нельзя сжимать до бесконечности. То есть в какой-то момент должна
появиться своего рода граница, при сжатии дальше которой восстановление
информации неоднозначно или просто невозможно. То есть хотелось бы,
чтобы выбранный нами способ кодирования был оптимальным: с одной
стороны, чтобы обеспечивалось максимально возможное сжатие, с другой
стороны, чтобы записанная таким образом информация не теряла свою
полноту. Одним из методов, обеспечивающих такое оптимальное кодирование
отдельных символов является метод Шеннона-Фано.
Суть метода состоит в следующем: пусть дан некоторый алфавит (конечный
набор символов, который будет использован для написания текста). Пусть
также дано сообщение. Какие-то символы в сообщении обычно встречаются
чаще, какие-то – реже. Для часто используемых символов создадим более
короткие коды, для реже используемых – длинные (слайд №4 – частота
использования букв русского языка).
Для начала, в качестве повторения, оценим (например, по формуле Хартли)
сколько бит необходимо отвести для записи кода одного символа, и
создадим «обычные» коды равной длины (слайд №5).
Теперь подсчитаем для каждого символа какую часть сообщения он занимает (проверка: сумма всех таких дробей должна быть равна единице – целому сообщению). Сведем наши данные в таблицу и упорядочим ее по убыванию долей (слайд №6).
Далее, разделим таблицу на две части, чтобы сумма
долей всех символов в одной была как можно ближе к сумме долей всех
символов другой. Пусть коды всех символов из первой части начинаются на
0, коды всех символов из второй – на 1 (слайд №7). Если в какой-то части
находится более одного символа, то повторим для нее процесс деления,
находя вторую, третью и так далее цифры кода. Как только для всех
символов найдены коды – процесс завершен (слайды №8 и №9)
Осталось только подчитать количество бит, которые необходимы для
представления сообщения в новом коде (слайд №10).
4. Закрепление пройденного материала, решение задач (слайд №11)
5. Подведение итогов урока