Задание 11

Общая идея этих задач в том, что даётся набор значений, необходимо понять, сколько информации необходимо, чтобы зашифровать один символ из этого набора и сколько - для последовательности символов.

Чаще всего необходимо ещё до подсчёта получить кол-во бит на один символ, понять, какое минимальное число байт необходимо для хранения этих битов и дальше оперировать уже байтами.

Например, если дан набор значений А, Б, В, Г, Д, К содержит 6 элементов, чтобы понять, сколько бит для него необходимо выделить, следует найти такую минимальную степень двойки, что она будет больше их количества.

Для 6 минимальная степень двойки, которая больше него - это $2^3$. Получается, что для хранения одного символа потребуется 3 бита. В одном байте 8 бит, поэтому если в задаче говорится, что каждый символ хранится в целом количестве байт, то для одного символа нам будет достаточно одного байта.

Пример 1

Задача

При регистрации в компьютерной системе каждому объекту сопоставляется идентификатор, состоящий из 15 символов и содержащий только символы из 8-символьного набора: А, В, C, D, Е, F, G, H. В базе данных для хранения сведений о каждом объекте отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование идентификаторов, все символы кодируют одинаковым и минимально возможным количеством бит.

Кроме собственно идентификатора, для каждого объекта в системе хранятся дополнительные сведения, для чего отведено 24 байта на один объект. Определите объём памяти (в байтах), необходимый для хранения сведений о 20 объектах. В ответе запишите только целое число – количество байт.

алфавит состоит из 8 символов, так как $8 = 2^3$, то на каждый символ нужно выделить не менее $3 бит$

для хранения $15$ символов нужно $15 * 3 бита = 45 бит$ или $6 байт$ (с округлением до целого числа байт)

идентификатор + дополнительные сведения занимают $6 + 24 = 30 байт$

на хранения информации о $20$ объектах нужно $20 * 30 = 600 байт$

Ответ: 600 байт.

Пример 2

Задача

Информационная панель может отображать сообщения, состоящие из $10$ цифр, причем каждая цифра может быть трёх цветов. Цифры и цвета могут повторяться. Контроллер панели выделяет под каждое сообщение одинаковое и минимальное возможное целое число байт. При этом используется посимвольное кодирование, все символы сообщения кодируются одинаковым минимально возможным количеством бит. Укажите объем памяти в байтах для хранения $100$ сообщений.

на панели 10 позиций, каждая позиция – это цифра, которая может гореть одним из трёх цветов

подсчитаем, сколько сигналов можно закодировать с помощью одной позиции панели: выбираем $1$ из $10$ цифр, и кроме того (независимо от цифры!) один из трёх цветов; поэтому общее количество вариантов равно $10 * 3 = 30$

для кодирования $30$ вариантов нужно $5$ битов ($2^4 \leq 30 \leq 2^5)

для кодирования состояния 10 позиций панели нужно $10 * 5 = 50$ битов или $6.25 байта$, округляем вверх до $7$ байтов (на одно сообщение)

на кодирование $100$ сообщений требуется $100 * 7 = 700 байт$

Ответ: 700 байт.

Пример 3

Задача

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из $11$ символов. Из соображений информационной безопасности каждый пароль должен содержать хотя бы $2$ десятичных цифры, как прописные, так и строчные латинские буквы, а также не менее 2-х символов из 6-символьного набора: «&», «#», «$», «*», «!», «@». В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт.

При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей. Для хранения сведений о 30 пользователях потребовалось $900 байт$. Сколько байт выделено для хранения дополнительных с ведений об одном пользователе? В ответе запишите только целое число – количество байт.

если бы мы знали точно, сколько цифр и сколько специальных символов содержит пароль и где точно они расположены, можно было бы использовать «раздельное» кодирование: на кодирование цифр использовать по $4$ бита ($2^4 > 10$), на кодирование спецсимволов – по 3 бита ($2^3 > 6$), а на кодирование остальных символов (латинских букв) – по 6 бит ($2^6 > 26*2=52$)

поскольку количество и месторасположение цифр и спецсимволов а пароле неизвестно, нужно рассматривать полный набор символов: $10 + 6 + 26*2 = 68$

при этом на каждый символ нужно выделить 7 бит ($27 > 68$)

на 11 символов пароля выделяется $77 бит$, округляя вверх до целого числа байт получаем $10 байт$ ($80 бит$) на пароль

