Ошибка.
Попробуйте повторить позже
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж, З, И, К. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 001, Б — 010, В — 1000, Г — 1001, Д — 11, Е — 0110.
Какое наименьшее количество двоичных знаков потребуется для кодирования четырёх оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: Ж, З, И, К.
Построим дерево Фано для известных букв. У нас остается 3 свободных ветви: 101, 0111 и 000. Но оставшихся букв
четыре: Ж, З, И, К. Значит, продлим ветвь минимальной длины, например, код 000 представим в виде 0000
и 0001. Теперь все буквы заполнены кодами. Итоговая длина кодов оставшихся четырех букв равна:
.
Ошибка.
Попробуйте повторить позже
Для кодирования некоторой последовательности, состоящей из букв A, B, C, D, E, F, решили использовать неравномерный двоичный код, для которого выполняется условие Фано. Для букв A и B было решено использовать коды 100 и 11 соответственно. Какова минимальная общая длина кодовых слов для всех шести букв?
Расширяем ветки до тех пор, пока не получится 6 кодовых слов.
Получаем сумму 3+3+2+3+3+2=16.
Ошибка.
Попробуйте повторить позже
Для кодирования некоторой последовательности, состоящей из букв A, B, C, D, E, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. При этом, в последовательности буква A встречается 70 раз, буква B - 60 раз, буква C - 50 раз, буква D - 45 раз, и буква E - 30 раз. Какова минимальная общая длина кодовых слов для всех пяти букв, при условии, что с этими кодами удалось получить кратчайшую длину всей последовательности?
Расширяем ветки до тех пор, пока не получится 5 кодовых слов.
Итого, получается сумма 3+3+2+2+2=12.
Ошибка.
Попробуйте повторить позже
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, К, О, Т, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А - 101, О - 11, Я - 011. Какое наименьшее количество двоичных знаков потребуется для кодирования слова КАТОК?
Нарисуем дерево Фано. Свободными кодами окажутся: 00, 010 и 100. Так как нам нужно закодировать еще 4 буквы, а кодов всего 3, то необходимо одну из ветвей раздвоить. Перед этим поймем какие буквы нам осталось закодировать и как часто они встречаются в требуемой последовательности.
Б - не встречается, К - встречается дважды, Т - встречается один раз, Р - не встречается.
Тогда, чтобы длина кода для слова КАТОК была минимальной, нужно присвоить букве К код 00, букве Т любой из оставшихся, а последний код раздвоить и присвоить полученное оставшимся буквам.
Тогда получаем 
.
Ошибка.
Попробуйте повторить позже
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж, решили использовать неравномерный двоичный код, удовлетворяющий условию, что никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для буквы А использовали кодовое слово 10; для буквы Б — кодовое слово 01. Какова наименьшая возможная сумма длин всех семи кодовых слов?
После составления дерева Фано остается 2 свободных листа: 00 и 11, а букв которые нужно закодировать остается 5. Можно пойти по 2 путям:
1) оба листа раздвоить, получим 4 свободных позиции и один из них еще раздвоить, получим 5 свободных позиций;
2) одному из листов присвоить букву, а второй раздвоить и каждый из полученных листов тоже раздвоить.
При первой схеме длина всех кодовых слов равна 
.
При второй длина всех кодовых слов равна 
.
Следовательно выбираем первую стратегию, наименьшая возможная сумма длин всех семи кодовых слов это 21.
Ошибка.
Попробуйте повторить позже
По каналу связи передаются сообщения, содержащие только буквы Е, Ж, К, Й, О, Ф. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для букв известны: К: 00; Ж: 111; О: 100; Ф: 101.
Укажите наименьшую возможную длину закодированной последовательности для слова ЖОКЕЙ.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
После построения дерева Фано можно заметить, что минимальными кодами, при которых не нарушится условие Фано, являются 01 и 110. Так как все буквы в слове ЖОКЕЙ повторяются одинаковое количество раз, то нам неважно, какой букве присваивать код. Пусть буква Е имеет код 01, буква Й - 110.
Тогда, длина последовательности равна 
Ошибка.
Попробуйте повторить позже
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, В, Д, Е, И, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 110, Б – 01, И – 000. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ВВЕДЕНИЕ?
Примечание: условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
После построения дерева Фано можно заметить, что свободными остаются ветви 111, 10 и 001. Однако, у нас остались
незакодированными 4 буквы - В, Д, Е, Н, т.е. четыре буквы. Так как буква Е встречается в слове 3 раза, то присвоим
ей код длины 2. Буква В встречается в слове 2 раза - ей присвоим код длины 3. Продолжим ветвь 001 до 0010 и 0011.
Тогда буквы Д и Н будут закодированы кодами длиной 4. Тогда итоговая длина всех семи кодовых слов равна:
Ошибка.
Попробуйте повторить позже
По каналу связи передаются сообщения, содержащие только пять букв: А, М, П, Е, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы М используется кодовое слово 1; для буквы Р используется кодовое слово 01.
Какова минимальная общая длина кодовых слов для всех пяти букв?
Примечание: условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Построим дерево фано, на нем видно, что свободный лист только один, а букв закодировать необходимо еще 3, поэтому пустим ветки из этого листа. Теперь имеется 2 свободных позиции, этого не достаточно, поэтому из любого листа пустим еще 2 ветки, теперь есть 3 свободных позиции.
Не важно каким образом мы расставим буквы на свободные позиции, так как от этого сумма длин кодов не изменится: 1+2+3+4+4 = 14.
Ошибка.
Попробуйте повторить позже
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 01, для буквы Б – кодовое слово 1011. Какова наименьшая возможная суммарная длина всех пяти кодовых слов? Примечание: условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Построим дерево Фано:
Свободными остаются листья с кодами 00, 11 и 100. Тогда, итоговая длина всех пяти кодовых слов равна:
.
Ошибка.
Попробуйте повторить позже
По каналу связи передаются сообщения, содержашие только шесть букв: М, О, Щ, Н, Ы, Й. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы Й используется кодововое слово 01; для буквы О используется кодовое слово 10.
Какова минимальная общая длина кодовых слов для всех шести букв?
Построим деревья для значений 0 и 1. Как мы знаем, Й это 01, а О это 10. Построим продолжения для значений 00 и 11.
Мы получили значения 000,001,110,111. Каждой оставшейся букве присвоим одно из кодовых слов.
Минимальная длина для всех шести букв будет равна: 
. Ответ: 16.
Ошибка.
Попробуйте повторить позже
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано; для букв A, Б, В используются такие кодовые слова: А — 0, Б — 101, В — 110.
Какова наименьшая возможная суммарная длина всех кодовых слов?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.
Нам уже известны длины букв А, Б и В, теперь необходимо подобрать кодовые слова для Г, Д, Е. У нас имеется два
свободных кодовых слова — 100 и 111. Так как нужно закодировать три буквы, нужно три свободных кодовых слова.
Для этого добавляем разряд в любое из них и получаем два кодовых слова с длиной 4. Таким образом, для Г мы
можем взять кодовое слово 100, для Д — 1110, а для Е — 1111. Складываем длины имеющихся слов и получаем ответ:
Ошибка.
Попробуйте повторить позже
По каналу связи передаются сообщения, содержащие только пять букв: Ш, К, О, Л, А. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы О используется кодовое слово 0; для буквы А используется кодовое слово 10.
Какова минимальная общая длина кодовых слов для всех пяти букв?
Примечание: условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Так как нужно закодировать три оставшиеся буквы, нам необходимо подобрать три кодовых слова. Для буквы Ш мы можем взять кодовое слово 110, для К – 1110, а для Л – 1111.
Складываем длины имеющихся слов и получаем ответ: 1+2+3+4+4 = 14
Ошибка.
Попробуйте повторить позже
По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А – 11, B – 101, C – 0. Какова наименьшая возможная суммарная длина всех кодовых слов?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.
Найдём кодовые слова для букв D, E, F. Мы не можем брать слова, начинающиеся с нуля, так как это кодовое слово занято буквой С, поэтому рассмотрим слова, начинающиеся с единицы. Нам нужно добавить разряд в свободное кодовое слово — 100. Добавляем и получаем два свободных кодовых слова — 1000 и 1001. Так как нам нужно закодировать три буквы, то необходимо увеличить количество разрядов в одном из чисел. Соответственно, для буквы D возьмём кодовое слово 1000, для E — 10010, а для F — 10011.
Складываем длины имеющихся слов и получаем ответ: 
.
Ошибка.
Попробуйте повторить позже
По каналу связи передаются сообщения, содержащие только буквы слова М А Н Г. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы М используется кодовое слово 00; для буквы Н используется кодовое слово 1.
Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАНГА?
Примечание: условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Построим дерево Фано, из которого очевидно, что свободное место только одно – 01. Но нам нужно закодировать ещё две буквы, А и Г, поэтому пустим ветки из этого места. Теперь имеется 2 свободных позиции, нам не важно каким образом мы расставим буквы на свободные позиции, так как от этого сумма длин кодов не изменится: 2+3+1+3+3 = 12.
Ошибка.
Попробуйте повторить позже
По каналу связи передаются сообщения, содержащие только восемь букв: А, В, И, Н, Р, Т, У, Ф. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: В – 010, Н – 00, Т – 101. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ФАРТУНА?
Построим дерево Фано и увидим, что есть три свободные ветки – 11, 100 и 011. Нам нужно найти кодовые слова для четырёх букв - Ф, А, Р, У. Причём буква А встречается в слове ФАРТУНА дважды. Продлим ветвь 11 и любую из ветвей 100 или 011. Букве А присвоим код длины 3, букве Ф – длины 3, букве Р – длины 4 и букве У – длины 3.
Общая длина последовательности ФАРТУНА: 
.
Ошибка.
Попробуйте повторить позже
Для кодирования некоторой последовательности, состоящей из букв К, Е, Ш, А решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Е использовали кодовое слово 0, для буквы К – кодовое слово 10. Какова наименьшая возможная суммарная длина всех четырех кодовых слов?
Нарисуем дерево. Заметим, что веточки 0 и 10 уже заняты буквами Е и К, тогда остается только одна свободная ветка
— 11. Так как нам нужно разместить еще две буквы, то продлеваем эту ветку до 110 и 111. Присвоим букве
Ш код 110, а букве А — 111. Тогда минимальная суммарная длина этих четырех кодовых слов равна:
.
Ошибка.
Попробуйте повторить позже
По каналу связи передаются сообщения, содержащие только пять букв: П, И, Л, О, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы И используется кодовое слово 1; для буквы О используется кодовое слово 01.
Какова минимальная общая длина кодовых слов для всех пяти букв?
Примечание: условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Построим дерево фано, на нем видно, что свободный лист только один, а букв закодировать необходимо еще 3, поэтому пустим ветки из этого листа. Теперь имеется 2 свободных позиции, этого не достаточно, поэтому из любого листа пустим еще 2 ветки, теперь есть 3 свободных позиции.
Не важно каким образом мы расставим буквы на свободные позиции, так как от этого сумма длин кодов не
изменится: 
.
Ошибка.
Попробуйте повторить позже
По каналу связи передаются сообщения, содержащие только восемь букв: А, В, Е, З, И, Н, О, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 101, В — 010, И — 00. Какое наименьшее количество двоичных знаков потребуется для кодирования слова НЕВЕЗЕНИЕ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Построим дерево Фано:
Остается 3 свободных листа. В лист, у которого код имеет длину 2 запишем букву Е, так как она в искомом слове встречается четыре раза. Букву Н запишем в любой оставшийся лист с длиной кода 3, так как она встречается в слове дважды. Из оставшегося листа необходимо отвести 2 ветки, чтобы иметь возможность закодировать все оставшиеся буквы, а в один из листов с длиной кода 4 запишем букву З.
Тогда итоговая длина двоичного кода будет: 
.
Ошибка.
Попробуйте повторить позже
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 00, Г — 101. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ГРАММ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Построим дерево фано:
Остается 3 свободных листа. В лист, у которого код имеет длину 2 запишем букву М, так как она в искомом слове встречается дважды. Букву Р запишем в любой оставшийся лист с длиной кода 3.
Тогда итоговая длина двоичного кода будет: 3+3+3+2+2 = 13.
Ошибка.
Попробуйте повторить позже
Для кодирования последовательности, состоящей из букв слова ШKOЛKOВО решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Ш использовали кодовое слово 00, для буквы К — 1. Укажите, какова наименьшая длина всех символов заданного слова.
Построим дерево для решения задачи. Для букв Ш и К есть кодовые слова 00 и 1 соответственно. В слове ШКОЛКОВО самая частовстречаемая буква — О, следовательно, её нужно закодировать минимальновозможным количеством символов.
Минимально возможная длина кодового слова для буквы состоит из трёх битов, то есть О закодируем с помощью 010.
Буквы Л и В встречаются всего один раз, закодируем их минимально возможным количеством символов.
Самая маленькая длина кодовых слов для них 
: 0110 и 0111.
Посчитаем сумму длин кодовых слов:
Ш, Л и В встречаются один раз,
К — 2 раза,
О — 3 раза.
.png)
