Код Фано: как решать — ЕГЭ по информатике

ЕГЭ Информатика сложность в тренажёре: продвинутая

По каналу связи передаются сообщения, составленные только из букв Г, О, П, Т. Буквы кодируются двоичным кодом… Код Фано — ЕГЭ по информатике, тема «Кодирование вариантов и мощность алфавита». Ответ проверяется на странице, разбор — сразу.

Пример 1

По каналу связи передаются сообщения, составленные только из букв Г, О, П, Т. Буквы кодируются двоичным кодом, удовлетворяющим условию Фано: ни одно кодовое слово не является началом другого кодового слова. Для некоторых букв кодовые слова уже выбраны: О — 10. Для остальных букв (Г, П, Т) кодовые слова ещё не выбраны, но каждая буква набора должна получить своё кодовое слово. Какое наименьшее количество двоичных знаков может занять код слова ПОТОП?

Ответ и разбор

Ответ: 9

По условию Фано новое кодовое слово не может совпадать с известным (10), быть его началом или начинаться с него.
Заняты сами известные слова и их начала (1), поэтому новые слова можно начинать только со свободных ветвей кодового дерева: 0, 11.
Кодовые слова нужны ещё 3 буквам (Г, П, Т), а свободных ветвей 2 — одну ветвь придётся разделить: ветвь x делится на x0 и x1, и её слова становятся на знак длиннее.
В слове ПОТОП: буква П — 2 раза, буква Т — 1 раз. Короткие слова выгодно отдавать частым буквам, а букве Г, которой в слове нет, — самое длинное слово: в длину кода она не входит, но место в дереве занимает.
Наборы слов, которые могут дать наименьшую длину (любой другой набор по каждой длине не короче одного из них):

  • 0, 110, 111 (длины 1, 3, 3): П — 0, Т — 110, Г — 111; длина кода 2 · 1 + 3 = 5;
  • 00, 01, 11 (длины 2, 2, 2): П — 00, Т — 01, Г — 11; длина кода 2 · 2 + 2 = 6.

Наименьшая длина кода букв Г, П, Т — 5.
Буквы с известным кодом: О (10, 2 знака) встречается 2 раза — 4.
Итого: 5 + 4 = 9.

Ответ: 9.

Нашли ошибку? Напишите нам, код задания: ege-informatics-kod-fano-dlina-slova-13rbxx1

Ещё задания этого вида — ниже. Открыть тренажёр

RAID 1 хранит зеркальные копии данных на дисках, помогая пережить отказ одного из них. Но это не полноценная резервная копия: ошибочное удаление тоже отражается в зеркале. Защита от поломки носителя и возможность вернуть старый файл решают разные задачи.

Разобранный пример

По каналу связи передаются сообщения, составленные только из букв А, В, М, О, Т. Буквы кодируются двоичным кодом, удовлетворяющим условию Фано: ни одно кодовое слово не является началом другого кодового слова. Для некоторых букв кодовые слова уже выбраны: А — 001. Для остальных букв (В, М, О, Т) кодовые слова ещё не выбраны, но каждая буква набора должна получить своё кодовое слово. Какое наименьшее количество двоичных знаков может занять код слова АВТОМАТ?

Решение

Ответ: 17

По условию Фано новое кодовое слово не может совпадать с известным (001), быть его началом или начинаться с него.
Заняты сами известные слова и их начала (0, 00), поэтому новые слова можно начинать только со свободных ветвей кодового дерева: 000, 01, 1.
Кодовые слова нужны ещё 4 буквам (В, М, О, Т), а свободных ветвей 3 — одну ветвь придётся разделить: ветвь x делится на x0 и x1, и её слова становятся на знак длиннее.
В слове АВТОМАТ: буква Т — 2 раза, буквы В, М, О — по одному разу. Короткие слова выгодно отдавать частым буквам.
Наборы слов, которые могут дать наименьшую длину (любой другой набор по каждой длине не короче одного из них):

  • 1, 000, 010, 011 (длины 1, 3, 3, 3): Т — 1, В — 000, М — 010, О — 011; длина кода 2 · 1 + 3 + 3 + 3 = 11;
  • 01, 10, 11, 000 (длины 2, 2, 2, 3): Т — 01, В — 10, М — 11, О — 000; длина кода 2 · 2 + 2 + 2 + 3 = 11;
  • 1, 01, 0000, 0001 (длины 1, 2, 4, 4): Т — 1, В — 01, М — 0000, О — 0001; длина кода 2 · 1 + 2 + 4 + 4 = 12.

