Что проверяет: Кодирование и условие Фано
Задание 4 ЕГЭ по информатике проверяет тему «кодирование и условие Фано». Ниже вы найдёте 4 варианта с условием, ответом и разбором, а под ними теория и алгоритм решения этого номера.
Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны. Какое наименьшее количество двоичных знаков требуется для кодирования оставшихся букв? Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений
Текст распознан с изображения задания. Формулы, таблицы и рисунки смотрите на картинке ниже.
Для кодирования сообщения используются пять букв: А, Б, В, Г и Д. Для четырёх из них известны двоичные коды: А — 00, Б — 01, В — 110, Г — 1110. Укажите кратчайший код буквы Д, при котором код допускает однозначное декодирование, то есть выполняется условие Фано: ни одно кодовое слово не является началом другого. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Условие Фано нарушается, если новый код начинается с одного из уже занятых или какой-то занятый код начинается с нового.
Коды длины 1 не подходят: любая однобитная строка окажется началом уже выданных слов. Перебирая двухбитные и более длинные строки по возрастанию, находим первую подходящую: 10.
Для кодирования сообщения используются пять букв: А, Б, В, Г и Д. Для четырёх из них известны двоичные коды: А — 10, Б — 111, В — 0110, Г — 0111. Укажите кратчайший код буквы Д, при котором код допускает однозначное декодирование, то есть выполняется условие Фано: ни одно кодовое слово не является началом другого. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Условие Фано нарушается, если новый код начинается с одного из уже занятых или какой-то занятый код начинается с нового.
Коды длины 1 не подходят: любая однобитная строка окажется началом уже выданных слов. Перебирая двухбитные и более длинные строки по возрастанию, находим первую подходящую: 00.
Для кодирования сообщения используются пять букв: А, Б, В, Г и Д. Для четырёх из них известны двоичные коды: А — 01, Б — 0011, В — 101, Г — 1000. Укажите кратчайший код буквы Д, при котором код допускает однозначное декодирование, то есть выполняется условие Фано: ни одно кодовое слово не является началом другого. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Условие Фано нарушается, если новый код начинается с одного из уже занятых или какой-то занятый код начинается с нового.
Коды длины 1 не подходят: любая однобитная строка окажется началом уже выданных слов. Перебирая двухбитные и более длинные строки по возрастанию, находим первую подходящую: 11.
Нужно построить кодовые слова, удовлетворяющие условию Фано, и найти их минимальную суммарную длину.
Для букв А, Б, В уже заданы коды 0, 10 и 110. Какой минимальной длины код можно дать букве Г, чтобы выполнялось условие Фано?
Ответ111, длина 3
Задание 4 входит в ЕГЭ по информатике. Это единственная страница сайта, где собраны все варианты этого номера: текст условия, картинка задания, правильный ответ, разбор решения и теория с алгоритмом. Остальные номера открываются в списке выше, а их перечень с темами есть в списке заданий ЕГЭ по информатике.