Кодирование и условие Фано: ЕГЭ по информатике

Кодирование и условие фано

Тренировать в Focusy66 карточек · 3 уровня сложности

Примеры заданий с ответами

Карточки из тренажёра 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: короткие блоки заданий, разбор ошибок, статистика, серии дней и рейтинг.

Другие разделы ЕГЭ по информатике