для 5 букв русского алфавита заданы их двоичные коды
infoegehelp.ru
Разбор задачи A13 (демо ЕГЭ 2006)
Для 5 букв русского алфавита заданы их двоичные коды (для некоторых букв ‑ из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
| В | К | А | Р | Д |
|---|---|---|---|---|
| 000 | 11 | 01 | 001 | 10 |
Из четырех полученных сообщений в этой кодировке, только одно прошло без ошибки и может быть корректно декодировано. Найдите его:
Построим графы для быстрого поиска в двоичной строке букв:
На графе розовым цветом выделены коды иcпользуемых букв.
Начнем с варианта 1:
Анализ строки 110100000100110011 происходит так:
1) берем первый символ. Он равен «1», поэтому смотрим граф с вершиной, равной «1»:
Видно, что в этом графе есть коды: 10 и 11.
2) берем второй символ. Он равен «1», поэтому идем по правой ветке: 1→11. кодом «11» закодирована буква К.
После того как нашли символ, анализ снова начинаем с вершины графа.
3) берем следующий третий символ. Он равен «0», поэтому смотрим граф с вершиной, равной «0»:
Видно, что в этом графе есть коды: 01, 000 и 001.
5)берем четвертый символ. Он равен «1», поэтому идем по правой ветке: 0→01. кодом «01» закодирована буква A.
и т.д. для остальных символов закодированной строки.
В таблицах ниже описан полный анализ всех строк:
| Двоичная строка | 11 01 000 001 001 10 01 1 | |||||||
|---|---|---|---|---|---|---|---|---|
| Путь в графе до кода буквы | 1→11 | 0→01 | 0→00→000 | 0→00→001 | 0→00→001 | 1→10 | 0→01 | 1 |
| Двоичная строка, разбитая на коды букв | 11 | 01 | 000 | 001 | 001 | 10 | 01 | 1 |
| Буква | К | А | В | Р | Р | Д | А | — |
| Двоичная строка | 11 10 10 000 01 001 001 1 | |||||||
|---|---|---|---|---|---|---|---|---|
| Путь в графе до кода буквы | 1→11 | 1→10 | 1→10 | 0→00→000 | 0→01 | 0→00→001 | 0→00→001 | 1 |
| Двоичная строка, разбитая на коды букв | 11 | 10 | 10 | 000 | 01 | 001 | 001 | 1 |
| Буква | К | Д | Д | В | А | Р | Р | — |
| Двоичная строка | 11 01 000 01 001 10 01 11 | |||||||
|---|---|---|---|---|---|---|---|---|
| Путь в графе до кода буквы | 1→11 | 0→01 | 0→00→000 | 0→01 | 0→00→001 | 1→10 | 0→01 | 1→11 |
| Двоичная строка, разбитая на коды букв | 11 | 01 | 000 | 01 | 001 | 10 | 01 | 11 |
| Буква | К | А | В | А | Р | Д | А | К |
| Двоичная строка | 11 01 10 000 10 01 10 01 0 | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Путь в графе до кода буквы | 1→11 | 0→01 | 1→10 | 0→00→000 | 1→10 | 0→01 | 1→10 | 0→01 | 0 |
| Двоичная строка, разбитая на коды букв | 11 | 01 | 10 | 000 | 10 | 01 | 10 | 01 | 0 |
| Буква | К | А | Д | В | Д | А | Д | А | — |
Сообщения вариантов 1, 2, 4 оканчиваются кодом, которым не закодирована ни одна буква:
Сообщение варианта 3 может быть корректно декодировано.
Для 5 букв русского алфавита заданы их двоичные коды
Для 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 букв латинского алфавита заданы их двоичные коды (для некоторых букв из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
Какая последовательность из 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. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?
Для однозначного декодирования получившееся в результате сокращения кодовое слово не должно быть началом никакого другого. Второй вариант ответа не подходит, поскольку код буквы А является началом кода буквы В. Третий вариант не подходит, поскольку код буквы В является началом кода буквы Г. Четвёртый вариант ответа подходит.
Для 5 букв русского алфавита заданы их двоичные коды
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
Более подробное решение данного задания представлено в видеоуроке:
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 |
Используем метод подстановки. Для этого приведенные варианты заменим двоичными кодами:
Декодирование двоичных кодов в буквенные сообщения
Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:
Какой набор букв закодирован двоичной строкой 011000101011?
Из таблицы видно, что в данной ситуации выполнено условие Фано (кодовое слово любой буквы не является началом кодового слова другой), поэтому однозначно можем раскодировать сообщение с начала.
Разбиваем двоичную строку на части (слева направо) с помощью данной в условии таблицы и переписываем ее, заменяя кодовые слова на буквы: 011|00|010|10|11 = debac.
Для 6 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:
Какой набор букв закодирован двоичной строкой 101000110100100? Буквы не могут повторяться.
Из таблицы видно, что в данной ситуации не выполнены условие Фано (кодовое слово любой буквы не является началом кодового слова другой) и обратное условие Фано (кодовое слово любой буквы не является концом кодового слова другой), поэтому код нельзя раскодировать однозначно.
Разбиваем двоичную строку на части (слева направо) с помощью данной в условии таблицы (получим 2 возможных случая):
Во (2) случае мы видим повторение кодовых слов 00 и 101. Значит, случай (2) не подходит (т.к. по условию буквы не могут повторяться).
Значит, наш ответ – (1) случай. Перепишем его, заменяя кодовые слова на буквы: 101|000|11|01|00|100 = acebdf.
Для 6 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:
Какой набор букв закодирован двоичной строкой 0010001011011101?
Из таблицы видно, что в данной ситуации выполнено обратное условие Фано (кодовое слово любой буквы не является концом кодового кода другой), поэтому можем однозначно раскодировать сообщение с конца.
Разбиваем двоичную строку на части (справа налево) с помощью данной в условии таблицы и переписываем, заменяя кодовые слова на буквы: 001|00|010|110|11|101 = cdebaf.
Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:
Какой набор букв закодирован двоичной строкой 100111000011? Буквы не могут повторяться.
Из таблицы видно, что в данной ситуации не выполнены условие Фано (кодовое слово любой буквы не является началом кодового слова другой) и обратное условие Фано (кодовое слово любой буквы не является концом кодового слова другой), поэтому код нельзя раскодировать однозначно.
Разбиваем двоичную строку на части (слева направо) с помощью данной в условии таблицы (получим 2 возможных случая):
Во (2) случае мы видим повторение кодовых слов 011 и 10. Значит, случай (2) не подходит (т.к. по условию буквы должны быть различные).
Значит, наш ответ – (1) случай. Перепишем его, заменяя кодовые слова на буквы: 10|01|110|00|011 = XWIZY.
Для 4 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех), и для 1 буквы двоичный код незвестен. Эти коды представлены в таблице:
Кодовое слово буквы e такое, что оно должно быть минимально возможной длины и удовлетворять обратному условию Фано (кодовое слово любой буквы не является концом кодового слова другой).
Какой набор букв закодирован двоичной строкой 000100111110?
Чтобы выяснить двоичный код буквы e, построим граф. Так как обратное условие Фано должно выполняться, кодовое слово любой буквы не должно являться концом кодового слова другой. Значит, строим граф ”с конца” кодового слова (то есть читаем значения задом наперед: a: 01 \(\rightarrow\) 10, b: 110 \(\rightarrow\) 011, c: 00 \(\rightarrow\) 00, d: 010 \(\rightarrow\) 010).
Из графа видно, что кодовое слово минимальной длины, удовлетворяющее обратному условию Фано, – 11. Значит, кодовое слово буквы e – 11.
В данной ситуации выполнено обратное условие Фано, поэтому можем однозначно раскодировать сообщение с конца.
Разбиваем двоичную строку на части (справа налево) с помощью данной в условии таблицы и переписываем, заменяя кодовые слова на буквы: 00|010|01|11|110 = cdaeb.
Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех), и для 1 буквы двоичный код незвестен. Эти коды представлены в таблице:
Кодовое слово буквы f такое, что оно должно быть минимально возможной длины и удовлетворять условию Фано (кодовое слово любой буквы не является началом кодового кода другой).
Какой набор букв закодирован двоичной строкой 1000000010110111?
Чтобы выяснить двоичный код буквы f, построим граф. Так как условие Фано должно выполняться, кодовое слово любой буквы не должно являться началом кодового слова другой. Значит, строим граф ”с начала” кодового слова.
Из графа видно, что кодовое слово минимальной длины, удовлетворяющее условию Фано, – 000. Значит, кодовое слово буквы f – 000.
Здесь выполнено условие Фано, поэтому можем однозначно раскодировать сообщение с начала.
Разбиваем двоичную строку на части (слева направо) с помощью данной в условии таблицы и переписываем строку, заменяя кодовые слова на буквы: 100|000|001|01|101|11 = cfebad.
Для 3 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из одного бита, для некоторых — из двух), и для 1 буквы двоичный код незвестен. Эти коды представлены в таблице:
Кодовое буквы d такое, что оно должно быть минимально возможной длины и кодовое слово буквы b должно являться началом этого кодового слова.
Какой набор букв закодирован двоичной строкой 0100110? Буквы не могут повторяться.
Чтобы выяснить двоичный код буквы d, построим граф. Так как кодовое слово буквы b должно являться началом кодового слова d, строим граф ”с начала” кодового слова.
Из графа видно, что кодовое слово минимальной длины, началом которого является кодовое слово буквы b, – 01. Значит, кодовое слово буквы d – 01.
Из таблицы видно, что в данной ситуации не выполнены условие Фано (кодовое слово любой буквы не является началом кодового слова другой) и обратное условие Фано (кодовое слово любой буквы не является концом кодового слова другой), поэтому код нельзя раскодировать однозначно.
Разбиваем двоичную строку на части (слева направо) с помощью данной в условии таблицы (получим 2 возможных случая):
В (1) случае мы видим повторение кодового слова 01. Значит, случай (1) не подходит (по условию буквы не должны повторяться).
Значит, наш ответ – (2) случай. Перепишем его, заменяя кодовые слова на буквы: 01|00|11|0 = dcab.