Разбор заданий егэ информатика задание 5. Кодирование и расшифровка сообщений

Единый государственный экзамен по информатике состоит из 27 заданий. В задании 5 проверяются навыки кодирования и декодирования информации. Школьник должен уметь кодировать и декодировать информацию в различных системах счисления, а также расшифровывать сообщения и выбирать оптимальный код. Здесь вы можете узнать, как решать задание 5 ЕГЭ по информатике, а также изучить примеры и способы решения на основе подробно разобранных заданий.

Все задания ЕГЭ все задания (107) ЕГЭ задание 1 (19) ЕГЭ задание 3 (2) ЕГЭ задание 4 (11) ЕГЭ задание 5 (10) ЕГЭ задание 6 (7) ЕГЭ задание 7 (3) ЕГЭ задание 9 (5) ЕГЭ задание 10 (7) ЕГЭ задание 11 (1) ЕГЭ задание 12 (3) ЕГЭ задание 13 (7) ЕГЭ задание 16 (19) ЕГЭ задание 17 (4) ЕГЭ без номера (9)

Для кодирования букв решили использовать двоичное представление

Для кодирования букв решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если закодировать последовательность букв таким способом и результат записать восьмеричным кодом, то получится...

Для передачи по каналу связи сообщения, состоящего только из символов

Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется посимвольное кодирование. Через канал связи передаётся сообщение. Закодируйте сообщение данным кодом. Полученное двоичное число переведите в шестнадцатеричный вид.

Задание входит в ЕГЭ по информатике для 11 класса под номером 5.

Для кодирования букв А, Б, В, Г решили использовать двухразрядные

Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11, соответственно). Если таким способом закодировать последовательность символов и записать полученное двоичное число в шестнадцатеричной системе счисления, то получится...

Задание входит в ЕГЭ по информатике для 11 класса под номером 5.

По каналу связи передаются сообщения, содержащие только 5 букв

По каналу связи передаются сообщения, содержащие только 5 букв. Для кодирования букв используется неравномерный двоичный код. Среди приведённых ниже слов укажите такое, код которого можно декодировать только одним способом. Если таких слов несколько, укажите первое по алфавиту.

Задание входит в ЕГЭ по информатике для 11 класса под номером 5.

Для передачи сообщений нужно использовать неравномерный двоичный код

По каналу связи передаются сообщения, содержащие только 4 буквы. Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование; при этом сообщения должны быть как можно короче. Шифровальщик может использовать один из перечисленных ниже кодов. Какой код ему следует выбрать?

Задание входит в ЕГЭ по информатике для 11 класса под номером 5.

Для кодирования сообщения, состоящего только из букв А, Б, В и Г

Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код. Если таким способом закодировать последовательность символов и записать результат в шестнадцатеричном коде, то получится...

Задание входит в ЕГЭ по информатике для 11 класса под номером 5.

Для 5 букв латинского алфавита заданы их двоичные коды

Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв - из двух бит, для некоторых - из трех). Эти коды представлены в таблице. Определите, какой набор букв закодирован двоичной строкой?

Задание входит в ЕГЭ по информатике для 11 класса под номером 5.

Для передачи чисел по каналу с помехами используется код проверки четности

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

Задание входит в ЕГЭ по информатике для 11 класса под номером 5.

Для передачи данных по каналу связи используется 5-битовый код

Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются кодовыми словами. При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается "х"). Получено сообщение. Декодируйте это сообщение - выберите правильный вариант.

Задание входит в ЕГЭ по информатике для 11 класса под номером 5.

Для кодирования некоторой последовательности, состоящей из букв

Для кодирования некоторой последовательности, состоящей из букв, используется неравномерный двоичный префиксный код. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему остался префиксным? Коды остальных букв меняться не должны. Выберите правильный вариант ответа. Примечание. Префиксный код - это код, в котором ни одно кодовое слово не является началом другого; такие коды позволяют однозначно декодировать полученную двоичную последовательность.