Наименьшая длина кода букв В, М, О, Т — 11.
Буквы с известным кодом: А (001, 3 знака) встречается 2 раза — 6.
Итого: 11 + 6 = 17.

Ответ: 17.

Нашли ошибку? Напишите нам, код задания: ege-informatics-kod-fano-dlina-slova-u435f

Формулы и приём

Число вариантов и биты

Сколько бит нужно, чтобы закодировать 30 учеников класса?

N = 2i

N
количество различных вариантов, штук
i
количество бит на один вариант, бит

Каждый бит удваивает число вариантов. Для 30 человек 4 бита мало (16), а 5 бит хватает (32). Берут наименьшее i, при котором 2i не меньше нужного числа.

Округлять надо ВВЕРХ: 4,9 бита не бывает, нужен целый пятый.

Ещё примеры

Пример 2

По каналу связи передаются сообщения, составленные только из букв Б, К, Л, О. Буквы кодируются двоичным кодом, удовлетворяющим условию Фано: ни одно кодовое слово не является началом другого кодового слова. Для некоторых букв кодовые слова уже выбраны: К — 11. Для остальных букв (Б, Л, О) кодовые слова ещё не выбраны, но каждая буква набора должна получить своё кодовое слово. Какое наименьшее количество двоичных знаков может занять код слова КОЛОБОК?

Ответ и разбор

Ответ: 13

По условию Фано новое кодовое слово не может совпадать с известным (11), быть его началом или начинаться с него.
Заняты сами известные слова и их начала (1), поэтому новые слова можно начинать только со свободных ветвей кодового дерева: 0, 10.
Кодовые слова нужны ещё 3 буквам (Б, Л, О), а свободных ветвей 2 — одну ветвь придётся разделить: ветвь x делится на x0 и x1, и её слова становятся на знак длиннее.
В слове КОЛОБОК: буква О — 3 раза, буквы Б, Л — по одному разу. Короткие слова выгодно отдавать частым буквам.
Наборы слов, которые могут дать наименьшую длину (любой другой набор по каждой длине не короче одного из них):

  • 0, 100, 101 (длины 1, 3, 3): О — 0, Б — 100, Л — 101; длина кода 3 · 1 + 3 + 3 = 9;
  • 00, 01, 10 (длины 2, 2, 2): О — 00, Б — 01, Л — 10; длина кода 3 · 2 + 2 + 2 = 10.

Наименьшая длина кода букв Б, Л, О — 9.
Буквы с известным кодом: К (11, 2 знака) встречается 2 раза — 4.
Итого: 9 + 4 = 13.

Ответ: 13.

Нашли ошибку? Напишите нам, код задания: ege-informatics-kod-fano-dlina-slova-nub78q

Пример 3

По каналу связи передаются сообщения, составленные только из букв А, В, М, О, Р, С. Буквы кодируются двоичным кодом, удовлетворяющим условию Фано: ни одно кодовое слово не является началом другого кодового слова. Для некоторых букв кодовые слова уже выбраны: О — 0111, С — 0110. Для остальных букв (А, В, М, Р) кодовые слова ещё не выбраны, но каждая буква набора должна получить своё кодовое слово. Какое наименьшее количество двоичных знаков может занять код слова САМОВАР?

Ответ и разбор

Ответ: 19

