Практическая работа "представление информации"

Класс: 7

Тема урока: Представление информации

Уровень: базовый

Планируемые образовательные результаты:

предметные – обобщённые представления о различных способах представления информации;

метапредметные – понимание общепредметной сущности понятия «знак»; общеучебные умения анализа, сравнения, классификации;

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

Задача

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А  — 010, Б  — 011, Г  — 100. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ? 

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Решение.

Следующая буква должна кодироваться как 11, поскольку 10 мы взять не можем. 100 взять не можем из-за Г, значит, следующая буква должна быть закодирована кодом 101. Следующая буква должна кодироваться как 000, поскольку 00 взять не можем, иначе не останется кодовых слов для оставшейся буквы, которые удовлетворяют условию Фано. Значит, последняя буква будет кодироваться как 001. Тогда наименьшее количество двоичных знаков, которые потребуются для кодирования слова МАГИЯ, равно 2 + 3 + 3 + 3 + 3  =  14.

 Ответ: 14.

 Примечание.

Заметим, что после кодирования всех букв, входящих в слово МАГИЯ, должен остаться хотя бы один свободный код для кодирования буквы Р, которая не входит в данное слово, но может передаваться по каналу связи. Проверить наличие свободного кода можно, построив дерево кодов.