ГДЗ по информатике, 10 класс, Босова, номер 4.8: Обработка информации

Даны коды для пяти букв латинского алфавита:

• A→000
• B→01
• C→10
• D→11
• E→001

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

Обратим внимание на следующие пары:

• Код B=01. Он является началом кода A=000? Нет (01≠00…). Является ли он началом E=001? Нет.
• Код E=001. Он начинается с 00, что является началом A=000. Если мы видим последовательность 0001, её можно прочитать как A(000)+? или ?+E(001)? Нет, 0001 нельзя разбить на E+..., так как E заканчивается на 1, а перед ним должно быть 00. Но 000 — это A. А если взять первые три бита 000, это A. Остается 1. Код 1 не существует. Значит, 0001 само по себе не декодируется, но в составе длинной строки важно следить за границами.
• Важный момент: код A=000 и код E=001 имеют общий префикс 00. Также код B=01 и код C=10 короткие.

Давайте попробуем декодировать каждую из предложенных последовательностей слева направо, выбирая единственный возможный вариант на каждом шаге. Если на каком-то этапе возникает развилка (можно выбрать два разных кода), то такое сообщение может содержать ошибку или быть неоднозначным. Однако задача просит найти единственное сообщение без ошибки среди четырех. Это значит, что три других либо содержат несуществующие комбинации, либо декодируются неоднозначно/невозможны при строгом следовании правилам, либо просто «битые».

Будем использовать алгоритм жадного декодирования с проверкой всех возможных путей, если они есть. Но сначала посмотрим на структуру кодов:

Заметим, что все коды начинаются либо с 0, либо с 1. Если первый бит 1, то возможны только C(10) или D(11). Второй бит определяет выбор: - 10→C - 11→D Таким образом, подпоследовательности, начинающиеся с 1, декодируются однозначно парами битов.

Если первый бит 0, то возможны A(000), B(01), E(001). - Если второй бит 1, то это обязательно B(01), так как A и E начинаются с 00. - Если второй бит 0, то у нас есть префикс 00. Теперь смотрим на третий бит: - Если третий бит 0, то это A(000). - Если третий бит 1, то это E(001). Таким образом, система кодов является префиксным кодом (ни один код не является началом другого)? Проверим: - B=01 не является началом A=000 или E=001. - C=10 не является началом D=11. - A=000 не является началом E=001 (различаются в 3-м бите). - E=001 не является началом A=000. Да, это префиксный код! Следовательно, любое корректное сообщение декодируется однозначно . Ошибка в условии задачи может заключаться в том, что одна из последовательностей содержит комбинацию битов, которая не соответствует ни одному коду, или же вопрос в другом: возможно, некоторые последовательности невозможно полностью разложить на эти коды (останется «хвост», который не образует кода).

Поэтому стратегия решения: попытаться декодировать каждую последовательность до конца. Та, которая декодируется полностью и корректно, и будет ответом. Те, где в конце останутся лишние биты или возникнет невозможная комбинация, считаются ошибочными.

Последовательность: 110100000100110011

Разобьем на блоки, используя правила: 1. Начинается с 1. Смотрим второй бит: 1. Пара 11→D. Остаток: 0100000100110011. 2. Начинается с 0. Смотрим второй бит: 1. Пара 01→B. Остаток: 00000100110011. 3. Начинается с 0. Второй бит 0. Третий бит 0. Триплет 000→A. Остаток: 00100110011. 4. Начинается с 0. Второй бит 0. Третий бит 1. Триплет 001→E. Остаток: 00110011. 5. Начинается с 0. Второй бит 0. Третий бит 1. Триплет 001→E. Остаток: 10011. 6. Начинается с 1. Второй бит 0. Пара 10→C. Остаток: 011. 7. Начинается с 0. Второй бит 1. Пара 01→B. Остаток: 1. 8. Остался одиночный бит 1. Ни один код не состоит из одного бита. Коды C и D требуют двух битов (10,11). У нас нет следующего бита.

Вывод: Последовательность 1) не декодируется полностью, остается «хвост». Считаем её ошибочной.

Последовательность: 111010000010010011

Разобьем на блоки: 1. 11→D. Остаток: 1010000010010011. 2. 10→C. Остаток: 10000010010011. 3. 10→C. Остаток: 0000010010011. 4. 000→A. Остаток: 0010010011. 5. 001→E. Остаток: 0010011. 6. 001→E. Остаток: 0011. 7. 001→E. Остаток: 1. 8. Остался бит 1. Как и в предыдущем случае, одиночная 1 не образует кода.

Вывод: Последовательность 2) не декодируется полностью. Считаем её ошибочной.

Последовательность: 110100001001100111

Разобьем на блоки: 1. 11→D. Остаток: 0100001001100111. 2. 01→B. Остаток: 00001001100111. 3. 000→A. Остаток: 01001100111. 4. 01→B. Остаток: 001100111. 5. 001→E. Остаток: 100111. 6. 10→C. Остаток: 0111. 7. 01→B. Остаток: 11. 8. 11→D. Остаток пуст.

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

Расшифрованное слово: D-B-A-B-E-C-B-D.

Вывод: Последовательность 3) декодируется корректно и полностью.

Для полноты картины проверим и четвертую последовательность.

Последовательность: 110110000100110010

Разобьем на блоки: 1. 11→D. Остаток: 0110000100110010. 2. 01→B. Остаток: 10000100110010. 3. 10→C. Остаток: 000100110010. 4. 000→A. Остаток: 100110010. 5. 10→C. Остаток: 0110010. 6. 01→B. Остаток: 10010. 7. 10→C. Остаток: 010. 8. 01→B. Остаток: 0. 9. Остался бит 0. Ни один код не начинается с одиночного 0 без продолжения (коды A,B,E требуют минимум 2-3 бита). 0 сам по себе не является кодом.

Вывод: Последовательность 4) не декодируется полностью.