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

Даны коды для первых трёх букв:

• А: 0
• Б: 10
• В: 110

Проверим их на префиксность. Код А (0) не является началом кода Б (10) или В (110). Код Б (10) не является началом кода В (110). Значит, эти три кода уже образуют корректный префиксный набор.

Рассмотрим структуру двоичного дерева, соответствующего этим кодам:

• Корень имеет две ветви: 0 и 1.
• Ветвь 0 занята буквой А. Это лист дерева.
• Ветвь 1 ведёт к следующему узлу. От этого узла идут ветви 10 и 11.
• Ветвь 10 занята буквой Б. Это лист дерева.
• Ветвь 11 ведёт к следующему узлу. От него идут ветви 110 и 111.
• Ветвь 110 занята буквой В. Это лист дерева.

Таким образом, в дереве заняты пути 0, 10 и 110. Свободными остаются ветви, исходящие из узлов, которые ещё не стали листьями, или новые уровни глубины.

Нам нужно добавить два новых кодовых слова для букв Г и Д так, чтобы они не конфликтовали с существующими (не были их продолжениями и не имели их как начало) и суммарная длина всех пяти кодов была минимальной.

Существующие длины: l(А)=1, l(Б)=2, l(В)=3. Сумма длин текущих трёх: 1+2+3=6.

Чтобы найти кратчайшие свободные коды, посмотрим на «свободные» места в дереве:

1. После кода 110 (В) следующий возможный короткий код в этой ветке — это 111. Длина 3.
2. Если мы возьмём код 111 для одной из букв (например, Г), то он станет листом. Тогда для последней буквы Д нам придётся искать место дальше.
3. Давайте проверим возможность использования кодов длины 3. У нас есть только один свободный путь длины 3: 111. Второй путь длины 3? Нет, все пути длины 3 начинаются с 0 или 1. - Начиная с 0: единственный путь 0... занят А (0). Любое расширение 00,01 будет иметь длину ≠3 или конфликтует? Нет, если А=0, то 00 и 01 невозможны, так как 0 уже является полным кодом. Поэтому подветви от А закрыты. - Начиная с 1: у нас есть 10 (Б) и 11.... От 11 идут 110 (В) и 111. Значит, единственный свободный код длины 3 — это 111.

Значит, одну букву (Г или Д) можно закодировать словом длины 3 (111).

Теперь найдём самый короткий свободный код для второй буквы (Д). После того как мы заняли 111, все пути длины 3 исчерпаны или заблокированы: - 0 (занято) - 10 (занято) - 110 (занято) - 111 (занято новой буквой)

