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

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

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

Какой набор букв закодирован двоичной строкой 1100000100110?

Мы видим, что выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова, поэтому однозначно можем раскодировать сообщение с начала.

Разобьём код слева направо по данным таблицы и переведём его в буквы:

110 000 01 001 10 — b a c d e.

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

Какой набор букв закодирован двоичной строкой 1000110110110? Все буквы в последовательности — разные.

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

Будем пробовать разные варианты, отбрасывая те, в которых получаются повторяющиеся буквы:

1) 100 011 01 10 110

Первая буква определяется однозначно, её код 100: a.

Пусть вторая буква — с, тогда следующая буква — d, потом — e и b.

Такой вариант удовлетворет условию, значит, окончательно получили ответ: acdeb.

Для 6 букв латинского алфавита заданы их двоичные коды (для некоторых букв из двух бит, для некоторых – из трех). Эти коды представлены в таблице:

001001001111101

Какая последовательность из 6 букв закодирована двоичной строкой 011111000101100?

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

Будем пробовать различные варианты:

1) 011 11 100 0101100

Первая буква определяется однозначно, её код 011: D.

Вторая буква также определится однозначно — E.

Пусть третья буква B, тогда следующая начинается с кода 010, но таких букв в таблице нет, значит, предположение не верно.

2) 011 11 10 00 101 100

Третья буква — С, потом — A. Мы хотим получить ещё две буквы, чтобы в сумме их было 6, тогда следующая буква — F, и последняя — B.

Окончательно получили ответ: DECAFB.

Примечание. DECACEA не подходит, так как 7 букв.

так же подходит decacea

011 11 10 00 10 11 00

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

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

Из примера видно, что 2 знака кодируются 10 двоичными разрядами (битами), на каждую цифру отводится 5 бит. В условии сказано, что каждая цифра записывается кодом длиной 4 знака, значит, пятую цифру можно отбросить.

Разобьём двоичную запись на группы по 5 знаков: 01100 01010 01001 00110. Отбрасываем последнюю цифру в каждой пятёрке и переводим в десятичную запись:

0110 0101 0100 0011 — 6 5 4 3.

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

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

Источник

infoegehelp.ru

Разбор задачи A13 (демо ЕГЭ 2005)

Определить, какой набор букв закодирован двоичной строкой 0110100011000

Построим графы для быстрого поиска в двоичной строке букв:

На графе розовым цветом выделены коды искомых букв.

На рисунке видно, что декодирование цепочки символов будет неоднозначным, т.к. идет дублирование (повторение) части кода другого символа. Например, в коде буквы E ( 01 1) дублируется код буквы B ( 01 ), а в коде буквы C ( 10 0) дублируется код буквы D ( 10 ).

При раскодировании последовательности будем стараться использовать буквы, код которых длиннее, чтобы быстрее рассмотреть всю последовательность. Например, если встретится последовательность 011, то сначала ее раскодируем как E. И если идущий дальше код раскодироваь нельзя, то вернемся обратно и выберем вместо E букву B. Также поступим с буквами C и D.

Анализ строки 0110100011000 происходит так:

1) берем первый символ. Он равен «0», поэтому смотрим граф с вершиной, равной «0»:

Видно, что в этом графе есть коды: 01, 000, 011.

2) берем второй символ. Он равен «1», поэтому идем по правой ветке: 0→01 (на рисунке розовая стрелка). Получаем код «01». Им закодирован символ «B».

Если взять следующий 3-й символ (он равен «1»), то пойдем по ветке 0→01→011 (на рисунке синие стрелки). Получится код «011». Им закодирована буква E.

Далее анализ снова начинаем с вершины графа

3)берем четвертый символ. Он равен «0», поэтому смотрим граф с вершиной, равной «0».

Видно, что в этом графе есть коды: 01, 000, 011.

4)берем пятый символ. Он равен «1», поэтому идем по правой ветке: 0→01 (на рисунке розовая стрелка). Получаем код «01». Им закодирован символ «B».

Надо проверить, даст ли следующий (шестой) символ букву E. Он равен «0», поэтому пойдем по ветке 0→01→010. Получится код 010. Следовательно, E не получим. Остановимся на букве B.