на одного пользователя выделяется $900 / 30 = 30 байт$

на дополнительную информацию остается $30 – 10 = 20 байт$

Ответ: 20.

Пример 4

Задача

В велокроссе участвуют $119$ спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем в битах сообщения, записанного устройством, после того как промежуточный финиш прошли $70$ велосипедистов?

велосипедистов было $119$, у них $119$ разных номеров, то есть, нам нужно закодировать $119$ вариантов

по таблице степеней двойки находим, что для этого нужно минимум $7$ бит (при этом можно закодировать $128$ вариантов, то есть, еще есть запас); итак, $7$ бит на один отсчет

когда $70$ велосипедистов прошли промежуточный финиш, в память устройства записано $70$ отсчетов

поэтому в сообщении $70*7 = 490 бит$ информации.

Ответ: 490 бит.

Пример 5

Задача

Объем сообщения, содержащего 4096 символов, равен 1/512 части Мбайта. Какова мощность алфавита, с помощью которого записано это сообщение?

в сообщении было $4096 = 2^{12}$ символов

объем сообщения

$$1/512 Мбайта = 223 / 512 бита = 223 / 29 бита = 214 бита (= 16384 бита!)$$

место, отведенное на 1 символ:

$$214 бита / 212 символов = 22 бита на символ = 4 бита на символ$$

$4$ бита на символ позволяют закодировать $2^4 = 16$ разных символов

поэтому мощность алфавита – $16$ символов

Ответ: 16 символов

Пример 6

Задача

В зоопарке 32 обезьяны живут в двух вольерах, А и Б. Одна из обезьян заболела. Сообщение «Заболевшая обезьяна живет в вольере А» содержит 4 бита информации. Сколько обезьян живут в вольере Б?

информация в $4$ бита соответствует выбору одного из 16 вариантов,

поэтому в вольере $А$ живет $1/16$ часть всех обезьян (это самый важный момент!)

всего обезьян – $32$, поэтому в вольере $А$ живет

$32/16 = 2 обезьяны$

поэтому в вольере Б живут все оставшиеся

$32 – 2 = 30 обезьян$

Ответ: 30.

Пример 6

Задача

В корзине лежат 32 клубка шерсти, из них 4 красных. Сколько бит информации несет сообщение о том, что достали клубок красной шерсти?

красные клубки шерсти составляют 1/8 от всех,

поэтому сообщение о том, что первый вынутый клубок шерсти – красный, соответствует выбору одного из 8 вариантов

выбор 1 из 8 вариантов – это информация в 3 бита (по таблице степеней двойки)

Ответ: 3.

Пример 7

Задача

В некоторой стране автомобильный номер длиной $7$ символов составляется из заглавных букв (всего используется $26$ букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным целым количеством байт. Определите объем памяти, необходимый для хранения $20$ автомобильных номеров.

всего используется 26 букв + 10 цифр = 36 символов

для кодирования 36 вариантов необходимо использовать 6 бит, так как $2^5=32\lt 16 \leq 2^6=64$,

т.е. пяти бит не хватит (они позволяют кодировать только $32$ варианта), а шести уже достаточно

таким образом, на каждый символ нужно $6$ бит (минимально возможное количество бит)

полный номер содержит $7$ символов, каждый по $6 бит$, поэтому на номер требуется $6*7=42 бита$

по условию каждый номер кодируется целым числом байт (в каждом байте – $8 бит$), поэтому требуется 6 байт на номер ($5*8=40\lt\leq 6*8=48$), пяти байтов не хватает, а шесть – минимально возможное количество

на $20$ номеров нужно выделить $20*6=120 байт$

Ответ – 120.

Возможные ловушки:

• если не обратить внимание на то, что каждый номер кодируется целым числом БАЙТ, получаем неверный ответ $2$ ( $20*42=105*8 бит = 105 байт$)
• если по невнимательности считать, что каждый СИМВОЛ кодируется целым числом байт, получаем $7$ байт на символ и всего $140 байт$ (неверный ответ $4$)
• если «забыть» про цифры, получим всего $26$ символов, $5 бит$ на символ, $35 бит$ ($5$ полных $байт$) на каждый номер и неверный ответ $100 байт$ (на $20$ номеров)

Задания для самостоятельного выполнения