Следующий уровень — длина 4. Посмотрим, какие коды длины 4 доступны. Они должны начинаться с незаблокированных префиксов. Но все префиксы длины 1,2,3 либо заняты, либо являются частью занятых кодов. Однако в префиксных кодах мы можем использовать любые последовательности, которые не являются продолжением существующих кодов и не содержат существующие коды как начало. Давайте перестроим логику через неравенство Крафта или просто перебор коротких комбинаций. Текущие коды: 0,10,110. Свободные окончания в дереве: - Из корня: ветвь 0 закрыта (лист). - Из корня: ветвь 1 открыта. - Из узла 1: ветвь 10 закрыта (лист). - Из узла 1: ветвь 11 открыта. - Из узла 11: ветвь 110 закрыта (лист). - Из узла 11: ветвь 111 открыта. Мы можем взять код 111 (длина 3). Теперь этот узел становится листом. Осталась одна буква. Где взять самый короткий код? Все пути длины 1, 2, 3 теперь либо заняты, либо проходят через занятые листья (что запрещено). Значит, нужно идти на глубину 4. Какие коды длины 4 возможны? Они должны быть «новыми ветвями», исходящими от узлов, которые ещё не стали листьями. Но в нашем случае после добавления 111 все узлы на глубине до 3 стали либо листьями, либо имеют потомков, которые тоже стали листьями/заняты. Подождите, давайте проверим альтернативу. Может быть, выгоднее не брать 111, а взять два кода длины 4? Или один длины 3 и один длины 4? Если берём 111 (дл. 3), то для последнего кода нужно выбрать любой доступный путь длины 4. Например, 1110 или 1111? Нет, если 111 стал кодом, то 1110 и 1111 запрещены, так как 111 является их префиксом. Значит, если мы используем 111, мы блокируем всё под ним. Тогда где взять последний код? Нужно вернуться к структуре дерева. Чтобы получить код длины 4, он должен исходить из узла, который не является листом. Но все узлы на глубине 0, 1, 2, 3 уже либо листья, либо имеют детей-листьев. Давайте посмотрим внимательнее. Коды 0,10,110 занимают определённые позиции. Оставшееся пространство для кодов должно удовлетворять условию префиксности. Сумма вероятностей (или весов) в неравенстве Крафта для двоичного кода: 1/2^l₁+1/2^l₂+...1/2^l_n1/2. Для 5 символов сумма должна быть 1/2. Имеющиеся: A(1),B(2),C(3). 1/2¹+1/2²+1/2³=1/2+1/4+1/8=7/8. Остаток для двух других кодов: 1-7/8=1/8. Нам нужно представить 1/8 в виде суммы двух дробей вида 1/2^k. Варианты: 1. 1/8=1/8+0? Нет, нужно два ненулевых кода. 2. Разложим 1/8 на два слагаемых степени двойки. Можно ли взять два кода длины 3? 1/8+1/8=2/8=1/4≠1/8. Не подходит. Нужно, чтобы сумма была ровно 1/8. Единственный способ разбить 1/8 на сумму двух обратных степеней двойки — это использовать более длинные коды. Например: 1/16+1/16=2/16=1/8. Это соответствует двум кодам длины 4. Другой вариант: 1/8 нельзя разбить на 1/2^a+1/2^b, где a,b<4, кроме случая, когда один из них равен 1/8, но тогда второго нет. Подождите, я ошибся в остатке? Неравенство Крафта для полного кода равно 1. Для префиксного кода сумма 1/2^l_i1/2. Текущая сумма: 0.5+0.25+0.125=0.875. Остаток: 1-0.875=0.125=1/8. Нам нужно добавить два кода, сумма весов которых равна 1/8. Вариант 1: Два кода длины 4. Вес каждого 1/16. Сумма 1/16+1/16=2/16=1/8. Подходит. Вариант 2: Один код длины 3 (1/8) и один код... нулевой длины? Нет. Если взять код длины 3, его вес 1/8. Тогда остаток 0. Но нам нужен ещё один символ. Значит, нельзя взять код длины 3, потому что он «заберёт» весь остаток, и для последнего символа не останется места в рамках префиксного кода без нарушения структуры (пришлось бы брать бесконечную длину или нарушить префиксность). Следовательно, единственное решение с минимальной суммарной длиной — это использование двух кодов длины 4. Почему нельзя было взять один длины 3 и один большей? Потому что если мы возьмём код длины 3 (например, 111), то его вес 1/8 полностью покрывает остаток. Но физически в дереве, если мы заняли 111, мы не можем создать другой код, не пересекающийся с ним, используя оставшуюся ёмкость? Давайте проверим геометрически. Если мы добавляем 111, то все пути, начинающиеся с 111, становятся недоступны. А другие пути? Все остальные пути длины 1, 2, 3 уже заняты (0,10,110). Значит, любой новый код должен иметь длину больше 3. Минимальная длина нового кода будет 4. Но если мы уже использовали 111, то код длины 4 должен быть, например, 1110? Нет, 111 — префикс 1110. Запрещено. Значит, если мы хотим использовать код длины 3, мы должны убедиться, что он не блокирует возможность создания другого кода. Но в данном случае, взяв 111, мы исчерпываем все возможности на уровне глубины 3. Следующий доступный код должен быть глубже. Но какой именно? Он должен быть в ветке, которая ещё не стала листом. Но все ветки глубины 3 стали листьями или заняты. Вернёмся к неравенству Крафта. Оно необходимое, но достаточное ли оно для существования кода? Да, для двоичных префиксных кодов. Если сумма весов равна 1, код существует. Если меньше 1, код неполный, но его можно дополнить. Здесь сумма весов имеющихся 3 кодов 7/8. Остаток 1/8. Нам нужно добавить 2 кода. Их веса w_1,w₂ должны в сумме давать 1/8. Чтобы минимизировать суммарную длину L=l₁+l₂+l₃+l₄+l₅, нам нужно минимизировать l₄+l₅ при условии 1/2^l₄+1/2^l₅=1/8. Переберём варианты: - Если l₄=3, то 1/8+1/2^l₅=1/8→1/2^l₅=0. Невозможно. - Если l₄=4, то 1/16+1/2^l₅=1/8=2/16→1/2^l₅=1/16→l₅=4. Сумма длин новых кодов: 4+4=8. - Если l₄=5, то 1/32+1/2^l₅=4/32→1/2^l₅=3/32. Не степень двойки. Невозможно. - Если l₄=6, то 1/64+1/2^l₅=8/64→1/2^l₅=7/64. Невозможно. Таким образом, единственное целочисленное решение для длин двух новых кодов — это 4 и 4.

Нам нужны два кода длины 4, которые не являются префиксами друг друга и не имеют префиксов среди 0,10,110. Существующие коды занимают пути: - 0 - 10 - 110 Свободные пути на уровне глубины 4: Рассмотрим ветвление от корня. 1. Ветвь 0 закрыта. 2. Ветвь 1 открыта. - Подветвь 10 закрыта. - Подветвь 11 открыта. - Подветвь 110 закрыта. - Подветвь 111 открыта. - От узла 111 идут ветви 1110 и 1111. Оба этих кода (1110 и 1111) имеют длину 4. Проверим условия: - Является ли 1110 префиксом какого-то существующего кода? Нет. - Является ли какой-то существующий код префиксом 1110? - 0? Нет. - 10? Нет. - 110? Нет (110≠111...). - Аналогично для 1111. - Являются ли 1110 и 1111 префиксами друг друга? Нет, они разной длины? Нет, одинаковой, но отличаются последним битом. Ни один не является началом другого. Таким образом, мы можем назначить: Г: 1110 Д: 1111 (Или наоборот, порядок букв не важен для минимальности суммарной длины).

Количество символов: 5. Длины кодов: - А: 1 - Б: 2 - В: 3 - Г: 4 - Д: 4 Суммарная длина: S=1+2+3+4+4=14. Можно ли получить меньшую сумму? Мы доказали через неравенство Крафта, что минимальная сумма длин двух дополнительных кодов при остатке 1/8 равна 4+4=8. Любая другая комбинация длин (l_4,l₅), дающая сумму весов 1/8, привела бы к большим длинам (например, 5 и ? невозможно, 6 и ? невозможно). Комбинация 3 и ? невозможна, так как требует нулевой длины для второго кода. Следовательно, минимальная суммарная длина действительно 14. Пример итогового набора кодов: А: 0 Б: 10 В: 110 Г: 1110 Д: 1111