Кодирование и условие Фано: ЕГЭ по информатике
Кодирование и условие фано
Примеры заданий с ответами
Карточки из тренажёра Focusy. Попробуйте ответить сами, потом откройте ответ.
Лёгкий уровень
Реши задачу
По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв Б, В, Г используются такие кодовые слова: Б – 101; В – 110; Г – 0.
Укажите кратчайшее кодовое слово для буквы А, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.
Примечание . Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
1111110100
Показать ответ
Ответ: 111
Двухбитные 10 и 11 — префиксы слов 101 и 110. Свободные трёхбитные слова: 100 и 111; наибольшее из них — 111.
Реши задачу
По каналу связи передаются шифрованные сообщения, содержащие только пять букв: А, Б, В, Г, Д. Для передачи используется неравномерный двоичный код. Для букв А, Б и В используются кодовые слова 1100, 1110, 11010 соответственно.
Укажите минимальную сумму длин кодовых слов для букв Г и Д, при котором код будет удовлетворять условию Фано.
Примечание . Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
5234
Показать ответ
Ответ: 3
Ветви 0 и 10 свободны: Г = 0, Д = 10 – сумма длин 3.
Реши задачу
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.
Буква
Кодовое слово
Буква
Кодовое слово
А
00
Л
1101
Б
1100
Р
1000
Е
010
С
1110
И
011
Т
1001
К
У
101
Укажите кратчайшее кодовое слово для буквы К, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код
с наименьшим числовым значением.
Примечание . Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
1111111101111111
Показать ответ
Ответ: 1111
Все коды длины ≤ 3 конфликтуют (111 – префикс 1110). Свободен только 1111.
Реши задачу
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.
Буква
Кодовое слово
Буква
Кодовое слово
А
00
Л
1101
Б
1100
Р
1000
Е
010
С
1110
И
011
Т
1001
К
1111
У
Укажите кратчайшее кодовое слово для буквы У, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код
с наименьшим числовым значением.
Примечание . Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
101101010011
Показать ответ
Ответ: 101
10 – префикс 1000, а 101 не является префиксом ни одного кода и сам не имеет префиксов – кратчайший код 101.
Средний уровень
Реши задачу
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.
А
000
Б
001
В
01
Г
11
Какое наименьшее количество двоичных знаков требуется для кодирования четырёх оставшихся букв?
В ответе запишите суммарную длину кодовых слов для букв: Д, Е, Ж, З.
Примечание . Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
17161512
Показать ответ
Ответ: 16
Свободна только ветвь 10. Четыре буквы под префиксом 10: 1000, 1001, 1010, 1011 – суммарно 16.
Реши задачу
По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В используются такие кодовые слова: А – 1010; Б – 1100;
В – 0.
Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.
Примечание . Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.
Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
111111010011
Показать ответ
Ответ: 111
Коды длины 1 и 2 – префиксы 1010 или 1100. Длины 3 подходят 100 и 111; наибольшее значение – 111.
Реши задачу
Для кодирования некоторой последовательности, состоящей из букв А, Б,
В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали кодовые слова 100, 101, 00, 01 соответственно. Для двух оставшихся букв –
Д и Е – коды неизвестны.
Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.
Примечание . Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
110111111111
Показать ответ
Ответ: 111
Свободна ветвь 11, но код 11 не оставит места для Е. Поэтому Д длины 3: 110 или 111; наибольший – 111.
Реши задачу
Для кодирования некоторой последовательности, состоящей из букв A , B , C , D , E , F , решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы A использовали кодовое слово 0; для буквы B – кодовое слово 10. Какова наименьшая возможная сумма длин кодовых слов для букв C , D , E , F ?
Примечание . Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
15161217
Показать ответ
Ответ: 16
Свободна ветвь 11: четыре кода 1100, 1101, 1110, 1111 – сумма 16.
Сложный уровень
Реши задачу
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.
Е
10
Ж
010
З
011
Д
11
Какое наименьшее количество двоичных знаков требуется для кодирования четырёх оставшихся букв?
В ответе запишите суммарную длину кодовых слов для букв: А, Б, В, Г.
Примечание . Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
8121614
Показать ответ
Ответ: 16
Свободен только префикс 00. Чтобы получить из него 4 кодовых слова без нарушения условия Фано, нужны 0000, 0001, 0010, 0011: суммарная длина 4·4=16.
Реши задачу
По каналу связи передаются шифрованные сообщения, содержащие только 10 букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.
Буква
Кодовое слово
Буква
Кодовое слово
А
00
Л
1101
Б
1100
Р
1010
Е
010
С
1110
И
011
Т
К
1111
У
100
Укажите кратчайшее кодовое слово для буквы Т, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание . Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
10111011111110
Показать ответ
Ответ: 1011
Трёхбуквенные 101 и 111 конфликтуют с Р=1010 и К=1111. Из четырёхбуквенных свободны 1011 и 1110, наименьшее — 1011.
Реши задачу
По каналу связи передаются шифрованные сообщения, содержащие только шесть букв: А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код. Для букв А, Б, В и Г используются кодовые слова 1, 00, 0100, 0111 соответственно.
Укажите минимальную сумму длин кодовых слов для букв Д и Е, при которых код будет удовлетворять условию Фано.
Примечание . Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
8697
Показать ответ
Ответ: 8
Свободны 0101 и 0110: 01 — префикс у В и Г, а 1 и 00 заняты. Более короткие слова невозможны, сумма 4+4=8.
Реши задачу
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.
Буква
Кодовое слово
Буква
Кодовое слово
А
00
Л
1001
Б
1000
Р
1110
Е
010
С
1010
И
011
Т
К
1011
У
110
Укажите кратчайшее кодовое слово для буквы Т, при котором код будет удовлетворять условию Фано. Если таких слов несколько, укажите код с наибольшим числовым значением.
Примечание . Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
101011011111111
Показать ответ
Ответ: 1111
Трёхбуквенные 101 и 111 — начала слов С, К (1010, 1011) и Р (1110). Из четырёхбуквенных свободно только 1111.
Частые вопросы
Как готовиться к теме «Кодирование и условие Фано»?
Понемногу и регулярно: 10 минут в день дают больше, чем один длинный вечер. В Focusy карточки с ошибками возвращаются на повторение через 1, 3, 7, 16, 35 и 90 дней, а в режиме «Теория» можно повторить правила и определения по темам.
Откуда задания для подготовки к ЕГЭ по информатике?
Карточки составлены по заданиям открытого банка ФИПИ и кодификатору ЕГЭ. Каждый ответ проверен дважды независимо, у карточек есть короткий разбор.
Можно ли тренироваться бесплатно?
Да. Focusy — бесплатный тренажёр в Telegram: короткие блоки заданий, разбор ошибок, статистика, серии дней и рейтинг.