Далее анализ снова начинаем с вершины графа

5)снова берем шестой символ. Он равен «0», поэтому смотрим граф с вершиной, равной «0».

В таблицах ниже описан анализ всей строки:

Двоичная строка	011 01 000 110 00
Путь в графе до кода буквы	0→01→011	0→01	0→00→000	1
Двоичная строка, разбитая на коды букв	011	01	000	—
Буква	E	B	A	—

Т.к. строку раскодировать не удалось, то возвращаемся к букве E. Берем вместо » E «, букву » B «:

Двоичная строка	01 10 100 011 000
Путь в графе до кода буквы	0→01	1→10	1→10→100	0→01→011	0→00→000
Двоичная строка, разбитая на коды букв	01	10	100	011	000
Буква	B	D	C	E	A

Используем метод подстановки. Для этого приведенные варианты заменим двоичными кодами:

Источник

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

010 010 001 110 010

Результат: 22162

Решение ЕГЭ данного задания по информатике, видео:

ЕГЭ 5.2: Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:

a	b	c	d	e
000	110	01	001	10

Результат: b a c d e.

2 вариант решения: Этот вариант решения 5 задания ЕГЭ более сложен, но тоже верен.

Результат: b a c d e.

Кроме того, вы можете посмотреть видео решения этого задания ЕГЭ по информатике:

Решим следующее 5 задание:

Где сами цифры исходного числа: 0010 1 0011 0 (0010 — 2, 0011 — 3)

Первая добавленная цифра 1 после двоичной двойки — это проверка четности (1 единица в 0010 — значит нечетное), 0 после двоичной тройки — это также проверка нечетности (2 единицы в 0011, значит — четное).

Исходя из разбора примера решаем нашу задачу так: поскольку «нужные» нам цифры образуются из групп по 4 числа в каждой плюс одно число на проверку четности, то разобьем закодированное сообщение на группы по 5, и отбросим из каждой группы последний символ:

01100 01010 01001 00110

0110 0101 0100 0011

Вы можете посмотреть видео решения этого задания ЕГЭ по информатике:

Кодовые слова 01 и 00 использовать нельзя, так как тогда нарушается условие Фано (начинаются с 0, а 0 — это Н).

Возьмем для буквы Л кодовое слово 11. Тогда для четвёртой буквы нельзя подобрать кодовое слово, не нарушая условие Фано (если потом взять 110 или 111, то они начинаются с 11).

Значит для надо использовать трёхзначные кодовые слова. Закодируем буквы Л и Мкодовыми словами 110 и 111.

Суммарная длина всех четырёх кодовых слов равна (Н)1 + (К)2 + (Л)3 + (М)3 = 9.

1 вариант решения: будем использовать дерево

Суммарная длина всех четырёх кодовых слов равна (Н)1 + (К)2 + (Л)3 + (М)3 = 9.

РАЗБОР ЗАДАНИЯ 5 ЕГЭ ПО ИНФОРМАТИКЕ 2017

Следующим наименьшим кодом было бы двухбуквенное слово 00. Так как оно не является префиксом ни одного из представленных кодовых слов, то Г = 00.

Результат: 00

Результат: 101

Подробней разбор урока можно посмотреть на видео ЕГЭ по информатике 2017:

1 — не подходит (все буквы кроме А начинаются с 1)
10 — не подходит (соответствует коду Д)
11 — не подходит (начало кодов Б, В и Г)
100 — не подходит (код Д — 10 — является началом данного кода)
101 — не подходит (код Д — 10 — является началом данного кода)
110 — не подходит (начало кода В и Г)
111 — не подходит (соответствует коду Б)
1000 — не подходит (код Д — 10 — является началом данного кода)
1001 — не подходит (код Д — 10 — является началом данного кода)
1010 — не подходит (код Д — 10 — является началом данного кода)
1011 — не подходит (код Д — 10 — является началом данного кода)
1100 — не подходит (начало кода В и Г)
1101 — подходит

Результат: 1101

Более подробное решение данного задания представлено в видеоуроке:

Источник