Задание входит в ЕГЭ по информатике для 11 класса под номером 5.

Чтобы посмотреть презентацию с картинками, оформлением и слайдами, скачайте ее файл и откройте в PowerPoint на своем компьютере.
Текстовое содержимое слайдов презентации: Подготовка к ЕГЭучитель информатикиМБОУ СОШ №1 г. Азова Баламутова Ирина Александровна2015 г. Кодирование и декодирование информации. (Задания 5) Кодирование данных, комбинаторика, системы счисления (Задания 10) СодержАние темы ” Кодирование и декодированиеинформации.”ТеорияЗадача 1Задача 2Задача 3Задача 4Задачи для тренировкиТема: Кодирование данных, комбинаторика, системы счисленияТеорияЗадача 1Задача 2Задача 3Задача 4Задача 5Задачи для тренировкиСписок литературыПОЛЕЗНЫЕ САЙТЫ ДЛЯ ПОДГОТОВКИ К ЕГЭ2 декодировать с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова;закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова;условие Фано – это достаточное, но не необходимое условие однозначного декодированиятеория3 Кодирование – это перевод информации с одного языка на другой. Кодирование может быть равномерное и неравномерное.При равномерном кодировании все символы кодируются кодами равной длины.При неравномерном кодировании разные символы могут кодироваться кодами разной длины.4теория По каналу связи передаются сообщения, каждое из которых содержит 16 букв А, 8 букв Б, 4 буквы В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования: а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование); б) общая длина закодированного сообщения должна быть как можно меньше.Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?555551) А:0, Б:10, В:110, Г:1112) А:0, Б:10, В:01, Г:113) А:1, Б:01, В:011, Г:0014) А:00, Б:01, В:10, Г:11Задача 15 сначала выберем коды, в которых ни одно кодовое слово не совпадет с началом другого (такие коды называю префиксными)для кода 2 условие «а» не выполняется, так как кодовое слово буквы В (01) начинается с кодового слова буквы А (0)для кода 3 условие «а» не выполняется, так как кодовое слово буквы В (011) начинается с кодового слова буквы Б (01)для кодов 1 и 4 условие выполняется, их рассматриваем дальшесчитаем общее количество битов в сообщении для кода 1:16∙1 + 8·2 + 4∙3 + 4∙3 = 56 битовсчитаем общее количество битов в сообщении для кода 4:16∙2 + 8·2 + 4∙2 + 4∙2 = 64 битакод 1 даёт наименьшую длину сообщения, поэтому выбираем егоОтвет: 1.6Решение задачи 1 Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0, для буквы Б – кодовое слово 110.Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?1) 7 2) 8 3) 9 4) 107Задача 2 Решение (способ 1, исключение вариантов):условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового словапоскольку уже есть кодовое слово 0, ни одно другое кодовое слово не может начинаться с 0 поскольку есть код 110, запрещены кодовые слова 1, 11; кроме того, ни одно другое кодовое слово не может начинаться с 110таким образом, нужно выбрать еще два кодовых слова, для которых выполняются эти ограничения.Есть одно допустимое кодовое слово из двух символов: 10 если выбрать кодовое слово 10 для буквы В, то остаётся одно допустимое трёхсимвольное кодовое слово – 111, которое можно выбрать для буквы Г8Решение задача 2 выбрав кодовые слова А – 0, Б – 110, В – 10, Г – 111, получаем суммарную длину кодовых слов 9 символов.Если же не выбрать В – 10, то есть три допустимых трёхсимвольных кодовых слова: 100, 101 и 110; при выборе любых двух их них для букв В и Г получаем суммарную длину кодовых слов 10, что больше 9; поэтому выбираем вариант 3 (9 символов) Ответ: 3. Решение задча 2 (продолжение) 9 АБ10100Решение (способ 2, построение дерева):условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового слова; при этом в дереве кода все кодовые слова должны располагаться в листьях дерева которые не имеют потомков;построим дерево для заданных кодовых слов А – 0 и Б – 110:10Задача 2 штриховыми линиями отмечены две «пустые» ветви, на которые можно «прикрепить» листья для кодовых слов букв В (10) и Г (111)АБ10100ВГвыбрав кодовые слова А – 0, Б – 110, В – 10, Г – 111, получаем суммарную длину кодовых слов 9 символовОтвет: 3. Задача 2 способ 2, построение дерева продолжение11 По каналу связи передаются сообщения, содержащие только 4 буквы П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П: 100.Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением. 12Задача 3 ОТ101000П1Решение (способ 2, построение дерева):условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового слова; при этом в дереве кода все кодовые слова должны располагаться в листьях дерева, то есть в узлах, которые не имеют потомков;построим дерево для заданных кодовых слов О – 0, Т – 111 и П – 100:13Решение задачи 3 Штриховыми линиями отмечены две «пустые» ветви, на которые можно «прикрепить» лист для кодового слова буквы С: 101 или 110; из них минимальное значение имеет код 101Решение задачи 3(продолжение) 14 15Штриховыми линиями отмечены две «пустые» ветви, на которые можно «прикрепить» лист для кодового слова буквы С: 101 или 110; из них минимальное значение имеет код 101.ОТ101000П1СВыбрав кодовые слова А – 0, Б – 110, В – 10, Г – 111, получаем суммарную длину кодовых слов 9 символовОтвет: 101. Решение задачи 3 (продолжение)15 Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый. BD9AA5 2) BDA9B5 3) BDA9D5 4)DB9DAB 16Задача 4 «вытянем» растровое изображение в цепочку: сначала первая (верхняя) строка, потом – вторая, и т.д.:в этой полоске 24 ячейки, черные заполним единицами, а белые – нулями:поскольку каждая цифра в шестнадцатеричной системе раскладывается ровно в 4 двоичных цифры, разобьем полоску на тетрады – группы из четырех ячеек (в данном случае все равно, откуда начинать разбивку, поскольку в полоске целое число тетрад – 6):переводя тетрады в шестнадцатеричную систему, получаем последовательно цифры B (11), D(13), A(10), 9, D(13) и 5, то есть, цепочку BDA9D5поэтому правильный ответ – 3.17Решение задачи 4 1 строка2 строка3 строка4 строка1011110110101001110101011 строка2 строка3 строка4 строка10111101101010011101010118Решение задачи 4 (продолжение) За­да­ние 5 № 7746. Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв А, Б, В, Г и Д, ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный код, поз­во­ля­ю­щий од­но­знач­но де­ко­ди­ро­вать по­лу­чен­ную дво­ич­ную по­сле­до­ва­тель­ность. Вот этот код: А - 1; Б - 0100; В - 000; Г - 011; Д - 0101. Тре­бу­ет­ся со­кра­тить для одной из букв длину ко­до­во­го слова так, чтобы код по-преж­не­му можно было де­ко­ди­ро­вать од­но­знач­но. Коды осталь­ных букв ме­нять­ся не долж­ны. Каким из ука­зан­ных спо­со­бов это можно сде­лать? 1) для буквы Г - 112) для буквы В - 003) для буквы Г - 014) это не­воз­мож­ноОтвет:19 задачи для самостоятельного решения2
Задание 5 № 1104. Для кодирования букв X, Е, Л, О, Д решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с со­хра­не­ни­ем одного незначащего нуля в случае одноразрядного представления). Если закодировать последовательность букв ЛЕДОХОД таким способом и результат записать шестнадцатеричным кодом, то получится 1) 999С2) 32541453) 123F 4) 2143034 Ответ:20 ответы За­да­ние 5 № 1104ХЕЛОД0123400011011100Сна­ча­ла сле­ду­ет пред­ста­вить дан­ные в усло­вии числа в дво­ич­ном коде:за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв: ЛЕ­ДО­ХОД - 1001100110011100. Те­перь разобьём это пред­став­ле­ние на четвёрки спра­ва на­ле­во и пе­ре­ведём по­лу­чен­ный набор чисел cна­ча­ла в де­ся­тич­ный код, затем в шест­на­дца­те­рич­ный. 1001 1001 1001 1100 - 9 9 9 12 - 999С.Пра­виль­ный ответ ука­зан под но­ме­ром 1.21 Задание 5 № 7193 Для пе­ре­да­чи по ка­на­лу связи со­об­ще­ния, со­сто­я­ще­го толь­ко из сим­во­лов А, Б, В и Г, ис­поль­зу­ет­ся не­рав­но­мер­ный (по длине) код: А – 0; Б – 100; В – 101. Каким ко­до­вым сло­вом нужно ко­ди­ро­вать сим­вол Г, чтобы длина его была ми­ни­маль­ной, а код при этом до­пус­кал од­но­знач­ное раз­би­е­ние ко­ди­ро­ван­но­го со­об­ще­ния на сим­во­лы? 1) 12) 113) 01 Решение4) 010 http://inf.reshuege.ru/test?theme=232 Ответ:222
Задание 5 № 9293.23 Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Л использовали кодовое слово 1, для буквы М – кодовое слово 01. Какова наи­мень­шая возможная суммарная длина всех пяти кодовых слов?Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.Ответ:4Решение http://inf.reshuege.ru/test?theme=23123
24Задачидля тренировки видеоурок ссылкассылкаhttps://www.youtube.com/watch?v=BoBnzjwLsnU Тема: Кодирование данных, комбинаторика, системы счисления(Задания 10)25 Что нужно знать:русский алфавит принципы работы с числами, записанными в позиционных системах счисленияесли слово состоит из L букв, причем есть n1 вариантов выбора первой буквы, n2 вариантов выбора второй буквы и т.д., то число возможных слов вычисляется как произведение N = n1 · n2 · … · nLесли слово состоит из L букв, причем каждая буква может быть выбрана n способами, то число возможных слов вычисляется как N = nL26теория Вася составляет 5-буквенные слова, в которых есть только буквы С, Л, О, Н, причём буква С используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?27Задача 1 Буква С может стоять на одном из пяти мест: С****, *С***, **С**, ***С* и ****С, где * обозначает любой из оставшихся трёх символов в каждом случае в остальных четырёх позициях может быть любая из трёх букв Л, О, Н, поэтому при заданном расположении буквы С имеем 34 = 81 вариант всего вариантов 5 · 81 = 405.Ответ: 405.28решение Сколько существует различных символьных последовательностей длины 5 в четырёхбуквенном алфавите {A, C, G, T}, которые содержат ровно две буквы A?29Задача 2 Решение (вариант 1, перебор):рассмотрим различные варианты слов из 5 букв, которые содержат две буквы А и начинаются с А:АА*** А*А** А**А* А***АЗдесь звёздочка обозначает любой символ из набора {C, G, T}, то есть один из трёх символов. Итак, в каждом шаблоне есть 3 позиции, каждую из которых можно заполнить тремя способами, поэтому общее число комбинаций (для каждого шаблона!) равно 33 = 27 всего 4 шаблона, они дают 4 · 27 = 108 комбинаций30решение теперь рассматриваем шаблоны, где первая по счёту буква А стоит на второй позиции, их всего три:*АА** *А*А* *А**Аони дают 3 · 27 = 81 комбинациюдва шаблона, где первая по счёту буква А стоит на третьей позиции:**АА* **А*А они дают 2 · 27 = 54 комбинации и один шаблон, где сочетание АА стоит в конце ***АА они дают 27 комбинаций всего получаем (4 + 3 + 2 + 1) · 27 = 270 комбинаций Ответ: 270.Решение (продолжение)31 Все 4-буквенные слова, составленные из букв К, Л, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:КККК2. КККЛ3. КККР4. КККТ……Запишите слово, которое стоит на 67-м месте от начала списка. 32Задача 3 Самый простой вариант решения этой задачи – использование систем счисления; действительно, здесь расстановка слов в алфавитном порядке равносильна расстановке по возрастанию чисел, записанных в четверичной системе счисления (основание системы счисления равно количеству используемых букв).Выполним замену К0, Л1, Р2, Т3; поскольку нумерация слов начинается с единицы, а первое число КККК0000 равно 0, под номером 67 будет стоять число 66, которое нужно перевести в четверичную систему: 66 = 10024 Выполнив обратную замену (цифр на буквы), получаем слово ЛККР.Ответ: ЛККР.33Решение 34Задача 4 За­да­ние 10 № 6777. Сколь­ко слов длины 5 можно со­ста­вить из букв Е, Г, Э? Каж­дая буква может вхо­дить в слово не­сколь­ко раз. 35РешениеЕсли в алфавите M символов, то количество всех возможных «слов» (сообщений) длиной N равно Q = MN. В нашем слу­чае N = 5, M = 3. Сле­до­ва­тель­но, Q = 35 = 243. Ответ: 243. 36Задача 5 Задание 10 № 4797. В закрытом ящике находится 32 карандаша, некоторые из них синего цвета. Наугад вынимается один карандаш. Сообщение «этот карандаш – НЕ синий» несёт 4 бита информации. Сколько синих карандашей в ящике? 37 Формула Шенонна: где x - количество информации в сообщении о событии P, p - вероятность события P. вероятность того, что до­ста­ли НЕ синий где - число синих ка­ран­да­шей.Воспользовавшись формулой Шенонна, получаем, чтоУ=30Решение 38Задачидля тренировки самоподготовка видеоурок ссылкассылкаhttps://www.youtube.com/watch?v=BoBnzjwLsnU СПИСОК ЛИТЕРАТУРАhttp://kpolyakov.narod.ru/ Крылов С.С., Чуркина Т.Е. ЕГЭ 2015. Информатика и ИКТ. Типовые экзаменационные варианты. - М.: «Национальное образование», 2015. Лещинер В.Р. ЕГЭ 2015. Информатика. Типовые тестовые задания. - М.: Экзамен, 2015.Евич Л.Н., Кулабухов С.Ю. Информатика и ИКТ. Подготовка к ЕГЭ-2015. - Ростов-на-Дону: Легион, 2014. Ушаков Д.М., Якушкин П.А. Информатика. Самое полное издание типовых вариантов заданий ЕГЭ 2014. - М.: Астрель, 2014. Евич Л.Н., Кулабухов С.Ю. Информатика и ИКТ. Подготовка к ЕГЭ-2015. - Ростов-на-Дону: Легион, 2014. Островская Е.М., Самылкина Н.Н. ЕГЭ 2015. Информатика. Сдаём без проблем! - М.: Эксмо, 2014. Самылкина Н.Н., Островская Е.М. ЕГЭ 2015. Информатика. Тематические тренировочные задания. - М.: Эксмо, 2014.Зорина Е.М., Зорин М.В. ЕГЭ 2015. Информатика. Сборник заданий. - М.: «Эксмо», 2015.39 Полезные сайты для ПОДГОТОВКИ К ЕГЭ!40Информатика - это просто http://easyinformatics.ru/Видеоразбор задачи ЕГЭ-2013 http://www.агейчев.рф/ege.htmlОбразовательный портал для подготовки к экзаменам http://inf.reshuege.ru/?redir=1ЕГЭ по информатике 2013 http://infoegehelp.ru/40

