4.02 Выбор кода для конкретной буквы
Ошибка.
Попробуйте повторить позже
По информационному каналу передаются сообщения, которые содержат буквы 
Для передачи
используется двочиный код, допускающий однозначное декодирование. Для букв 
используются
кодоые слова: 
— 
— 
— 
Укажите кратчайшее кодовое слово для буквы 
при котором код будет допускать однозначное
декодирование.
Если таких кодов несколько, укажите код с наименьшим числовым значением.
Требуется подобрать кратчайший код с наименьшим числовым значением,который будет удовлетворять кодировке, то есть будет однозначно декодироваться (распознаваться).
Начнём перебирать коды с минимально возможного, т.е. с кода длиной 
Таких кода два: 
и
С 
код начинаться может, так как в таком случае будет игнорироваться условие однозначности
декодирования, ведь коды для букв 
начинаются с 
С 
код может начинаться,ведь никакой иной код с данного символа не начинается.
Значит кратчайшее кодовое слово для B состоит из одного символа — 
Ошибка.
Попробуйте повторить позже
Крабозавр закодировал буквы Ч, А, Й равномерным двоичным кодом. Известно, что буквам Ч, А соответствуют кодовые слова 0010, 1101. Также известно, что кодовые слова отличаются минимум двумя знаками. Найдите кодовое слово для буквы Й, при условии, что оно начинается и заканчивается 1.
Так как оно начинается и заканчивается единицей - оно уже отличается от кодового слова Ч на 2 знака. Чтобы оно отличалось от кодового слова буквы А на 2 знака, достаточно поменять 10 на 01 в середине слова.
Ошибка.
Попробуйте повторить позже
Для кодирования некоторой последовательности, состоящей из букв Б, А, Р, С, У, Ч, О, К, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв Б, А, Р, С, У, Ч использовали соответственно кодовые слова 11, 0010, 100, 0011, 01, 000. Укажите кратчайшее возможное кодовое слово для буквы О, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажит код с наименьшим числовым значением.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Единственное доступное значение, удовлетворяющее условию Фано, является 101. Но, кроме буквы О нам нужно закодировать букву К. Поэтому, значений требуется два. Возьмём следующие по величине значения - 1010 и 1011. Наименьшее из них 1010, значит его мы и присвоим букве О.
Ошибка.
Попробуйте повторить позже
Школьник шифрует слова. По каналу связи передаются сообщения, содержащие только заглавные латинские буквы. Для передачи используется двоичный код, удовлетворяющий прямому условию Фано. Кодовые слова для некоторых букв известны: A - 111, B - 0110, C - 101, D - 00, E - 010, F - 1000. Укажите кратчайшее возможное кодовое слово для буквы Z. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание: условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Если мы построим дерево Фано, можно заметить, что единственная свободная ветвь длины 3 равна коду 110. Остальные свободные ветви имеют длины 4 и выше. Значит, букве Z нужно присвоить код 110.
Ошибка.
Попробуйте повторить позже
Житель страны «МАШИНА» Егор шифрует слова. По каналу связи передаются сообщения, содержащие только заглавные латинские буквы. Для передачи используется двоичный код, удовлетворяющий прямому условию Фано. Кодовые слова для некоторых букв известны: M – 001, N – 010, P – 1000, Q – 1001, O – 111, R – 0110.
Укажите кратчайшее возможное кодовое слово для буквы W. Если таких кодов несколько, укажите код с наибольшим числовым значением.
Примечание. Прямое условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Чтобы решить задачу, нам следует определить возможное положение кода, соответствующего букве ’W’, в дереве кодирования Фано.
В кодировании Фано, каждая буква представлена путём от корня дерева к одному из его листьев, где самый короткий путь соответствует кратчайшему коду.
Согласно принципу Фано, ни одно кодовое слово не может быть началом другого кодового слова. Это свойство сохраняется при представлении кодов в виде дерева, где каждый узел представляет собой бит (0 или 1), а каждый лист - букву. Следовательно, каждый путь от корня до листа представляет собой уникальный код для буквы.
После построения дерева можно заметить, что код 110 остается свободным. Так как он соответствует принципу Фано, то буква ’W’ может быть закодирована как 110. Ответ: 110.
Ошибка.
Попробуйте повторить позже
По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В используются такие кодовые слова: А – 10; Б – 110; В – 001. Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Рассмотрим различные варианты для буквы Г, начиная с самого меньшего:
Г - 0, условие Фано нарушается; аналогично и для Г - 00. Однако код 01 нам сразу же подойдёт. Кроме того он и будет являться наименьшим.
Ошибка.
Попробуйте повторить позже
Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, удовлетворяющим условию Фано. Кодовые слова для некоторых букв известны: А – 00, В – 010, Е – 011, К – 100, Я – 11. Укажите возможный код минимальной длины для буквы Ы. Если таких кодов несколько, укажите тот из них, который имеет минимальное числовое значение.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Если построить дерево Фано, можно заметить, что единственной свободной для буквы веткой является код 101. Но, так как кроме буквы Ы в алфавите есть и другие буквы, то нам нужно эту ветвь разделить на две, чтобы другим буквам также можно было присвоить код. После разделения получаем коды 1010 и 1011. Так как от нас требуется минимальное значение, то это код 1010.
Ошибка.
Попробуйте повторить позже
По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В используются такие кодовые слова: А - 0; Б - 110; В - 101. Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.
Построим дерево Фано и распределим известные буквы. Свободным остаются листья с кодами: 100 и 111. Так как требуется указать код с наибольшим числовым значением, то выберем 111.
Ошибка.
Попробуйте повторить позже
Для кодирования некоторой последовательности, состоящей из букв Б, А, Р, С, У, К решили использовать неравномерный двоичный код, допускающий однозначное декодирование. Известны коды для некоторых букв: Б — 10, А — 11, Р — 0010, С — 01, У — 0000. Укажите кратчайшее возможное кодовое слово для буквы К, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.
Построим дерево фано. У нас остались свободными листья с кодами 0001 и 0011. Так как эти коды имеют одинковую длину, то выбираем с наибольшим числовым значением, это 0011.
Ошибка.
Попробуйте повторить позже
По каналу связи передаются шифрованные сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж, З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А - 11, B - 101, Г - 00, Д - 011. Найдите код минимальной длины для буквы Б. Если таких кодов несколько, укажите код с минимальным числовым значением.
Примечание. условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Построив дерево Фано, можно увидеть что на 4 неизвестные буквы у нас остается 2 ветви наименьшей длины: 010 и 100. Так как нам нужно найти код минимальной длины, то для букв Е, Ж. З распишем ветвь 100 как 1001, 100010 и 100011. Теперь мы можем спокойно поставить букву Б на место кода 010 и он будет являться минимальным.