По условию Фано новое кодовое слово не может совпадать с известным (0111, 0110), быть его началом или начинаться с него.
Заняты сами известные слова и их начала (0, 01, 011), поэтому новые слова можно начинать только со свободных ветвей кодового дерева: 00, 010, 1.
Кодовые слова нужны ещё 4 буквам (А, В, М, Р), а свободных ветвей 3 — одну ветвь придётся разделить: ветвь x делится на x0 и x1, и её слова становятся на знак длиннее.
В слове САМОВАР: буква А — 2 раза, буквы В, М, Р — по одному разу. Короткие слова выгодно отдавать частым буквам.
Наборы слов, которые могут дать наименьшую длину (любой другой набор по каждой длине не короче одного из них):

  • 1, 000, 001, 010 (длины 1, 3, 3, 3): А — 1, В — 000, М — 001, Р — 010; длина кода 2 · 1 + 3 + 3 + 3 = 11;
  • 00, 10, 11, 010 (длины 2, 2, 2, 3): А — 00, В — 10, М — 11, Р — 010; длина кода 2 · 2 + 2 + 2 + 3 = 11;
  • 1, 00, 0100, 0101 (длины 1, 2, 4, 4): А — 1, В — 00, М — 0100, Р — 0101; длина кода 2 · 1 + 2 + 4 + 4 = 12.

Наименьшая длина кода букв А, В, М, Р — 11.
Буквы с известным кодом: О (0111, 4 знака) встречается 1 раз — 4; С (0110, 4 знака) встречается 1 раз — 4.
Итого: 11 + 8 = 19.

Ответ: 19.

Нашли ошибку? Напишите нам, код задания: ege-informatics-kod-fano-dlina-slova-irhvxu

Пример 4

По каналу связи передаются сообщения, составленные только из букв А, В, Г, Л, О. Буквы кодируются двоичным кодом, удовлетворяющим условию Фано: ни одно кодовое слово не является началом другого кодового слова. Для некоторых букв кодовые слова уже выбраны: А — 10. Для остальных букв (В, Г, Л, О) кодовые слова ещё не выбраны, но каждая буква набора должна получить своё кодовое слово. Какое наименьшее количество двоичных знаков может занять код слова ГОЛОВА?

Ответ и разбор

Ответ: 14

По условию Фано новое кодовое слово не может совпадать с известным (10), быть его началом или начинаться с него.
Заняты сами известные слова и их начала (1), поэтому новые слова можно начинать только со свободных ветвей кодового дерева: 0, 11.
Кодовые слова нужны ещё 4 буквам (В, Г, Л, О), а свободных ветвей 2 — ветви придётся делить: ветвь x делится на x0 и x1, и её слова становятся на знак длиннее.
В слове ГОЛОВА: буква О — 2 раза, буквы В, Г, Л — по одному разу. Короткие слова выгодно отдавать частым буквам.
Наборы слов, которые могут дать наименьшую длину (любой другой набор по каждой длине не короче одного из них):

  • 00, 11, 010, 011 (длины 2, 2, 3, 3): О — 00, В — 11, Г — 010, Л — 011; длина кода 2 · 2 + 2 + 3 + 3 = 12;
  • 0, 110, 1110, 1111 (длины 1, 3, 4, 4): О — 0, В — 110, Г — 1110, Л — 1111; длина кода 2 · 1 + 3 + 4 + 4 = 13.

Наименьшая длина кода букв В, Г, Л, О — 12.
Буквы с известным кодом: А (10, 2 знака) встречается 1 раз — 2.
Итого: 12 + 2 = 14.

Ответ: 14.

Нашли ошибку? Напишите нам, код задания: ege-informatics-kod-fano-dlina-slova-8taaiv

Рядом

Продолжить тренировку

Откройте тренажёр, чтобы решать похожие задания и отслеживать прогресс по темам. Для тренажёра нужен вход; на этой странице вход не нужен.

Задание в формате экзамена с разбором

Родителю

Приложение — для ученика. Родителю ставить его не нужно: кабинет родителя открывается в браузере. Родитель видит фактическую активность, регулярность и повторяющиеся ошибки. Проверять решения самостоятельно не требуется.