Каталог заданий.
Передача информации. Выбор кода

Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К - кодовое слово 10. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

Примечание.

Решение.

Найдём наиболее короткие представления для всех букв. Кодовые слова 01 и 00 использовать нельзя, поскольку тогда нарушается условие Фано. Используем, например, для буквы Л кодовое слово 11. Тогда для четвёртой буквы нельзя подобрать кодовое слово, не нарушая условие Фано. Следовательно, для оставшихся двух букв нужно использовать трёхзначные кодовые слова. Закодируем буквы Л и М кодовыми словами 110 и 111. Тогда суммарная длина всех четырёх кодовых слов равна 1 + 2 + 3 + 3 = 9.

Ответ: 9.

Ответ: 9

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А - 1; Б - 0100; В - 000; Г - 011; Д - 0101. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?

1) для буквы Г - 11

2) для буквы В - 00

3) для буквы Г - 01

4) это невозможно

Решение.

Для однозначного декодирования получившееся в результате сокращения кодовое слово не должно быть началом никакого другого. Первый вариант ответа не подходит, поскольку код буквы А является началом кода буквы Г. Второй вариант ответа подходит. Третий вариант ответа не подходит, т. к. в таком случае код буквы Г является началом кода буквы Д.

Правильный ответ указан под номером: 2.

Ответ: 2

Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К – кодовое слово 10. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?

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

Решение.

Нельзя использовать кодовые слова, которые начинаются с 0 или с 10. 11 также не можем использовать, поскольку тогда мы больше не сможем взять никакое другое кодовое слово, а нам их нужно пять. Поэтому берём трёхзначное 110. 111 опять же не можем использовать, потому что понадобиться ещё одно кодовое слово, а вместе с этим не останется больше свободных. Теперь осталось взять всего два слова и это будут 1110 и 1111. Итого имеем 0, 10, 110, 1110 и 1111 - 14 символов.

Ответ: 14.

Ответ: 14

Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Л использовали кодовое слово 1, для буквы М – кодовое слово 01. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?

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

Решение.

Условие Фано - никакое кодовое слово не может быть началом другого кодового слова. Так как уже имеется кодовое слово 1, то никакое другое не может начинаться с 1. Только с 0. Также не может начинаться с 01, поскольку у нас уже есть 01. То есть любое новое кодовое слово будет начинаться с 00. Но это не может быть 00, так как иначе мы не сможем взять больше ни одного кодового слова, поскольку все более длинные слова начинаются либо с 1, либо с 00, либо с 01. Мы можем взять либо 000, либо 001. Но не оба сразу, поскольку опять же в таком случае мы больше не сможем взять ни одного нового кода. Тогда возьмём 001. И так как нам осталось всего два кода, то можем взять 0000 и 0001. Итого имеем: 1, 01, 001, 0000, 0001. Всего 14 символов.

Разбор 5 задания ЕГЭ 2016 года по информатике из демоверсии. Это задание на умение кодировать и декодировать информацию (уметь интерпретировать результаты, получаемые в ходе моделирования реальных процессов). Это задание базового уровня сложности. Примерное время выполнения задания 2 минуты.

Задание 5:

По каналу связи передаются сообщения, содержащие только четыре буквы: П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П: 100.
Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Ответ: ________

Разбор 5 задания ЕГЭ 2016:

Для решения данного задания нужно знать условие Фано.

Условие Фано:
Закодированное сообщение можно однозначно декодировать если никакое кодовое слово не является окончанием другого кодового слова.

Обратное условие Фано:
Закодированное сообщение можно однозначно декодировать с конца, если никакое кодовое слово не является окончанием другого кодового слова.

Начнем проверять по порядку:

0 — быть не может, так как О-0 (также кодовое слово не может начинаться с 0, так как не выполнится условие Фано),

1 — быть не может, так как с единицы начинаются Т-111 и П-100,

10 — быть не может, так как с 10 начинается П-100,

11 — быть не может, так как с 11 начинается Т-111,

100 — быть не может, так как П-100,

101 — подходит , так как выполняется условие Фано,

110 — подходит , так как выполняется условие Фано.

По условию задачи, если слов будет несколько, нужно выбрать код с наименьшим числовым значением — поэтому выбираем 101 .