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

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

Для 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

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

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

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

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

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

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

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

2) берем второй символ. Он равен «1», поэтому идем по правой ветке: 1→11. кодом «11» ничего не закодировано.

3)берем третий символ. Он равен «0», спускаемся по ветке: 1→11→110. Получаем код «110». им закодирован символ «b».

После того как нашли символ, анализ снова начинаем с вершины графа.

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

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

5) берем пятый символ. Он равен «0», поэтому идем по левой ветке: 0→00. кодом «00» ничего не закодировано.

6) берем шестой символ. Он равен «0», поэтому идем по левой ветке: 0→00→000. Получаем код «000». им закодирован символ «a».

и т.д. для остальных символов закодированной строки.

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

Двоичная строка	110 000 01 001 10
Путь в графе до кода буквы	1→11→110	0→00→000	0→01	0→00→001	1→10
Двоичная строка, разбитая на коды букв	110	000	01	001	10
Буква	b	a	с	d	e

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

Источник

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

Для 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 букв.

Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 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. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?

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

Источник

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

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

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

Источник

Кодирование и декодирование информации. ЕГЭ

Задание:

1) Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11 соответственно). Если таким способом закодировать последовательность символов ГБАВ и записать результат в шестнадцатеричной системе счисления, то получится:
1) 132 ₁₆ 2) D2 ₁₆ 3) 3102 ₁₆ 4) 2D ₁₆

Решение и ответ:

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

1) 138 ₁₆ 2) DBCA ₁₆ 3) D8 ₁₆ 4) 3120 ₁₆

Решение и ответ:

По условию:
А = 00
Б = 01
В = 10
Г = 11
Значит:
ГБВА = 11011000 в двоичной системе. Переведем в шестнадцатеричную и получим D8
Ответ: 3

Решение и ответ:

4) Для кодирования букв А, Б, В, Г используются четырехразрядные последовательные двоичные числа от 1000 до 1011 соответственно. Если таким способом закодировать последовательность символов БГАВ и записать результат в восьмеричном коде, то получится:
1) 175423 2) 115612 3) 62577 4) 12376

Решение и ответ:

По условию:
А = 1000
Б = 1001
В = 1010
Г = 1011
БГАВ = 1001101110001010, теперь слудует перевести данное число из двоичной в восьмеричную, и получить ответ.
1001101110001010₂ = 115612₈

Ответ: 2

Для кодирования букв А, В, С, D используются трехразрядные последовательные двоичные числа, начинающиеся с 1 (от 100 до 111 соответственно). Если таким способом закодировать последовательность символов CDAB и записать результат в шестнадцатеричном коде, то получится:
1) А52₁₆ 2) 4С8₁₆ 3) 15D₁₆ 4) DE5₁₆

Решение и ответ:

По условию: Соответственно
A = 100
B = 101
C = 110
D = 111
СDAB = 110111100101, переведем двоичное число в шестнадцатеричную:
110111100101₂ = DE5₁₆
Ответ: 4

6) Для кодирования букв К, L, М, N используются четырехразрядные последовательные двоичные числа от 1000 до 1011 соответственно. Если таким способом закодировать последовательность символов KMLN и записать результат в восьмеричном коде, то получится:
1) 84613₈ 2) 105233₈ 3) 12345₈ 4) 776325₈

Решение и ответ:

По условию: соответственно
K = 1000
L = 1001
M = 1010
N = 1011
KMLN = 1000101010011011, переведем в восьмеричное число:

Ответ: 2

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

а b с d е
100 110 011 01 10
Определите, какой набор букв закодирован двоичной строкой 1000110110110, если известно, что все буквы в последовательности – разные:
1) cbade 2) acdeb 3) acbed 4) bacde

Решение и ответ:

Запишем двоичный код в виде битов: Методом перебора возможных вариантов, чтобы не повторялись буквы.
Получается: 100 011 01 10 110
Следовательно: acdeb
Ответ: 2

8) Для 6 букв латинского алфавита заданы их двоичные коды (для некоторых букв из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
А В С D Е F
00 100 10 011 11 101
Определите, какая последовательность из 6 букв закодирована двоичной строкой 011111000101100.
1) DEFBAC 2) ABDEFC 3) DECAFB 4) EFCABD

Решение и ответ:

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

Получаем:
011 11 10 00 101 100
Соответственно: DECAFB
Ответ: 3

9) Для кодирования букв А, В, С, D используются четырехразрядные последовательные двоичные числа, начинающиеся с 1 (от 1001 до 1100 соответственно). Если таким способом закодировать последовательность символов CADB и записать результат в шестнадцатеричном коде, то получится:
1) AF52₁₆ 2) 4CB8₁₆ 3) F15D₁₆ 4) В9СА₁₆

10) Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код:
А Б В Г
00 11 010 011
Если таким способом закодировать последовательность символов ВГАГБВ и записать результат в шестнадцатеричном коде, то получится:
1) CDADBC₁₆ 2) A7C4₁₆ 3) 412710₁₆ 4) 4С7А₁₆

Решение и ответ:

ВГАГБВ = 0100110001111010, переведем в шестнадцатеричную:
0100 1100 0111 1010₂ = 4C7A₁₆

Ответ: 4

11) Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код:
А Б В Г
00 11 010 011
Если таким способом закодировать последовательность символов ГАВБВГ и записать результат в шестнадцатеричном коде, то получится:
1) 62D3₁₆ 2) 3D26₁₆ 3) 31326₁₆ 4) 62133₁₆

Ответ: 1

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

двоичный код:
А Б В Г
00 11 010 011
Если таким способом закодировать последовательность символов ГБВАВГ и записать результат в шестнадцатеричном

коде, то получится:
1) 71013₁₆ 2) DBCACD₁₆ 3) 31A7₁₆ 4) 7A13₁₆

13) Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код:
А Б В Г
00 11 010 011
Если таким способом закодировать последовательность символов ГАВБГВ и записать результат в шестнадцатеричном коде, то получится:
1) DACBDC₁₆ 2) AD26₁₆ 3) 621310₁₆ 4) 62DA₁₆
Решение и ответ: соответственно..

ГАВБГВ = 0110001011011010₂, переведем в шестнадцатеричную:
0110 0010 1101 1010₂ = 62DA₁₆
Ответ: 4

14) Для кодирования сообщения, состоящего только из букв A, B, C, D и E, используется неравномерный по длине двоичный код:
A B C D E
000 11 01 001 10
Какое (только одно!) из четырех полученных сообщений было передано без ошибок и может быть раскодировано:
1) 110000010011110
2) 110000011011110
3) 110001001001110
4) 110000001011110

Решение и ответ:

Возьмем первый код:
11 000 001 001 11 10 = BADDBE
Второй код:
11 000 001 10 11 110 = с ошибкой в конце.
Третий код:
11 000 10 01 001 110 = с ошибкой в конце.
Четвертый код:
11 000 000 10 11 110 = с ошибкой в конце.
Ответ: 1

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

кодирование: А-00, Б-11, В-010, Г-011. Через канал связи передается сообщение: ВАГБГВ. Закодируйте сообщение

данным кодом. Полученную двоичную последовательность переведите в шестнадцатеричный вид.
1) AD34 2) 43DA 3) 101334 4) CADBCD
Решение и ответ:

ВАГБГВ = 0100001111011010₂, переведем в шестнадцатеричную систему:
0100 0011 1101 1010₂ = 43DA₁₆
Ответ: 2

17) Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=100, В=101. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

1) 1 2) 11 3) 01 4) 010

Аналогично заданию номер 16.

Ответ: 2

18) Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый.

Для компактности результат записали в восьмеричной системе счисления. Выберите правильную запись кода.
1) 57414 2) 53414 3) 53412 4) 53012

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

101011100001010₂, переведем данный код в восьмеричную:
101 011 100 001 010₂ = 53412₈

Ответ: 3

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

кодирование: А-0, Б-11, В-100, Г-011. Через канал связи передается сообщение: ГБАВАВГ. Закодируйте сообщение

данным кодом. Полученную двоичную последовательность переведите в восьмеричный код.
1) DBACACD 2) 75043 3) 7A23 4) 3304043
Решение и ответ: Соответственно:
ГБАВАВГ = 0111101000100011₂, переведем в восьмеричную систему.
0 111 101 000 100 011₂ = 75043₈, первый нолик не значащий.
Ответ: 2

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

буквы А, Б и В, которые кодируются следующими кодовыми словами:

A — 11010, Б — 00110, В — 10101.

При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 10110, считается, что передавалась буква Б. (Отличие от кодового слова для Б — только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка(она обозначается‘x’).

Получено сообщение 00111 11110 11000 10111. Декодируйте это сообщение — выберите правильный вариант.

1) БААx
2) БААВ
3) xxxx
4) xAAx

Решение:
1) 00111 = Б, так как 1 ошибка в последней цифре.
2) 11110 = A, так как 1 ошибка в третьей цифре.
3) 11000 = А, так как 1 ошибка в четвертой цифре.
4) 10111 = В, так как 1 ошибка в четвертой цифре

00111 11110 11000 10111 = БААВ.
Ответ: 2

Источник