какой набор букв закодирован двоичной строкой 1100000100110
Какой набор букв закодирован двоичной строкой 1100000100110
Для 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 букв.
Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 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. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?
Для однозначного декодирования получившееся в результате сокращения кодовое слово не должно быть началом никакого другого. Второй вариант ответа не подходит, поскольку код буквы А является началом кода буквы В. Третий вариант не подходит, поскольку код буквы В является началом кода буквы Г. Четвёртый вариант ответа подходит.
Какой набор букв закодирован двоичной строкой 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 букв латинского алфавита заданы их двоичные коды (для некоторых букв из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
Какая последовательность из 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 |
Используем метод подстановки. Для этого приведенные варианты заменим двоичными кодами:
Максимальное количество слов (последовательностей)
Задание 1. В алфавите формального языка два знака («0» и «1») и каждое слово этого языка состоит из семи букв.
Определить максимальное количество слов в языке.
Существует формула, определяющая максимально возможное количество комбинаций (слов) фиксированной длины определенного алфавита:
m – это количество символов в алфавите. У нас их два – 0 и 1. Значит m = 2.
k – это длина слова, т.е. количество знакомест, отводимых под каждое из них. По условию задачи k = 7.
N – максимально возможное количество различных комбинаций из m знаков при длине слова в k знакомест.
В данном случае N = 2 7 = 128.
Ответ. Максимальное количество слов (комбинаций), состоящих из 7-ми букв (знакомест), в алфавите из 2-х знаков равно 128.
Задание 2. Определить количество различных последовательностей, которые можно закодировать с помощью двоичных слов, состоящих из восьми символов (знакомест).
Используется та же формула: N = m k
В данном случае m = 2, k = 8, следовательно, N = 2 8 = 256.
Ответ. Максимальное количество последовательностей, которые можно закодировать с помощью двоичных слов, состоящих из восьми букв, равно 256.
Задание 3. Определить количество различных последовательностей из символов «a”, «b”, «c”, «%”, «&” длиной в три символа.
Используется формула: N = m k
Количество букв (символов) алфавита равно 5, т.е. m = 5. Длина слова – k = 3. Получаем N = 5 3 = 125
Ответ. Количество последовательностей из пяти любых символов длиной в три символа равно 125.
Шифрование. Кодирование
Задание 1. Для шифрования каждой буквы используются двузначные числа. Известно, что буква «е» закодирована числом 20. Среди слов «елка», «полка», «поле», «пока», «кол» есть слова, кодируемые последовательностями цифр 11321220, 20121022.
Выясните код слова «колокол».
Решение.
Задание 2. Для пяти букв алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
Решение.
Задание 1. Исследователь наблюдает изменение параметра, который может принимать одно из семи значений. Значения записываются при помощи минимального количества бит. Исследователь зафиксировал 120 значений.
Определите информационный объем результатов наблюдения.
Нам известно максимальное количество значений, которые требуется закодировать с помощью одинаково количества знаков алфавита. Это семь.
В качестве алфавита используется бит, который может принимать всего два значения (0 и 1).
Для определения минимального количества бит, необходимых для кодирования одного значения, воспользуемся формулой Хартли: k = log2N. Здесь k – это количество бит, а N – кодируемое количество значений.
В нашем случае: k = log27. Другими словами, в какую степень нужно возвести двойку, чтобы получить семерку? Мы знаем, что 2 2 = 4, а 2 3 = 8. Следовательно, значение k находится между 2 и 3 и является дробью. Но количество бит не может быть дробным числом. Поэтому в данном случае, для кодирования одного значения требуется 3 бита.
Поскольку исследователь зафиксировал 120 значений, то общий информационный объем наблюдения равен (3 * 120 =) 360 битам или (360 / 8 =) 45 байтам.
Ответ. Информационный объем 120 наблюдений, принимаемых семь различных значений, равен 45 байтам.
Задание 2. Если каждый символ кодируется двумя байтами, то каков информационный объем следующего предложения в коде Unicode:
Сегодня 35 градусов тепла.
Посчитаем общее количество символов в предложении с учетом пробелов, цифр и знаков препинания. В данном случае, всего 26 символов.
Каждый символ кодируется двумя байтами. Значит информационный объем предложения равен (26 * 2 =) 52 байта или (52 * 8) = 416 бита.
Ответ. Информационный объем предложения равен 416 бит.
Задание 3. Каждое показание датчика, фиксируемое в памяти компьютера, занимает 20 бит. Записано 54 показания датчика. Каков информационный объем снятых значений в байтах?
Информационный объем сообщения в битах равен (20 * 54 =) 1080, что в переводе в байты равно (1080 / 8 =) 135.
Ответ. Информационный объем снятых значений равен 135 байт.
Передача данных
Задание 1. Длительность непрерывной передачи данных в сеть Интернет было 12 минут. Определите максимальный размер файла в мегабайтах, который может быть передан за это время, если скорость передачи информации в среднем была 128 килобит/с.
Решение.
Ответ. Размер файла, который можно передать по сети за 12 минут на скорости в 128 килобит/с, составляет 11,25 Мб.
Задание 2. Сколько времени потребуется сети, работающей со скоростью 56000 бит/с, для передачи 30 страниц текста по 50 строк в 70 символов каждая, при условии, что каждый символ кодируется одним байтом.
Решение.
Ответ. Для передачи 30 страниц текста по 50 строк, состоящих из 70 символов, со скоростью в 56 000 бит/с потребуется 15 секунд.
Задание 3. Сколько секунд потребуется модему, передающему сообщения со скоростью 14400 бит/с, чтобы передать сообщение длиной 225 Кбайт.
Решение.
Какой набор букв закодирован двоичной строкой 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
Более подробное решение данного задания представлено в видеоуроке: