Прежде чем продемонстрировать решение двух этих заданий давайте рассмотрим немного теории (без нее никуда)
Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило преобразования информации к такому представлению называется кодом.
Кодирование бывает равномерным и неравномерным:
- при равномерном кодировании всем символам соответствуют коды одинаковой длины;
- при неравномерном кодировании разным символам соответствуют коды разной длины, это затрудняет декодирование.
Пример: Зашифруем буквы А, Б, В, Г при помощи двоичного кодирования равномерным кодом и посчитаем количество возможных сообщений:
Таким образом, мы получили равномерный код, т.к. длина каждого кодового слова одинакова для всех кодов (2).
Основные термины которые вы можете встретить при решении задания номер 4
Для решения задач с декодированием, необходимо знать, что такое условие Фано:
Условие Фано: ни одно кодовое слово не должно являться началом другого кодового слова (что обеспечивает однозначное декодирование сообщений с начала)
Также в некоторых задачах может встретиться обратное условие Фано, при котором сообщение декодируется с конца:
Обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова
Префиксный код — это код, в котором ни одно кодовое слово не совпадает с началом другого кодового слова. Сообщения при использовании такого кода декодируются однозначно.
Постфиксный код — это код, в котором ни одно кодовое слово не совпадает с концом другого кодового слова. Сообщения при использовании такого кода декодируются однозначно и только с конца.
Устали от теории? Давайте на примере!
Однозначное декодирование обеспечивается:
Думаю условие фано вы поняли, давайте переходить к заданиям из самого ЕГЭ
4 задание бывает в основном четырех типов:
1) Первый тип "Выбор кода при неиспользуемых сигналах":
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 011, Г — 100. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Решение:
Для решение данного типа задание самым правильным способом будет нарисовать у себя на листочке двоичное дерево как на рисунке выше и заполнить его уже известными значениями. Строится оно довольно просто. Слева нули ,справа единички и так из всех вершин. В данной задаче получится что-то подобное:
Далее нам нужно расставить все оставшиеся буквы по листьям так, чтобы буквы кодировались наименьшим количеством знаков и не нарушали условия Фано. В нашем случае нам осталось закодировать 3 буквы (М, И, Я). Частой ошибкой в подобной задаче является выбор более длинных ветвей. Здесь у нас есть две ветви длинной в 2 знака и одна (соседняя с Г) длиной 3. В слове МАГИЯ все символы встречаются одинаковое количество раз , поэтому не важно какую именно букву мы выберем для конкретного кода, но в других задачах обязательно обращайте на это внимание! По итогу распределения у нас получится полностью заполненное дерево:
Ну и последним действием нам нужно посчитать длину закодированного слова. МАГИЯ - 0001010011101
М А Г И Я
Ответ: Длина 13 символов, что и является ответом на данную задачу
Надеюсь вы не сильно устали при прочтении данной статьи и она была для вас полезной. В следующих статьях мы рассмотрим остальные типы данного задания и перейдем к более сложному заданию по системам счисления, спасибо за внимание и удачи!
Ссылка на следующую статью:
#егэ #информатика #егэ по информатике #программирование