Давайте сначала разберём условие задачи. У нас имеются сообщения, в которых бывают только 4 буквы: П, О, С, Т. При этом сами сообщения закодированы с помощью двоичного кода, то есть вместо букв передаются последовательности ноликов и единичек.
Известно, что Т кодируется 111, О — 0, П — 100. Например, ПОП было бы закодировано так: 100 0100 (полужирным выделено вхождение буквы П). А, например, вот такая последовательность 1110100 декодировалась бы однозначно в слово ТОП.
Нам надо придумать наименьший возможный код для буквы С, при котором декодирование было бы однозначным. Что означает слово "однозначность" в данном контексте?
К примеру, давайте обозначим букву С за 1. Наименьший возможный? Да, потому что меньше 1 символа не бывает. Но есть ли однозначность?
Ответ: код буквы С, которых сохраняет однозначость кодирования/декодирования, — 101 .
По каналу связи передаются сообщения, содержащие только пять букв: A, B, С, D, E. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв A, B, C используются такие кодовые слова:
A – 1, B – 010, C – 000.
Укажите кратчайшее кодовое слово для буквы E, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Пояснение.
Буква E не может кодироваться как 0, так как кодирование буквы B начинается с 0.
Буква E не может кодироваться как 1, так как это кодирование буквы А.
Буква E не может кодироваться как 10 и 11 − так как кодирование буквы А - 1.
Буква E не может кодироваться как 01 и 00 - так как кодирование буквы B начинается с 01, а кодирование буквы C с 00. Буква E может кодироваться как 001 - это наименьшее возможное значение.
Ответ: 001.
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано; для букв A, Б, В используются такие кодовые слова: А - 0, Б - 101, В - 110.
Какова наименьшая возможная суммарная длина всех кодовых слов? Примечание.
Пояснение.
Перечислим возможные коды в порядке возрастания длины. Стоит сразу сказать, что любой код, начинающийся с 0, не подходит, так как код А - 0, поэтому смотрим только на те, что начинаются с 1.
1 - нельзя, Б, В начинаются с 1.
10 - нельзя из-за Б.
11 - нельзя из-за В.
111 - можно использовать, пусть это будет код Д.
100 - также можно использовать, но если мы его возьмём, то не будет больше кодов, которые можно будет взять, так как все коды, начинающиеся с 0, уже нельзя брать, а все коды, начинающиеся с 1 и имеющие длину больше трёх, начинаются с одной из этих строк: 100, 101, 110, 111.
Рассмотрели все коды с длинами от 1 до 3, поэтому теперь достаточно взять любые два подходящие кода длины 4. Например, 1000 и 1001.
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано; для букв A, Б, В используются такие кодовые слова: А - 1, Б – 010, В – 001.
Какова наименьшая возможная суммарная длина всех кодовых слов? Примечание. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.
Пояснение.
Перечислим возможные коды в порядке возрастания длины. Стоит сразу сказать, что любой код, начинающийся с 1, не подходит, так как код А - 1, поэтому смотрим только на те, что начинаются с 0.
0 - нельзя, Б, В начинаются с 0.
01 - нельзя из-за Б.
00 - нельзя из-за В.
000 - можно использовать, пусть это будет код Д.
011 - также можно использовать, но если мы его возьмём, то не будет больше кодов, которые можно будет взять, так как все коды, начинающиеся с 1, уже нельзя брать, а все коды, начинающиеся с 0 и имеющие длину больше трёх, начинаются с одной из этих строк: 011, 010, 001, 000.
Рассмотрели все коды с длинами от 1 до 3, поэтому теперь достаточно взять любые два подходящие кода длины 4. Например, 0111 и 0110.
В сумме длина кодов 1 + 3 + 3 + 3 + 4 + 4 = 18.
Ответ: 18
Коды выше удовлетворяют условию Фано. В сумме длина кодов будет равна 1 + 3 * 4 = 13.
По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А – 11, B – 101, C – 0. Какова наименьшая возможная суммарная длина всех кодовых слов?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.
Пояснение.
Заметим, что для алфавита из трёх букв, код с наименьшей суммарной длиной кодовых слов, удовлетворяющий условию Фано имел бы длину 1 + 2 + 2 = 5. Для алфавита из четырёх букв: 1 + 2 + 3 + 3 = 9. Аналогично можно получить минимальную длину суммарную длину кодовых слов для алфавита, содержащего произвольное число символов.
Удостоверимся, что, используя кодовые слова, приведённые в условии можно построить код, удовлетворяющий условию Фано и имеющий наименьшую суммарную длину. Будем использовать для буквы D кодовое слово 1000, для буквы E кодовое слово 10010, для буквы F 10011.
Ответ: 20.
По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А – 00, B – 010, C – 1. Какова наименьшая возможная суммарная длина всех кодовых слов?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.
Пояснение.
Для нахождения кодовых слов будем использовать двоичное дерево, в котором от каждого узла отходит две ветви, соответствующие выбору следующей цифры кода. Буквы будем размещать на конечных узлах дерева - листьях. Условие Фано выполняется, поскольку при проходе от корня дерева к букве в середине пути не встречается других букв.
Пример дерева, обеспечивающего минимальную сумму длин всех шести кодов изображено на рисунке.
Суммарная длина такого кода 1 + 2 + 3 + 4 + 5 + 5 = 20.
Ответ: 20.
По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А - 11, B - 101, C - 0.
Укажите кодовое слово наименьшей возможной длины, которое можно использовать для буквы F. Если таких слов несколько, укажите то из них, которое соответствует наибольшему возможному двоичному числу.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.
Пояснение.
Имеющиеся кодовые слова имеют длину один, два и три, следовательно, наименьшая длина кодового слова для буквы F равна четырём. Кодовое слово, удовлетворяющее условию Фано - 1001.
Ответ: 1001.
Примечание.
Заметим, что более короткое кодовое слово 100 не подходит, поскольку тогда невозможно найти кодовые слова для букв D и E.
Код 1000 не подходит, так как сказано "Если таких слов несколько, укажите то из них, которое соответствует наибольшему возможному двоичному числу".
Ответ: 1001
Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 30 сентября 2016 года Вариант ИН10104
По каналу связи передаются сообщения, содержащие только пять букв: Ш, К, О, Л, А. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы О используется кодовое слово 0; для буквы А используется кодовое слово 10.
Какова минимальная общая длина кодовых слов для всех пяти букв?
Примечание: условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Пояснение.
Следующая буква кодового слова должна кодироваться как 110, т.к. 11 мы взять можем, но тогда для всех кодов больше 2 не будет выполнено условие Фано (т.к. они начинаются на 10 или 11 и уже будут заняты). 100 мы взять не можем, как и 101. Следующая за ней буква имеет код 1110 для выполнения условия, а последующая - 1111. Тогда длина равна 4 + 4 + 3 + 2 + 1 = 14.
Ответ: 14.
Ответ: 14
Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 12 мая 2017 года Вариант ИН10503
По каналу связи передаются сообщения, содержащие только пять букв: П, И, Л, О, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы И используется кодовое слово 1; для буквы О используется кодовое слово 01.
Какова минимальная общая длина кодовых слов для всех пяти букв? Примечание: условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Пояснение.
Следующая буква кодового слова должна кодироваться кодом длины 3, т. к. 0, 11 и 10 мы взять не можем. Подходящий трехзначный код - 000 или 001. Если мы возьмем оба, то тогда наша пятая буква не может начинаться на 1, 01, 0, 00, 000, 001. Такого кода не существует, значит, мы можем взять только 1 из них. Тогда четвертая и пятая буква будут кодироваться минимум четыремя битами. Можно заметить, что нам подойдет код 0001 и 0000. Тогда длина равна 4 + 4 + 3 + 2 + 1 = 14.
Ответ: 14.
Ответ: 14
Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 12 мая 2017 года Вариант ИН10504
По каналу связи передаются сообщения, содержащие только четыре буквы: Р, Е, К, А; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Р, Е используются такие кодовые слова: А: 111, Р: 0, Е: 100.
Укажите кратчайшее кодовое слово для буквы К. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание
Пояснение.
0 - нельзя, это буква Р.
1 - нельзя, буквы Е и К начинаются с 1.
01 - нельзя из-за Р.
10 - нельзя из-за Е.
11 - нельзя из-за А.
000 - нельзя из-за Р.
001 - нельзя из-за Р.
101 - можно использовать.
Таким образом, кратчайшее кодовое слово для буквы К - 101.
Ответ: 101.
По каналу связи передаются сообщения, содержащие только четыре буквы: М, О, Р, Е; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв О, Р, Е используются такие кодовые слова: О: 111, Р: 0, Е: 100.
Укажите кратчайшее кодовое слово для буквы М. Если таких кодов несколько, укажите код с наибольшим числовым значением.
Примечание . Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Пояснение.
Перечислим возможные коды (не использующиеся для кодировки других букв) в порядке возрастания длины и числового значения.
0 - нельзя, Р начинаются с 0.
1 - нельзя, буквы Е и О начинаются с 1.
01 - нельзя из-за Р.
10 - нельзя из-за Е.
11 - нельзя из-за О.
000 - нельзя из-за Р.
001 - нельзя из-за Р.
101 - можно использовать.
110 - можно использовать.
111 - нельзя из-за О.
Таким образом, наибольшее числовое значение у кодового слова 110 для буквы М.
Ответ: 110.
Укажите кратчайшее кодовое слово для буквы И. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Пояснение.
Перечислим возможные коды (не использующиеся для кодировки других букв) в порядке возрастания длины и числового значения.
1 - нельзя, буквы А, Г и Т начинаются с 1.
01 - нельзя из-за М.
10 - нельзя из-за Г.
11 - нельзя из-за А.
000 - нельзя из-за Р.
001 - нельзя из-за Е.
100 - можно использовать.
101 - нельзя из-за Т.
110 - нельзя из-за А.
111 - нельзя из-за А.
Таким образом, наименьшее числовое значение у кодового слова 100 для буквы И.
Ответ: 100.
Ответ: 100
Источник: СтатГрад: Тренировочная работа 28.11.2017 ИН10203
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, Г, Е, И, М, Р, Т. Для передачи и спользуется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
Укажите кратчайшее кодовое слово для буквы Г. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Пояснение.
Перечислим возможные коды (не использующиеся для кодировки других букв) в порядке возрастания длины и числового значения.
1 - нельзя, буквы Б, Р и Т начинаются с 1.
01 - нельзя из-за А.
10 - нельзя из-за Б и Т.
11 - нельзя из-за Р.
000 - нельзя из-за И.
001 - нельзя из-за И.
100 - нельзя из-за Т.
101 - можно использовать.
110 - нельзя из-за Р.
111 - нельзя из-за Р.
Таким образом, наименьшее числовое значение у кодового слова 101 для буквы Г.
Ответ: 101.
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, Г, Е, И, М, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
Укажите кратчайшее кодовое слово для буквы И. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Пояснение.
Перечислим возможные коды (не использующиеся для кодировки других букв) в порядке возрастания длины и числового значения.
0 - нельзя, Б, Е, М и Р начинаются с 0.
1 - нельзя, А и Г начинаются с 1.
00 - нельзя из-за Б и Р.
01 - нельзя из-за М.
10 - нельзя из-за Г.
11 - нельзя из-за А.
000 - нельзя из-за Р.
001 - нельзя из-за Е.
010 - нельзя из-за М.
011 - нельзя из-за М.
100 - нельзя из-за Г.
101 - нельзя, поскольку, если закодировать букву И кодовым словом 101, для буквы Т не будет кодовых слов, удовлетворяющих условию Фано.
110 - нельзя из-за А.
111 - нельзя из-за А.
0000 - нельзя из-за Р.
0001 - нельзя из-за Р.
0010 - нельзя из-за Б.
0011 - нельзя из-за Е.
0100 - нельзя из-за М.
0101 - нельзя из-за М.
0110 - нельзя из-за М.
0111 - нельзя из-за М.
1000 - нельзя из-за Г.
1001 - нельзя из-за Г.
1010 - можно использовать.
1011 - можно использовать.
1100 - нельзя из-за А.
1101 - нельзя из-за А.
1110 - нельзя из-за А.
1111 - нельзя из-за А.
Таким образом, наименьшее числовое значение у кодового слова 1010 для буквы И.
Ответ: 1010.
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, Г, Е, И, М, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
Укажите кратчайшее кодовое слово для буквы Г. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Пояснение.
Перечислим возможные коды (не использующиеся для кодировки других букв) в порядке возрастания длины и числового значения.
0 - нельзя, А, Е, И и М начинаются с 0.
1 - нельзя, Б и Р начинаются с 1.
00 - нельзя из-за И.
01 - нельзя из-за А, Е и М.
10 - нельзя из-за Б.
11 - нельзя из-за Р.
000 - нельзя из-за И.
001 - нельзя из-за И.
010 - нельзя из-за М.
011 - нельзя из-за Е.
100 - нельзя, поскольку, если закодировать букву Г кодовым словом 100, для буквы Т не будет кодовых слов, удовлетворяющих условию Фано.
101 - нельзя из-за Б.
110 - нельзя из-за Р.
111 - нельзя из-за Р.
0000 - нельзя из-за И.
0001 - нельзя из-за И.
0010 - нельзя из-за И.
0011 - нельзя из-за И.
0100 - нельзя из-за М.
0101 - нельзя из-за А.
0110 - нельзя из-за Е.
№1
A, B, С, D. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв A, B, C используются такие кодовые слова: A: 111, B: 0, C: 100.
Укажите кратчайшее кодовое слово для буквы D, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
№2
По каналу связи передаются сообщения, содержащие только пять букв А, Б, В, Г, Д. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано; для букв A, Б, В используются такие кодовые слова: А: 0, Б: 101, В: 110.
№3
По каналу связи передаются сообщения, содержащие только буквы
А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано; для букв A, Б, В используются такие кодовые слова: А: 0, Б: 101, В: 110.
Какова наименьшая возможная суммарная длина всех кодовых слов?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.
№4
По каналу связи передаются сообщения, содержащие только пять букв А, Б, В, Г, Д. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано; для букв A и Б используются такие кодовые слова: А: 0, Б: 10.
Какова наименьшая возможная суммарная длина всех кодовых слов?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.
№5
По каналу связи передаются сообщения, содержащие только буквы
А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано; для букв A и Б используются такие кодовые слова: А: 0, Б: 10.
Какова наименьшая возможная суммарная длина всех кодовых слов?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.
№6
По каналу связи передаются сообщения, содержащие только пять букв: П, И, Л, О, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы И используется кодовое слово 0; для буквы О используется кодовое слово 10, для буквы Л используется кодовое слово 1101. Кодовое слово для буквы Т длиннее, чем кодовое слово для буквы П.
Напишите в ответе кодовое слово для буквы Т, имеющее наименьшую возможную длину. Если таких существует несколько таких слов, напишите то из них, которое имеет меньшее двоичное значение.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
№7
По каналу связи передаются сообщения, содержащие только шесть букв:
А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А – 11, B – 101, C – 0.
Укажите кодовое слово наименьшей возможной длины, которое можно использовать для буквы F. Если таких слов несколько, укажите то из них, которое соответствует наибольшему возможному двоичному числу.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование
№8 Для кодирования некоторой последовательности, состоящей из букв М, О, С, К, В, А, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв О, С, В, А использовали соответственно кодовые слова 000, 001, 10, 11. Укажите кратчайшее возможное кодовое слово для буквы М. Если существует несколько таких слов, укажите слово с наименьшим числовым значением.
№9
По каналу связи с помощью равномерного двоичного кода передаются сообщения, содержащие только 4 буквы У, Р, О,К. При этом для набора кодовых слов выполнено такое свойство:
любые два слова из набора отличаются не менее, чем в трёх позициях.
Это свойство важно для расшифровки сообщений при наличии помех.
Для кодирования букв Р, О, К используются 5-битовые кодовые слова:
Р: 01111, О: 00001, К: 11000.
5-битовый код для буквы У начинается с 1 и заканчивается на 0. Определите кодовое слово для буквы У
Урок посвящен тому, как решать 5 задание ЕГЭ по информатике
5-я тема характеризуется, как задания базового уровня сложности, время выполнения – примерно 2 минуты, максимальный балл — 1
Пример:
Зашифруем буквы А, Б, В, Г при помощи двоичного кодирования равномерным кодом и посчитаем количество возможных сообщений:
Таким образом, мы получили равномерный код
, т.к. длина каждого кодового слова одинакова для всех кодов
(2).
Декодирование (расшифровка) - это восстановление сообщения из последовательности кодов.
Для решения задач с декодированием, необходимо знать условие Фано:
Условие Фано: ни одно кодовое слово не должно являться началом другого кодового слова (что обеспечивает однозначное декодирование сообщений с начала)
Префиксный код - это код, в котором ни одно кодовое слово не совпадает с началом другого кодового слова. Сообщения при использовании такого кода декодируются однозначно.
Однозначное декодирование обеспечивается:
ЕГЭ 5.1: Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 0 , 1 , 2 , 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления).
Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.
Результат: 22162
Решение ЕГЭ данного задания по информатике, видео:
Рассмотрим еще разбор 5 задания ЕГЭ:
ЕГЭ 5.2: Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв - из двух бит, для некоторых - из трех). Эти коды представлены в таблице:
a | b | c | d | e |
---|---|---|---|---|
000 | 110 | 01 | 001 | 10 |
Какой набор букв закодирован двоичной строкой 1100000100110 ?
✎ 1 вариант решения:
Результат: b a c d e.
✎ 2 вариант решения:
Результат: b a c d e.
Кроме того, вы можете посмотреть видео решения этого задания ЕГЭ по информатике:
Решим следующее 5 задание:
ЕГЭ 5.3:
Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4 , и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23 , то получим последовательность 0010100110).
Определите, какое число передавалось по каналу в виде 01100010100100100110 .
Ответ: 6 5 4 3
Вы можете посмотреть видео решения этого задания ЕГЭ по информатике:
ЕГЭ 5.4:
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0 , для буквы К - кодовое слово 10 .
Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
✎ 1 вариант решения основан на логических умозаключениях:
✎ 2 вариант решения :
(Н) -> 0 -> 1 символ (К) -> 10 -> 2 символа (Л) -> 110 -> 3 символа (М) -> 111 -> 3 символаОтвет: 9
ЕГЭ по информатике 5 задание 2017 ФИПИ вариант 2 (под редакцией Крылова С.С., Чуркиной Т.Е.):
По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются такие кодовые слова: А: 101010 , Б: 011011 , В: 01000 .
Г, при котором код будет допускать однозначное декодирование. наименьшим числовым значением.
Результат: 00
ЕГЭ по информатике 5 задание 2017 ФИПИ вариант 16 (под редакцией Крылова С.С., Чуркиной Т.Е.):
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приемной стороне канала связи. Использовали код: А — 01 , Б — 00 , В — 11 , Г — 100 .
Укажите, каким кодовым словом должна быть закодирована буква Д.
Длина
этого кодового слова должна быть наименьшей
из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Результат: 101
Подробней разбор урока можно посмотреть на видео ЕГЭ по информатике 2017:
ЕГЭ по информатике 5 задание 2017 ФИПИ вариант 17 (Крылов С.С., Чуркина Т.Е.):
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д и Е, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приемной стороне канала связи. Использовали код: А — 0 , Б — 111 , В — 11001 , Г — 11000 , Д — 10 .
Укажите, каким кодовым словом должна быть закодирована буква Е. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.
1 - не подходит (все буквы кроме А начинаются с 1) 10 - не подходит (соответствует коду Д) 11 - не подходит (начало кодов Б, В и Г) 100 - не подходит (код Д - 10 - является началом данного кода) 101 - не подходит (код Д - 10 - является началом данного кода) 110 - не подходит (начало кода В и Г) 111 - не подходит (соответствует коду Б) 1000 - не подходит (код Д - 10 - является началом данного кода) 1001 - не подходит (код Д - 10 - является началом данного кода) 1010 - не подходит (код Д - 10 - является началом данного кода) 1011 - не подходит (код Д - 10 - является началом данного кода) 1100 - не подходит (начало кода В и Г) 1101 - подходит
Результат: 1101
Более подробное решение данного задания представлено в видеоуроке:
5 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.
Укажите кратчайшее кодовое слово для буквы Б
, при котором код будет удовлетворять условию Фано.
Если таких кодов несколько, укажите код с наименьшим
числовым значением.
Результат: 1100
Подробное решение данного 5 задания из демоверсии ЕГЭ 2018 года смотрите на видео:
Задание 5_9. Типовые экзаменационные варианты 2017. Вариант 4 (Крылов С.С., Чуркина Т.Е.):
По каналу связи передаются шифрованные сообщения, содержащие только четыре букв: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А , Б , В используются кодовые слова:
А: 00011 Б: 111 В: 1010
Укажите кратчайшее кодовое слово для буквы Г
, при котором код будет допускать однозначное декодирование.
Если таких кодов несколько, укажите код с наименьшим
числовым значением.
Результат: 00
Задание 5_10. Тренировочный вариант №3 от 01.10.2018 (ФИПИ):
По каналу связи передаются сообщения, содержащие только буквы: А, Е, Д, К, М, Р ; для передачи используется двоичный код, удовлетворяющий условию Фано. Известно, что используются следующие коды:
Е – 000 Д – 10 К – 111
Укажите наименьшую возможную длину закодированного сообщения ДЕДМАКАР
.
В ответе напишите число – количество бит.
Д Е Д М А К А Р 10 000 10 001 01 111 01 110
Результат: 20
Смотрите виде решения задания: