ЕГЭ · краткий ответ

Задание 4 ЕГЭ по информатике — кодирование и декодирование информации (условие Фано)

Что проверяет номер, типичные ошибки, пример с решением на Python и 10 заданий с ответами под спойлером.

67заданий в банке
с ответамикак в КИМ
1 кликзадание на доске

Что проверяет задание 4 ЕГЭ

Номер о неравномерных двоичных кодах. Чтобы сообщение можно было однозначно декодировать, код должен удовлетворять условию Фано: ни одно кодовое слово не является началом другого. Обычно известны коды части букв, а нужно подобрать самые короткие коды для остальных. Удобнее всего рисовать двоичное дерево: занятые коды — листья, свободные ветки — кандидаты.

КЕГЭ, задание 467 заданий в банке ИнфДоски

Типичные ошибки

  • Берут код, который сам является началом уже занятого кода (например, 0 при занятом 01).
  • Забывают, что новый код тоже не может начинаться с занятого кода.
  • Ищут минимальную длину одного кода, когда спрашивают суммарную длину нескольких.
  • Не проверяют, хватает ли свободных веток для всех оставшихся букв.

Пример с решением

Условие

Для кодирования букв А, Б, В, Г, Д, Е используется неравномерный двоичный код, удовлетворяющий условию Фано. Известны коды: А — 00, Б — 010, В — 011, Г — 10. Какова наименьшая возможная суммарная длина кодовых слов для букв Д и Е?

Решение

Строим дерево. Ветка 0 полностью занята (00, 010, 011). На ветке 1 занят код 10, свободна ветка 11. Двух букв в одну свободную ветку длины 2 не поместить: код 11 — только для одной буквы, тогда вторую ставить некуда. Делим 11 на 110 и 111: суммарная длина 3 + 3 = 6.

from itertools import product

known = ['00', '010', '011', '10']
words = [''.join(p) for n in range(1, 6) for p in product('01', repeat=n)]

def fano(codes):
    return len(set(codes)) == len(codes) and \
        all(not b.startswith(a) for a in codes for b in codes if a != b)

print(min(len(d) + len(e) for d in words for e in words if fano(known + [d, e])))
Код на Python 3 — его можно запустить прямо на ИнфДоске.
Ответ: 6

Задания из банка

В банке ИнфДоски 67 заданий этого номера. Ниже — 10 из них, ответ спрятан под спойлером. Кнопка «Открыть на доске» ставит задание на вашу ИнфДоску.

Задание 1 Кодирование информации Открыть на доске →

По каналу связи передаются сообщения, содержащие только четыре буквы: З, А, Р, Я; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв Я, Р, З используются такие кодовые слова: Я – 0, Р – 101, З – 110.

Укажите кратчайшее кодовое слово для буквы А, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код снаибольшим числовым значением.

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Ответ
111
Задание 2 Кодирование информации Открыть на доске →

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.

Буква Кодовое слово Буква Кодовое слово
А 00 Л 1101
Б Р 1010
Е 010 С 1110
И 011 Т 1011
К 1111 У 100

Укажите кратчайшее кодовое слово для буквы Б, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Ответ
1100
Задание 3 Кодирование информации Открыть на доске →

По каналу связи передаются шифрованные сообщения, содержащие только шесть букв: А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код. Для букв А, Б, В и Г используются кодовые слова 0, 11, 1000, 1011 соответственно.

Укажите минимальную сумму длин кодовых слов для букв Д и Е, при котором код будет удовлетворять условию Фано.

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Ответ
8
Задание 4 Кодирование информации Открыть на доске →

По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: К – 1, Н – 001. Для трёх оставшихся букв А, З и Т кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАНТАТА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

Ответ
18
Задание 5 Кодирование информации Открыть на доске →

Для кодирования некоторой последовательности, состоящей из букв К, Л,
М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М, Н использовали соответственно кодовые слова 000, 001, 010, 11. Для двух оставшихся букв – П и Р – длины кодовых слов неизвестны.

Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Ответ
10
Задание 6 Кодирование информации Открыть на доске →

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У.
Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.

Буква Кодовое слово Буква Кодовое слово
А 00 Л 1001
Б 1000 Р
Е 010 С 1010
И 011 Т 1101
К 1011 У 111

Укажите кратчайшее кодовое слово для буквы Р, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.
Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Ответ
1100
Задание 7 Кодирование информации Открыть на доске →

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.

Буква Кодовое слово Буква Кодовое слово
А 00 Л 1101
Б 1100 Р 1000
Е 010 С 1110
И 011 Т 1001
К 1111 У

Укажите кратчайшее кодовое слово для буквы У, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код
с наименьшим числовым значением.

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Ответ
101
Задание 8 Кодирование информации Открыть на доске →

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для кодирования букв используются кодовые слова.

Буква Кодовое слово Буква Кодовое слово
А 00 Л
Б 1000 Р 1110
Е 010 С 1010
И 011 Т 1111
К 1011 У 110

Укажите кратчайшее кодовое слово для буквы Л, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Ответ
1001
Задание 9 Кодирование информации Открыть на доске →

По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

А 000
Б 001
В 01
Г 11

Какое наименьшее количество двоичных знаков требуется для кодирования четырёх оставшихся букв?

В ответе запишите суммарную длину кодовых слов для букв: Д, Е, Ж, З.

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Ответ
16
Задание 10 Кодирование информации Открыть на доске →

По каналу связи передаются шифрованные сообщения, содержащие только пять букв: А, Б, В, Г, Д. Для передачи используется неравномерный двоичный код. Для букв А, Б и В используются кодовые слова 101, 110, 1000 соответственно.

Укажите минимальную сумму длин кодовых слов для букв Г и Д, при котором код будет удовлетворять условию Фано.

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Ответ
4
ИнфДоска

Разбирайте задание 4 ЕГЭ на онлайн-доске

Задание из банка — на доску в один клик, ответ видите только вы. После урока доска сама составит отчёт маме или папе.

Другие задания ЕГЭ