Информатика Кодирование. Основные понятия. Закодировать текст значит сопоставить ему другой текст. Кодирование применяется при передаче данных для того, чтобы зашифровать текст от посторонних, чтобы сделать передачу данных более надежной, потому что канал передачи данных может передавать только ограниченный набор символов например, только два символа, 0 и 1 и по другим причинам. При кодировании заранее определяют алфавит, в котором записаны исходные тексты исходный алфавит и алфавит, в котором записаны закодированные тексты коды, этот алфавит называется кодовым алфавитом. В качестве кодового алфавита часто используют двоичный алфавит, состоящий из двух символов битов 0 и 1. Слова в двоичном алфавите иногда называют битовыми последовательностями. Побуквенное кодирование. Наиболее простой способ кодирования побуквенный. При побуквенном кодировании каждому символу из исходного алфавита сопоставляется кодовое слово слово в кодовом алфавите. Иногда вместо кодовое слово буквы говорят просто код буквы. При побуквенном кодировании текста коды всех символов записываются подряд, без разделителей. Пример 1. Исходный алфавит алфавит русских букв, строчные и прописные буквы не различаются. Размер алфавита 3. Кодовый алфавит алфавит десятичных цифр. Размер алфавита  1. Применяется побуквенное кодирование по следующему правилу буква кодируется ее номером в алфавите код буквы А 1 буквы Я 3. Тогда код слова АББА это 1. Внимание Последовательность 1. АББА, но и КУ К 1. У 2. 1 я буква. Про такой код говорят, что он НЕ допускает однозначного декодирования. Пример 2. Каждая буква также кодируется своим номером в алфавите, НО номер всегда записывается двумя цифрами к записи однозначных чисел слева добавляется 0. Например, код А 0. Б 0. 2 и т. д. В этом случае кодом текста АББА будет 0. И расшифровать этот код можно только одним способом. Иллюстрации К Сказке Царевна Лягушка далее. Для расшифровки достаточно разбить кодовый текст 0. Такой способ кодирования называется равномерным. Равномерное кодирование всегда допускает однозначное декодирование. Далее рассматривается только побуквенное кодирование 3. Русский Алфавит Двоичный Код' title='Русский Алфавит Двоичный Код' />Двоичный код каждого символа в компьютерном тексте занимает 1 байт памяти. Двоичный код каждого символа, выглядит восьмизначным числом, например. В основе текстов на русском языке лежит алфавит, называемый. Постройте неравномерный двоичный код, соблюдая условие Фано. Неравномерное кодирование. Равномерное кодирование удобно для декодирования. Однако часто применяют и неравномерные коды, т. Это полезно, когда в исходном тексте разные буквы встречаются с разной частотой. Тогда часто встречающиеся символы стоит кодировать более короткими словами, а редкие более длинными. Из примера 1 видно, что в отличие от равномерных кодов не все неравномерные коды допускают однозначное декодирование. Есть простое условие, при выполнении которого неравномерный код допускает однозначное декодирование. Код называется префиксным,  если в нем нет ни одного кодового слова, которое было бы началом по научному, префиксом другого кодового слова. Код из примера 1 НЕ префиксный, так как, например, код буквы А т. Informatika_8_72.jpg' alt='Русский Алфавит Двоичный Код' title='Русский Алфавит Двоичный Код' />Пусть исходный алфавит включает 9 символов А, Л, М, О, П, Р, У, Ы,. Кодовые слова А 0. М 0. 1 1. 00. Л 1. У 1. 10. Ы 1. 10. Р 1. 11. О 1. 11. П 1. Кодовые слова выписаны в алфавитном порядке. Видно, что ни одно из них не является началом другого. Это можно проиллюстрировать рисунком. На рисунке изображено бинарное дерево. Его корень расположен слева. Image1.gif' alt='Русский Алфавит Двоичный Код' title='Русский Алфавит Двоичный Код' />Из каждого внутреннего узла выходит два ребра. Верхнее ребро имеет пометку 0, нижнее пометку 1. Таким образом, каждому узлу соответствует слово в двоичном алфавите. Если слово X является началом префиксом слова Y, то узел, соответствующий слову X, находится на пути из корня в узел, соответствующий слову Y. Наши кодовые слова находятся в листьях дерева. Поэтому ни одно из них не является началом другого. Теорема условие Фано. Любой префиксный код а не только равномерный допускает однозначное декодирование. Разбор примера вместо доказательства. Русский Алфавит Двоичный Код' title='Русский Алфавит Двоичный Код' />Рассмотрим закодированный текст, полученный с помощью кода из примера 3 0. Будем его декодировать таким способом. Двигаемся слева направо, пока не обнаружим код какой то буквы. М. 0. 10. 00. 10. Значит, исходный текст начинается с буквы М код никакой другой буквы не начинается с 0. В расшифрованном тексте 1. Таким образом, при равномерном кодировании закодированный текст имел бы длину 5. Как все это повторять. Задачи на понимание. Знание приведенного выше материала достаточно для решения задачи 5 из демо варианта и близких к ней см. Повторять учить этот материал стоит в том порядке, в котором он изложен. При этом нужно решать простые задачи до тех пор, пока не будет достигнуто полное понимание. Ниже приведены возможные типы таких задач. Опытные учителя легко придумают или подберут конкретные задачи таких типов. Если будут вопросы пишите. Понятие побуквенного кодирования. Дан алфавит Ф и кодовые слова для всех слов в алфавите Ф. Закодировать заданный текст в алфавите Ф. Коды могут быть с использованием разных кодовых алфавитов, равномерные и неравномерные. Префиксные неравномерные коды. Дан алфавит Ф и двоичный префиксный код для этого алфавита. Построить дерево кода см. Декодировать анализом слева направо данный текст в кодовом алфавите. Дан алфавит Ф и кодовые слова для всех слов в алфавите Ф. Определить, является ли данный код префиксным, или нет. В качестве примеров полезно приводить                        Равномерный код. При анализе дополнительной буквы полезно использовать дерево исходного кода. Полезно рассмотреть различные варианты потери префиксности а новый код начало одного из старых б один из старых кодов начало нового.